Could any coder/programer solve it? i'am really stucked

Esther and Daniel are playing a video game called Latticeville. Each level in Latticeville consists of a grid of m by n rooms, and the two players start in the southwest-most room. From each room in the level, the players are only permitted to move north or east. The level ends when both players reach the room furthest northeast. Esther and Daniel want to maximize the amount of the game that they explore collectively, so they want to ensure that—as much as possible—they never visit the same rooms as each other. But there seem to be many different ways to accomplish this. Given the size of a level in Latticeville, determine how many different subsets of rooms Esther and Daniel can visit such that the number of rooms visited is maximal.

Since the answer may be quite large, return the result modulo 109 + 7.

For m = 3 and n = 3, the output should be latticevillePaths(3, 3) = 3. In this level, they can visit a maximum of 8 rooms, and there are three ways for them to do that. The three pairs of routes are depicted below. The rooms that are visited in each case are lightly shaded.

For m = 3 and n = 4, the output should be latticevillePaths(3, 4) = 6. They can visit a maximum of 10 rooms in this level, and there are six ways to do that, depicted below.

what is the answer for the case which is n=5 and m=7 could anyone firgure out an algorithm for any n and m?

Note by Kien Huu Nguyen
6 months, 3 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

I'm almost certain I've seen this problem somewhere before, where did you get it from? (And it seems you're not the only one asking for an answer... https://math.stackexchange.com/questions/2790244/counting-lattice-paths/2790300)

Alex Li - 6 months, 2 weeks ago

Log in to reply

This is a very interesting problem. Did you come across this from some competitive programming site?

Also, before figuring out how many ways are there for them to cover the maximum number of cells, another interesting problem that we can try solving first is figuring out what this maximum number is.

Agnishom Chattopadhyay Staff - 6 months, 3 weeks ago

Log in to reply

A good way to approach this problem is to look at it as a set of smaller problems. For this problem specifically, a good choice is:

How many ways can we traverse an \(m\times n\) grid moving only north and east?

Imagine that we're programming a robot to move through some \(m\times n\) grid. This robot only has two commands: move one space north, and move one space east. We know that the grid is \(n\) spaces tall, so the robot has to move north \(n-1\) times. We also know that the grid is \(m\) spaces wide, so the robot has to move east \(m-1\) times. So, in total, we have \((n-1)+(m-1)=n+m-2\) commands to give the robot, from which, we choose \(n-1\) to tell it to move north. This means the robot can have \[{m+n-2\choose n-1}\] possible paths. This is an application of the stars and bars method.

Before we continue, let's think about the maximum number of spaces Esther and Daniel can hit on a given board. We know that one path will visit \(m+n-1\) spaces, and, in the maximal solution, two paths will only intersect at the beginning and end of the board, giving us \(2(m+n-1)-2 = 2m+2n-4\) spaces. Note here that in a \(1\times n\) or \(m\times 1\) board, there is an exception, but we know that that will always have \(1\) solution that will hit all \(nm\) spaces, so that's not too worrying.

Let's think about the paths that Esther and Daniel can take. If they both move in the same direction on the first space, they will intersect, giving a non-optimal solution. We also know that they will not intersect at their second-to-last move. This means we know that one player must start moving east and end moving north, while the other must start moving north and end moving east.

This means that both players traverse their own, intersecting \(m-1\times n-1\) sub-grid, with one sub-grid situated in the northwest corner of the board and the other situated in the southeast. That looks like this:

Where the red and blue lines represent each player's starting and ending moves, and the red and blue shading representing the grid they must traverse.

So now that we know this, how many ways can they both traverse these sub-grids?
To solve this, we must come up with a new way to represent the traversal of a grid. Let's label each point in the grid based on its distance from the leftmost square in the grid. That will look like this:

Then, any path can be described by a list of the labels of the grid squares where the player moves north. For example, the grid

can be described by the list [0, 2], since the player moves north in those squares.
It should be noted, though, that not every list corresponds with a valid lattice. The list [2, 1], for example, is not valid, since moving north first at label \(2\) and then at label \(1\) would require one step west, which is not allowed. To fix this, we add one restriction: The list must be non-decreasing. Two consecutive numbers can be the same, which corresponds to moving north twice in a row, but if there is a set of numbers in the list that decreases, we know the player must move west, so the grid is not allowed.

Very fortunately for us, there is a function in Python that generates non-decreasing lists of variable size from a given set of integers. This function is itertools.combinations_with_replacement. When used in a certain way, this returns an iterator that will give every non-decreasing list of size \(n-1\) constructed from integers in the interval \([0, m]\). We construct this like so:

def lattice_ville(m, n):
    for i in itertools.combinations_with_replacement(range(1, m), r = n-2):
        # do something here
        pass

Note: From now on, we will assume Esther always travels east to start.

This will give us the list description of every solution to an \(m-1 \times n-1\) rectangular grid. That's all well and good, but it surely isn't the solution. After all, one path for Esther could give way to a plethora of paths for Daniel. How do we solve this problem? Well, let's look at an example. Let's say we're on a \(4\times 4\) grid and Esther traverses her \(3\times 3\) sub-grid with the path represented by [1, 1]. That looks like this:

As you can see, Esther has blocked off a significant portion of Daniel's grid. We could use the same itertools.combinations_with_replacement for Daniel and just root out any intersecting paths that Daniel takes, but that would be wasteful and take a very long time to calculate. After all, just using itertools.combinations_with_replacement once puts our time complexity at \(O({m+n-4 \choose n-2})\), which gets big fast, especially for square-like grids. We want a way to take the output of the itertools function and somehow discover how many paths Daniel can take. Let's call the weird lattice-based polygon that Daniel needs to traverse a lattice-gon. Then we have a new sub-problem.

How many ways can you traverse a lattice-gon?

Let's represent a lattice-gon in the same way we did a traversal path: as a list. For an \(n\)-tall lattice-gon, we can represent it as a list of integers, where the \(i^{\text{th}}\) integer represents the length of the polygon at height \(i\). Let's start with a \(1\)-tall lattice-gon. This is easy: there's only one way to traverse it! We just go east until we finish.

Let's try one level more: a \(2\)-tall lattice-gon. We know that list[0] will give us the length of the first row of the lattice-gon, so we have list[0] places to go north. Once we go north, though, the rest of the problem is analogous to solving a \(1\)-tall lattice-gon, so we know that the number of solutions is equal to list[0].

The next one is harder: a \(3\)-tall lattice-gon. list[0] will give us the length of the first row of the lattice-gon. So we have list[0] ways to do this. Let's say we go north as soon as we can. Then, number of solutions branching from that path is analogous to the number of solutions to the lattice-gon list[1:], which is the list without its first element. If we go east \(x\) times before we go north, we will have cut off the first \(x\) elements of each row, so the number of solutions branching from that path is analogous to the number of solutions to the lattice-gon [i-x for i in list[1:]]. The total number of solutions is the sum of the number of solutions for each branching path.

This recursive pattern repeats for everything greater than \(3\).

One more thing before we write this in Python, though: It actually doesn't matter how long the top row is, so we will omit it in our list. So the function looks like this:

def lattice_gon(a):
    if len(a) == 0: return 1
    if len(a) == 1: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += lattice_gon([x-i for x in a[1:]])
    return sum

So we have two functions, but how do we connect them together? Well, it's really simple: The way that we used the itertools function meshes perfectly with our lattice_gon function! I'll leave it as an exercise to the reader to figure out why, but it shouldn't be too hard.

So our total function looks like:

import itertools
def lattice_gon(a):
    if len(a) == 0: return 1
    if len(a) == 1: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += lattice_gon([x-i for x in a[1:]])
    return sum

def lattice_ville(m, n):
    if m < 3 or n < 3: return 1

    total = 0
    for i in itertools.combinations_with_replacement(range(1, m), r=n-2): #for each path Esther takes
        total += lattice_gon(i) #add to the total the number of paths Daniel can take without intersecting
    return total

print(lattice_ville(5, 7))

This is a really slow function, but is slightly faster than brute-force as it generates no wrong solutions. I think it runs in \[O(m^2{m+n-4 \choose n-2}) \in O(m^2(m+n)!)\]

Which is much faster than the brute force solution, which runs in \[O(((m+n)!)^2)\]

lattice_ville(5,7) returns \(\boxed{1176}\).

Eric Schneider - 5 months, 2 weeks ago

Log in to reply

Thanks for the detailed explanation.

Apparently, Hana Wehbi's solution here has a more analytical approach which solves the problem almost in constant time (except for the cost of computing binomial coefficients), You might want to check it out.

Agnishom Chattopadhyay Staff - 5 months, 2 weeks ago

Log in to reply

In Python:

import itertools
def g(a):
    if len(a) == 2: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += g([x-i for x in a[1:]])
    return sum

def lattice_ville(m, n):
    total = 0
    for i in itertools.combinations_with_replacement(range(1, m), r=n-2): #for each path Esther takes
        a = list(i)
        a.append(m-1)

        total += g(a) #add to the total the number of paths Daniel can take without intersecting
    return total

I'll work on a write-up for how I got here if anybody asks, but the solution is \(\boxed{1176}\).

Eric Schneider - 5 months, 4 weeks ago

Log in to reply

I would really appreciate an explanation.

Agnishom Chattopadhyay Staff - 5 months, 2 weeks ago

Log in to reply

Sounds good! I'm at work right now but I'll write it up when I get home. Expect something around 4 or 5 hours from now!

Eric Schneider - 5 months, 2 weeks ago

Log in to reply

@Eric Schneider Sure, take your time. Your code does look like bruteforce, though.

Agnishom Chattopadhyay Staff - 5 months, 2 weeks ago

Log in to reply

@Agnishom Chattopadhyay This is sufficiently faster than brute force. Originally, I used a brute force method, but that wouldn't solve on larger boards in a reasonable time.

Eric Schneider - 5 months, 2 weeks ago

Log in to reply

A simple but inefficient way to do this is to generate an algorithm (here pseudocode).

Here rooms is a set of all positions in the room (of course this can be replaced by a simple parameterisation), vis is the set of rooms already visitted, posD = the current position of Daniel an posE = current position of Esther.

Calling nextmoves(array of mxn positions,{},(0,0),(0,0)) will return an object containing the length of the longest possible explorations and the # of possible ways to achieve this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
nextmoves(rooms,vis,posD,posE) {
    if posD==posE==End position, then:
        return {length=size(vis), count=1};
    else: 
    loop through all possibilities, i, for next posD and next posE in rooms
    so that posD(i) and posE(i) not in vis u {posD,posE}
    for each i set obj(i) := nextmoves(rooms,vis u {posD,posE},posD(i),posE(i)).
    set m := max all the obj(i).length.
    set c := sum of all obj(i).count for i with obj(i).length==m
    return {length=m, count=c};
}

R Mathe - 6 months, 2 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...