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.

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 $$$> 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

One easy idea on D. You BFS from (1, 1) to (N, M), and back from (N, M) to (1, 1) — and paint these cells. Any painted cell means that there exists a path through it. Then you check every diagonal line (up-right direction): how much painted cells does it contain. Minimum is an answer.

Try to place bulbs with indexes 2,4,6..2n in the line in order of decreasing di corresponding to each bulb.

You can initially construct a chain $$$n$$$ node.

Sort the distance from long to short.

Then for the distance $$$k$$$ :

For the $$$2i-1$$$ it takes the $$$i$$$_th vertice on the chain. Then we check if $$$i+k-1$$$:

If $$$i+k-1>n$$$ we create a new vertice on the chain, as we sorted it before, the vertice $$$i+k-2$$$ must be existed.

Otherwise it links to the vertice $$$i+k-1$$$ on the chain.

It's confusing!

sample inputs doesn't output minimum number!!

I think this might be the case:

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

Probably because you count useless cells?

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

It seems to me that this is an unpleasant working situation, which occasionally may well happen. It seems that there is no regular similar problem. (I want to thank MikeMirzayanov for beautiful Telegram and Google Translate platforms).

I just wanna see the data

Seems like it should work, you can submit now.

I had a completely different approach to the same condition — removing unicolored rows and columns. It doesn't allow bitsets, but I'll see if I can get it to pass.

maybe try increasing the percentage of mango next time

It's also the same as this problem (in Finnish), except that here $$$m$$$ was large and you had to output who works where, and in that problem you are given the number of workers and factories at every location. Furthermore, that problem is from a problemset of known educational problems we use here to practice for IOI, so I'm surprised this contests's organisers thought it was novel.

I see a submission using ternary search in F, why is it works?

60035603

Same here. Any idea how to pass it?

Well, to avoid hashing error, you could try the following way:

....*.

....*.

..#.*.

...?..

***.#.

Suppose we block the '?' cell, so obviously we should check there is a path from (1,1) to (n,m) that passes through one of '*' cells. Well, the remaining part is easy!

I can feel you :(

Same code + C++17 + pragmas = magic 60021780

let k,k1 be the number of dollars and euros used respectively. k1 must be a multiple of five and the answer will be the minimum of n-k1*e-k*d for given values of k1 and k, which you can get by running a loop on k1 and stopping when k1*e is bigger than n

The number of users who solved problem B and C is more than problem A.

So I think problem B and C is easier than A.

I tried use that and failed too...

Just use brute force:

int ans = n % d;
n -= 5 * e;
for (int i = 1;n >= 0;i++) {
	ans = min(ans, n % d); n -= 5 * e;
}

Another way could be to use dp. At any point we can choose b/w taking 'd' dollar or '5*e' euros. dp[i] represents the minimum money you'll end up with if you start from 'i'. for every multiple of d and every multiple of 5*e dp[i] will be zero. For every i<min(d,5*e) dp[i]=i and for i>min(d,5*e) you've dp[i] = min(dp[i-d],dp[i-(5*e)]). Ans will be dp[n]

that's the point

Results