LIFE_GOES_ON's blog

By LIFE_GOES_ON, history, 4 years 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

| Write comment?
»
4 years 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...

»
4 years 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