LIFE_GOES_ON's blog

By LIFE_GOES_ON, history, 7 weeks ago, In English,

Here in this CF problem my observations are —

1) There cannot be more paths than n-1

2)If you start going right from any cell , you cannot go upward or downward after its next cell. If the grids are -

A B C D E
F G H I J

You cannot go — A->B->G ....

or A->F->G->H->C...

But I do not know how to proceed further.

In the tutorial they said about calculating prefixes , suffixes . But how these gonna help in handling the time of visiting a cell?

Hey wait ! please help , I want to learn to solve 1600-1800 problems within contest time. So help me :p

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

»
7 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Firstly, you should use block code formatting like this (there's an option for it when writing the blog) to display the grid:

A B C D E 
F G H I J

because otherwise, it won't let you have the newline (look at your own blog to see what I mean).

Your observation is good. The conclusion to draw from that observation is that any valid path will look like this:

image

This entails an initial, perhaps non-existent 'snaking' part (in red), and another, perhaps non-existent other part that goes down to the right end, then comes back down the other row (in green). In fact, this snaking part will always span a specific amount of columns. This gives an easy way to take the maximum over all valid paths. Brute-force the amount of columns spanned by the snaking part (simply keep a running count of how many cells you've visited, and multiply that count by the element in each row/column you touch). This leaves efficiently summing the green part. I will leave this in a spoiler in case you want to figure this out.

Solution

If you want, since I happened to have solved this before, here is my submission. The code is disgusting, though...

»
7 weeks ago, # |
Rev. 23   Vote: I like it +3 Vote: I do not like it

Actually, it can be checked for a small number of columns $$$n$$$ such as 1, 2 and 3 that number of different paths is $$$n$$$, not $$$n-1$$$. For each column $$$j$$$, where $$$1 \leq j \leq n$$$, it is possible to make $$$n-j$$$ moves to the right followed by one up/down move, and then $$$n-j$$$ moves again to the same column. The total number of these moves is $$$2n+1-2j$$$.

A dynamic programming approach for computing the non-zigzag part of the path can use the symmetry of the grid. It can be observed that the foward part for the next column always starts from the other row after making exactly two moves: up/down and right. It can be proved that the total weight of the non-zigzag part starting at cell $$$(p,j)$$$, where $$$1 \leq p \leq 2$$$ and $$$1 \leq j \leq n$$$ can be expressed as follows, assuming that the other row index $$$1 \leq q \leq 2$$$ staisfies the equation $$$p+q = 3$$$:

$$$W(j) = (j-2)\sum\limits_{k = j}^{n} a_{p}[k] + (2n-1+j)\sum\limits_{k = j}^{n} a_{q}[k] + \sum\limits_{k = j}^{n} k~a_{p}[k] - \sum\limits_{k = j}^{n} k~a_{q}[k]$$$

As the starting cell of the tour is always $$$(1,1)$$$, there is only one valid non-zigzag path starting in the $$$j$$$-th column from cell $$$(p,j)$$$ and ending in the other cell of the column $$$(q,j)$$$, specified by

$$$p = 2 - (j \mod 2)$$$

$$$q = 1 + (j \mod 2)$$$

The other non-zigzag path starting from cell $$$(q,j)$$$ and ending in cell $$$(p,j)$$$ is invalid, because cell $$$(q,j)$$$ cannot be reached from cell $$$(1,1)$$$ during the zigzag part of the tour that visits all cells in the first $$$j-1$$$ columns.

In summary, the tour consists of two parts:

  1. $$$(2j-3)$$$-move zigazag part that visits all cells in the left-side $$$j-1$$$ columns when $$$j \geq 2$$$, and

  2. $$$(2n+1-2j)$$$-move non-zigag part that visits all cells in the right-side $$$n-j+1$$$ columns.

The transition from the zigzag part to the non-zigzag part when $$$j \geq 2$$$ is always made using a move to the right from cell $$$(p,j-1)$$$ to cell $$$(p,j)$$$.

The following is a simple C++17 implementation based on this observation.

76052896

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LIFE_GOES_ON (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried the problem. The above two answer do the job pretty well, their observations were good. However here I try to share my "Way of approach", as I hope it could be helpful.

Consider the state optimum(row, col) say, it stores the maximum gain if we start from cell(row, col) at time t = 0 and visit all the cells to the right of it as well as its own column (the region colored in blue). Let's call the blue region "block" and sum of rate of growth in the block as BlockSum (would be helpful later).

We realize that there is optimum substructure in the problem.

Consider a column, and choose a row (say the top row, row = 0): Now from there we have two options:

  • Either we go to the right, however this way we leave one cell untraversed in the same column. we must return to it. this means that the path would be like a spiral, let the gain associated with this be spiral(row, col).

  • Or we go to bottom cell, now from there we go to the right. however that is just the problem with state

opt(!row (= 1 in particular), col + 1) (row has values 0 or 1 in the problem), we can use it somehow.

We realize however that we cannot borrow directly from opt(!row, col + 1) since it stores the optimum if we were to start from there at t = 0, but we reach there at t = 2. Here is how we can derive a proper transition relation:

  • We know that opt(!row, col + 1) stores the optimum for path that starts from (!row, col + 1) and visits all the cell in it's block.
  • So, the path visits all cell. But now we reach cell (!row, col + 1) at time t = 2, so if we were to take the optimum path still, we would reach each cell in the block with delay = 2 seconds, this way every cell would contribute extra:

delay * rate(cell _i) = 2 * rate(cell_i)

So we get extra of

$$$\sum 2 * rate(cell_i) = 2 * \sum rate(cell_i) = 2 * BlockSum$$$

So, the transition relation for the second move becomes :

2 * BlockSum(!row, col + 1) + opt(!row, col + 1)

To wrap it all, opt(row, col) = max(spiral(row, col), 2 * BlockSum + opt(!row, col + 1))

One can also similarly compute spiral(row, col) from smaller values. I leave it to the you.

Now starting from right to left we can compare the two options for each cell. and compute the opt(0, 0).

Here is my submission of above idea 76065903