AzorAhai's blog

How to count simple cycles between cell (1,1) and cell (n,m) in a grid??
By AzorAhai, history, 8 years ago, In English

Hi guys, I was trying to solve this problem http://acm.timus.ru/problem.aspx?space=1&num=1459 obviously the solution is counting simple cycles between cell (1,1) and cell (n,m) in the given grid. but since m is very large I think that we need to use matrix power to solve this problem .. but I could't find any recurrence to use.. any help please?? thanks in advance.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Let dp[i][mask] be the number of simple cycles that visit cells of mask in ith column. Now you can find a formula to compute values of dp[i + 1] using dp[i]. Then you can find a matrix corresponding to this dynamic.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually you have to visit all cells. We need to count "how many such path".

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks egor_bb . but could you please explain your idea with more details??

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I didn't read an actual statement and relied on your explanation.

    If we should visit all the cells then imagine another dynamic. The idea is to construct a resulting cycle column by column. j-th bit in mask will show whether celli, j already has 2 neighbours in the cycle or not. If it doesn't — we should connect it with celli + 1, j. dp[n][0] is the answer.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Then it would be counting the number of ways to divide the grid into disjoint cycles which is not what we want to compute. Instead of keeping just a bitmask for the current column, we need to enumerate connected components in it as well so that later we don't connect cells belonging to the same component.

      → Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

kalimm thank you but number of cells is very huge

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Actually I didn't tell a solution, I just said egor_bb's solution don't match with problem.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Consider the dynamic dp[i][mask], where i is the number of fullfilled rows, 'mask' describes, how the ends of already built path(s) stick out of the columns. For example:

This corresponds to the mask=10010, because the ends stick out of the first and 4-th column. (I suppose N=5, because other cases are analogical and easier.) So this path will be counted in dp[4][10010]. There are only 16 possible masks: 00000, 11000, 10100, ..., 00011, 11220, 11202, 11022, 10122, 01122, 12210, 12201, 12021, 10221, 01221. The latter ten correspond to the cases when we have 4 sticking ends of 2 components of the line. Then we can construct 21x21 matrix A such that dp[n+1]=A*dp[n]. Finally, we just need to output (A^(M-1)*dp[1])[00000].

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you so much Grevozin I am very close to understand what do you mean but could you please tell me in some detail how to construct the array and how the mask can have 2 in some position

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Two more examples:

      In each example we have two components of the cycle, which will be connected later. Note that in the first example new component was spontaneously born on the third step of building the path (I haven't initially noticed this case). First example will be counted in dp[3][12201], an the second in dp[2][11022].

      I did't got what array you mean. We won't have dp in our memory at all, only dp[1] for all masks, which is easy to precalculate, and then use matrix exponentiation. If you mean how to build the matrix: you just need to understand, how dp[n+1][given mask] depends on all dp[n] masks — this will be a linear dependency. This can be done with some terrible brutforce of cases, how the lines from the previous step can glue together, and when these spontaneous burths can take place, which I definitely don't want to do...

      P.S. I guess we have to consider the case N=4 separately, but in the same manner, for the case N=2 the answer is always 1, for N=3 you can output 0, if M is odd, and 2^(M/2-1) otherwise.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know this is old, but a very nice way to solve this kind of problem is to build a DFA that recognizes the language of valid paths on the grid. Each state would correspond to a 1x5 row with arrows representing a broken path. Once you build the DFA, then the problem becomes: How many strings of length M are recognized by this DFA? This is just the number of walks of length M in the DFA, which can easily be solved via matrix exponentiation (it's a classical problem).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe keeping only the five arrows in the state is not enough to guarantee that the cycle is correct. For example, you can't be sure that there are no isolated cycles, in order to guarantee that you have to add some kind of partition of the arrows into pairs like Grevozin describes above. After that it transforms to a standard DP solution that may be treated as the number of walks in the DFA, but it doesn't actally simplify anything. Or maybe I misunderstood your idea?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I didn't make it clear that there will be multiple states corresponding to some of the 1x5 rows in order to fix the issue with isolated cycles. I spent an afternoon a couple of months ago working on Project Euler Problem 237 in order to arrive at this solution :P

      You're right, the DFA solution is equivalent to the other solutions mentioned here, I just thought it's a pretty neat way to formulate the problem!

      → Reply