Вообще плохо, что люди пишут мусорные комментарии на CF. Но ты держи всех в курсе, может еще что-то поменяется и ты успеешь на раунд.

Если ты из Москвы, то да, а есть те, для кого слишком поздно в 17:35 по МСК.

We are not TC, so this thing won't happen :)

Hope it will give an unusual experience!

Maybe 584 for next contest

Obviously, (before Edu Round 72 div 2) you'll have a rating of $$$72/2 = 36$$$.

Maybe you can get "+1" rating (Then your rating will be 1583) and you can become specialist.:)

Good luck!

Really fact

That is racist

Rated for both div 1 & div 2 .

Yes

It will be added later.

I want to thank MikeMirzayanov for beautiful Codeforces and Polygon platforms, and cdkrot for coordination of this round.

Я понял, что задачи слишком сложные, у меня не получится выиграть и я солью рейтинг. Рейтинг — самое важное в моей жизни, поэтому я встал на колени и умолял Майка перевести меня во внеконкурсное участие. Великий Майк, храни его Господь, согласился.

Я опубликовал скринкаст, на нем можно видеть как я просматриваю задачи и осознаю, что у меня нет шансов.

Выяснилось, что Um_nik встречался с одной из задач во время тестирования другой олимпиады. Как я понимаю туда эту задачу не взяли, а на олимпиаду мегаполисов — взяли. И я и cdkrot извинились, когда узнали о ситуации. Я бы на месте участника просто порешал раунд внеконкурсно без этой задачи, есть же еще 7 других задач.

This didn't work for my solution:

4 4
....
..#.
#...
....

The answer should be 2

I think this test is very similar to 12. 5 7 ....... ....... ..#.### ..#.... ..#....

Basically we have to find cut vertex if I am not wrong . Answer can be 0,1,2

You can solve it by maxFlow algorithm — you actually need minCut (same as maxFlow) from cell ($$$1,1$$$) to cell ($$$n, m$$$).

EDIT : I had wrong implementation, but idea is correct.

The insight is that there are only 3 possible answers: 0, 1, 2.

The answer is 0 iff there is no path from (1, 1) to (n, m);

As for the case when the answer is 1, the reasoning is as follows. Let's denote the set of valid paths from (1, 1) to (n, m) as P. It's obvious that the length of these paths is (n + m — 2). Let's say that, the kth step in all of these paths is the same. Then we can block this square and, by doing that, we guarantee that no paths remain. It's easy to see that the set of squares visited on the kth step satisfies the equation i + j = k (0-based notation). So we can simply set an array counting the number of such squares visited in the code for dfs. We include one more dfs to check, for every square, whether (n, m) is reachable from it. In this way we do not count "useless" squares which would not contribute to any path.

In all other cases the answer is 2.

My approach was, do a dfs mark all the cells which come path from 1,1 to n, m. Then we group marked cells on basis of there distance from 1, 1. If any group has only one cell answer is 1 other wise 2. Got runtime error so don't know for sure but looks like solution to me.

Solution for Problem D:

Let's call cell good if cell (n, m) is reachable from it. Now if cell (1, 1) isn't good then answer is obviously 0.

Now let's delete every not good cell from graph. Let's consider every path from (1, 1) to some (i, j), we can easily see that every path have same length.

Now we can think about graph, as graph made of layers. In layer number X, are all cells that distance from (1, 1) to it is equal to X.

We know that every path from (1,1) to (n, m) must go through at least one vertex in each layer. We know that layer number 0 contains only cell (0, 0) and last layer contains only cell (n, m), so if we look at all others layers and at least one of them contains only one cell, then we know that every path from (1, 1) to (n, m) must go through that cell, and answer is 1.

All of this can be done by two bfs's. Bfs on reverse graph to delete not good cells and second one to check if there is a layer with size equal to 1.

Simple solution :

I did two DFS, the first to find a path going greedily downwards before rightward, and marking the cells with 'A'. If there is no A-path the answer is 0 Then try to find another path that does not use the 'A' cells, if there is one the answer is 2, else it's 1.

If there is any articulation point in the graph of all the vertices that reach the cell NxM, starting from 1x1, the answer is 1.

check for both cases by blocking one by one.

If we block cell (i,j) Then cells with row = i & col > j should have paths originating only from (i,j) and same for cells with col = j & row > i. Use some precalculation and cumulative sums.

Let x = number of paths from (1, 1) to (i,j) and y = from (i, j) to (n, m). Then, it suffices to check if there exists some cell(i, j) such that x*y = Number of paths from (1, 1) to (n, m). It can be checked mod prime with some randomization to prevent hacks.

If you can only reach one cell in the diagonal defined by cells having same sum of (i + j) then after blocking that cell you can't reach the corner.

First, ignore all cells through which there is no path from (1, 1) or no path to (n, m). Then do a bfs on this new grid. If at any point the queue size is 1 and the element in the queue is not (1, 1) or (n, m), then this cell can be blocked. The same idea works for any general graph.

I checked for it during BFS,when queue size was exactly 1, and it didn't have points of start and end, but i didn't push useless cells in queue.

I've created two paths, one trying to go right whenever possible and one trying to go down. If those two paths intersect that intersection should be necessary and answer is 1.

I have another way to find the blocking cell:

Denote $$$f(i_1, j_1, i_2, j_2)$$$ as the number of ways to go from $$$(i_1, j_1)$$$ to $$$(i_2, j_2)$$$. A cell $$$(i, j)$$$ is a blocking cell if and only if $$$f(1, 1, i, j) * f(i, j, n, m) = f(1, 1, n, m)$$$

We can calculate the required terms using DP. The number of ways can be large so we need to use some hashing.

Build the directed graph $$$G$$$, represent cell $$$(1,1)$$$ as node $$$0$$$ and cell $$$(n, m)$$$ as node $$$nm-1$$$ in $$$G$$$. Now we need to check if the min number of nodes needed to delete in order to disconnect $$$0$$$ and $$$nm-1$$$, which is essentially max flow with node capacities $$$1$$$, is 1 or not. Make another graph $$$G^t$$$ consisting of two nodes $$$I_u$$$ and $$$O_u$$$ for each node $$$u$$$ in $$$G$$$. Add edge $$$I_u \rightarrow O_u$$$ for all $$$u$$$. Also for every edge $$$u \rightarrow v$$$ in $$$G$$$, add edge $$$O_u \rightarrow I_v$$$ in $$$G^t$$$. All edge capacities are $$$1$$$. Now, we just need to check if the max flow from $$$S = O_0$$$ to $$$T = I_{nm-1}$$$ in $$$G^t$$$ is $$$ \gt 1$$$ or not. Take a simple path from $$$S$$$ to $$$T$$$, if none exists, print $$$0$$$, otherwise, reverse the direction of every edge of that path. Now, try to go from $$$S$$$ to $$$T$$$ again, if it's possible, then max flow is $$$\ge 2$$$ (more precisely, exactly $$$2$$$ in this problem), print $$$2$$$, otherwise, max flow is $$$1$$$. To see why it is what it is, this is essentially the first two steps of Ford Fulkerson's algorithm. Code. Credit goes to Bruteforceman