Hi everybody!

These days Moscow is conducting the 4th International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Belgrade and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567).

Scientific Committee of the olympiad consists of: Chmel_Tolstiy, Jelena Hadži-Purić, Elena Andreeva, Zlobober, GlebsHP, andrewzta, meshanya.

The problems were developed by isaf27, cdkrot, manoprenko, GoToCoding, ch_egor, vintage_Vlad_Makeev, voidmax, grphil, malcolm under the guidance of GlebsHP and Zlobober.

Problems were adapted for codeforces by vintage_Vlad_Makeev and cdkrot, also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad. Also, thanks LHiC, voidmax and wrg0ababd for testing!

Good luck and high ratings for everybody!

Round will happen on Sep/04/2019 12:05 (Moscow time) and will last for two and half hours.

The round will consist of 8 problems and **will be combined** for both divisions. **The round is rated for all participants.**

**P.S.** We kindly ask everybody who knows problems of an onsite event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

**UPD1:** Winners!

Editorial will be published soon.

**UPD2:** Editorial

We kindly ask everybody who knows problems of an onsite event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.This round reminds me https://codeforces.com/blog/entry/65664

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

Excellent time for Chinese participants! waiting for a good round.

Unusual Time.

Hope it will give an unusual experience!

Of Course.

I have rating $$$583$$$ before Codeforces Round $$$583$$$. See how much it will be after the round.

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!

You tried and that's all that matters

Good

The problems in ( Div-1 & Div-2 ) combined contest are always interesting....

Waiting for a nice problems!!

US participants be like

Really fact

is this contest like manthan?

We are from China, everyone that i am fighting is fucking from China, china, china #Drdisrespect

That is racist

I believe that the main contest have problems go with subtasks. Will there be any mirror that we can gain points by solving subtasks?

This round is rated for div 2 ?

Rated for both div 1 & div 2 .

wish me luck I want to be master

Best of luck..Maybe some day..But not today

is the round rated for everyone?

Yes

where is score distribution

It will be added later.

Solve E is Enough :D, time for relaxing

Why did you have to include finding a solution in G? It's just more coding and more ways to make stupid mistakes without any more interesting ideas. Also, why such high constraints? Do you want heavily optimised $$$O((N+M)Q)$$$ to pass?

Apart from that, G is very nice! I realised that the condition we need to check is if it's possible to keep removing fully black/white columns until nothing remains — if we can't, there is a solution.

What is test case 16 in D?

This didn't work for my solution:

The answer should be 2

yeah got it.

What was pretest 10 for F?

What is pretest 12 in Problem D

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

what's in case 8 in D?

How To Solve D...?

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

How to avoid TLE in case 16?

If we are able to find a (i,j) such that

no of Ways to reach (i,j ) from (0,0) * no of ways to reach(i,j) from (n-1,m-1) == no of ways to reach (n-1,m-1) from (0,0)

then answer is 1

This can overflow easily, right?

Yeah .I forgot about that . WA on test case 175

I was watching your solution being judged, FeelsBadMan :/

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.

Can You Elaborate regarding minCut ?

I believe Max Flow algo's generally take a significant time, of order (N^2-3).I may be wrong. Could you please elaborate on how to apply Max Flow Algo?

the maximum flow can only be 2, so you only traverse the whole graph for 2 times. Therefore, it's time complexity is $$$\mathcal O(n\times m)$$$.

Aaah, got it. Thanks mate!

It seems that you need to connect an edge with 1 capacity between the same point, say

`u -> u`

, or you will fail on this testcase:Seems quite overkill, but a cool idea!

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

allof 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.

did you mean The answer is 0 iff there is

nopath from (1, 1) to (n, m)?Oh yes, my mistake. Thanks for the correction)

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.

can we solve D using concept of articulation point and bridges? Im getting TLE at 16th test case

You can make a undirected graph using edges that belog to at least 1 path from 1,1 to n, m, and them check if there exists articulation point, if it exists, answer is 1 else its 2

I did the same but got TLE, might be due to python

Does layers here directly correspond to the queue if we do a bfs from (1,1) to (n,m) ? If the queue contains only one element at some point of time then the answer is 1.

yes but only if at queue you have only cells that have same distance from (1, 1)

you can look at 60048095 where I implemented BFS using layers.

So, here basically we are using one queue for each level of layer and the layer is defined by i+j=w. Nice!

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.

can you share your code, i didn't get the complete intuition

http://codeforces.com/contest/1214/submission/60006023

In the code I make the second path (B-path) greedily rightward but it's not necessary.

pt() just prints the map for debug.

now i understood the solution. thanks for the code. and very nice solution

i did same thing but getting TLE can u tell me the reason?

60030230

## edit:: i think i got my problem,there is no need to backtrack!!

Your DFS has a problem, because you unmark cells when you exit a dead-end, they might get visited again. On a map like this your code will be super slow :

So either you leave cells marked like I do (and think about why it won't change the validity of the algorithm), or you make an extra boolean map keeping if each cell has been visited.

Thanks for your solution.

The intuition as others said is :

the answer is at most 2 because you could block (1,2) and (2,1)

it is 0 if you can't reach the treasure

it is 2 iff there is two disjoint paths from start to end

yeah, i have got first two. third i have got now

60023871

In my solution check pathes from (0,1) and (1,0)

After: I check that each diagonal have 2 diffirent ways for this pathes. I check diagonal because all points on diagonal points that we can reach by the same number of steps.

A was much harder than C

How to check wheter blocking 1 cell is enough in D?

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.

Can we find articulation point in directed graph?

I wasn't able, but I was trying to consider all the edges bidirected. I recieved TLE 16.

No, you have to make it undirected.

We can do so because of the fact that graph is acyclic, in other case we wouldnt be able to do so am i right?

I'm not sure why it would matter here. The definition of articulation point is based on the connectedness of undirected graph so it doesn't care about how you transform your directed graph. The only thing to take note here is we should exclude cells that are not connected to either top left or bottom right.

Yes, we can use dominators tree.

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.

Can you please explain why this works? Or what's the intuition behind it?

Similar to this just that all the cells at same distance from (1, 1) form a diagonal.

Thank you so much, Sir. This was a neat observation.

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 used the same solution, but I TLEd on test case 189. How did you precompute which squares had possible paths, and which didn't?

dp[i][j] = true iff u can reach (i,j) from cell (n,m); else dp[i][j] = false; U can easily calculate it in n*m. After this just greedy construct these 2 paths using this dp to check wheter you can go in direction you want.

I have done exactly the same thing, yet I still get TLE :p

You can refer this code. 60043962

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.

Sounds good, doesn't work. I had exactly the same solution with 2 different modulo for hashing, but it got WA on the test 224. OMG -_-.

Oh my god... I got passed by using 4 random modulos among the 7 I chose. You are so unlucky....

I got the same result. I guess your modulos are 1e9+7 and 1e9+9.

Yup, changing any mod to 1e9+11 gets accepted :(

I think you don't need to calculate number of ways. If exists way from (1,2) and (2,1) you can only check that all diagonals (same step) have different way for way1 and way2. If only one way exists result = 1, else result = 2. Solve after contest :) 60023871

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.Problem H "Thinking is very very easier than coding"

Any hints for E???

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.

Can someone explain me what exactly B was trying to ask?

It's confusing!

sample inputs doesn't output minimum number!!

I'll explain to you the second sample : 5 boys 3 girls

5 board games tournament participants. ===== I have n+1 decks of n badges as follows : 1: 0 5 //wrong because all the g girls is 3not5 ******** 2: 1 4 //wrong because all the g girls is 3not4 ******** 3: 2 3 //correct ******* 4: 3 2 //correct ****** 5: 4 1 //correct ****** 6: 5 0 //correct ******

Notice : I can have a number of blue badges is less than b Or number of red badges is less than g .

My answer got accepted which is: ~~~~~ FOR(i, n+1) { if (i <= b && n — i <= g) { ans++; } } ~~~~~ And this doesn't look for minimum, it checks for correctness!!

Exactly , I think word"minimum" is mentioned by mistake :( And this is my correct answer :

long long b , g , n , x=0,y=0, c=0;

,so it should be swapped with A :)

For problem D, I initially did sth like count the number of cells can be reached at every second and I believed the answer would be the smallest count of all instances except the starting and ending ones. However, it failed on pretest 12. Could anyone explain to me why this is wrong? Thanks.

I think this might be the case:

Probably because you count useless cells?

Ooops, that's the hack! Thanks

But can I fix this by go in the reverse direction (starting from the lower-right cell and moving only upwards and leftwards) after the first iteration? Then I count the number of cells in each distance in both ways?

deleted

It works if you count number of cells in intersection, rather than in forward/backward sets separately.

Sorry that my explanation was not clear here. Yes, I mean to count only the cells reachable from both directions.

You are correct, just got AC with it. I implemented this during contest but got WA because of using

`bool dp[n][m]={0}`

, I forgot that variable length arrays can't be initialized.I think I saw Um_nik on scoreboard but cannot see him now, Why?

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).

What do you mean ?

He mean he performed badly, but since he's an LGM he can message MikeMirzayanov and get away with it, I'm wondering what will happen if I asked that ?

Lol.

It means he knew some problems beforehand. Hence, he asked mike to remove him.

Not exactly, but on basic level that is what has happened, yes.

As far as I know, once you submit a problem the contest will be rated for you, can you tell me why it didn't apply in this case?

rating police has arrived

ah man, that's some rick level shit

when we can see the Editorial ????????????????????????

I just wanna see the data

I was late by half a minute to submit to G, I think I had a valid solution :(

solution? to GConsider the rows as bitstrings. We can find a rectangle of the desired type between two rows $$$i$$$ and $$$j$$$ iff neither of them is a subset of the other. So the problem is essentially asking us to maintain whether any of the $$$n$$$ bitstrings is a subset of another.

To do this, we maintain the bitstrings in sorted order by number of set bits. If we have $$$B_{i} \subset B_{i+1}$$$ for all $$$i$$$, then $$$B_{i} \subset B_{i+1} \subset \dots \subset B_{j}$$$ for all $$$i, j$$$ and no solution can exist. Therefore it is enough to maintain which adjacent bitsets work. To do this, we make a function to check whether two bitsets are subsets of eachother in time $$$O(\frac{m}{64})$$$, by just checking whether their xor equals the difference of their sizes. We also maintain which adjacent bitstrings are not subsets of eachother.

To make a query,

Step $$$1$$$ involves one bitset check and one set-operation in $$$O(\frac{m}{64} + \log n)$$$ time. Step two involves two bitset operations in time $$$O(\frac{m}{64})$$$. Step three involves two bitset operations and three set-operations (lower_bound, decrementing iterator and insertion) in $$$O(\frac{m}{64} + \log n)$$$ time. Step 4 takes amortized $$$O(\frac{m}{64})$$$ time, since every query we add at most 3 entries to the list of valid pairs. Step 5 can be done in time $$$O(\frac{m}{64})$$$ by taking any $$$1$$$ from $$$B_{i}$$$ & (~$$$B_{j}$$$) and any $$$1$$$ from (~$$$B_{i}$$$) & $$$B_{j}$$$. Therefore the total runtime is $$$O((n + m + q) (\frac{m}{64} + \log n))$$$, which should fit in the time limit of three seconds.

codeEdit: 60020107 so seems to work

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

The problem F was absolutely the same as 2006-2007 Summer Petrozavodsk Camp, Petr Mitrichev Contest 1 problem H.

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.

so you have to solve it with min cost max matching? Could you detail the solution?

So the translated problem statement of that problem is:

There are $$$n \leq 10^{5}$$$ children in a circle, initially the $$$i$$$'th has $$$k_{i} \leq 10^{9}$$$ candies. At every second, one child gives one candy to either of the children sitting next to them. At least how much time must pass so that all children have the same amount of candies?

So if there are $$$nm$$$ candies in total, then if $$$k_{i} < m$$$ we can say there are $$$m - k_{i}$$$ factories at position $$$i$$$, and otherwise there are $$$k_{i} - m$$$ workers at position $$$i$$$.

To solve both problems, let $$$w_{i}$$$ be the amount of workers at position $$$i$$$, and $$$f_{i}$$$ the amount of factories respectively. If no worker travels between cities $$$1$$$ and $$$m$$$, the total cost is $$$cost(0) = \sum_{i = 1}^{m} \left|\sum_{j = 1}^{i-1} w_{j} - f_{j}\right|$$$ (the sum of absolute values of prefixes), since exactly $$$\left|\sum_{j = 1}^{i-1} w_{j} - f_{j} \right|$$$ workers have to travel between cities $$$i$$$ and $$$i-1$$$ on their way to work.

Let $$$c$$$ denote the number of workers who travel from city $$$m$$$ to $$$1$$$, where $$$c$$$ is negative if $$$|c|$$$ workers travel from $$$1$$$ to $$$m$$$. Then the total cost will be $$$cost(c) = \sum_{i = 1}^{m} \left|c + \sum_{j = 1}^{i-1} v_{j}\right|$$$ with the same argument as before. But defining $$$v_{i} = \sum_{j = 1}^{i-1} w_{i} - f_{i}$$$, we get $$$cost(c) = \sum_{i = 1}^{m} \left| c + v_{i}\right|$$$, which is easy to minimise with the sweeping line technique.

To apply sweeping line, notice that the term $$$\left|c + v_{i}\right|$$$ contributes $$$1$$$ to $$$cost(c+1) - cost(c)$$$ if $$$c \geq -v_{i}$$$, and $$$-1$$$ otherwise. Therefore the gradient changes only at $$$m$$$ positions, and we can loop until $$$cost(c+1) - cost(c) > 0$$$.

Once you know the optimal $$$c$$$, it is easy to find the optimal pairing of workers and factories. Having large $$$m$$$ just adds weights to the absolute values corresponding to the distance between cities $$$i$$$ and $$$j$$$. So the reduction from that problem to the one in this contest doesn't show any difficulties.

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

60035603

TLE on Test 189 of problem D, that hurt!

Same here. Any idea how to pass it?

I was using a map to keep track of visited points, submitted just now using a vector for the same, and it got accepted.

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

It hurts even more now.

Please open the test cases...

How to solve problem A? Can someone please help.

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 problem in this round is good,but the pretest is not strong.

Some my classmates read the wrong problem of D,they think that's cut the edge,not cut the points,but they passed the pretest.

Why many div1+div2 rounds is hackforces(Codeforces Global Round 1,2,3 is hackforces,too.)

Is It me only or problems B and C were easier than A?

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.

You're right.

Can you tell me how did you approach both A and D?

I use maxflow to solve D,but I think their have an easy way to solve it.

I solved it later on using DFS. I'm not certain if there's a way to hack it, though.

You can run a DFS and stop once you reach the destination. Then you mark the start and end points as unvisited and run the DFS for the second time. If now you weren't able to reach the destination node, that means that there was a single path to the end point that was blocked, so the answer is 1. If you could still reach the destination node, that means there are more than 1 possible paths from start to end, so you must block both.

If you couldn't reach the destination node from the start (first DFS), then the answer is 0.

Thanks a ton! This is easiest to code.

What is test 44 of problem D?

No tall, thin grids in pretests for D? Sad.... I guess I'm used to assuming n, m <= 1000

how to approach problem A? i used ans= min((n%d)%(5*e), (n%5*e)%d) and failed -_-

I tried use that and failed too...

Just use brute force:

Basically you want to find x and y such that

`(n - x*d - y*(5*e))`

isminimum.What you do is brute force x (with the possible set of bills given, you can have any amount since you can take unlimited bills) and calculate the maximum amount of euros you can buy with what's left:

`n - x*d`

.Something like this:

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]

Wow, nice solution, cool way of thinking.

It wont fit in TL since n ~ 1e8

It'll fit coz anyhow you'll loop till n~1e8 and globally you can declare array of size ~1e8. So, yeah it'll pass!

The TL is 1.5 sec not 2 sec. PS -: I tried it and got TLE. Look at 59986638

You didn't did it right! See here

Very weak pretests. In every single page of standing you can see several fails!

that's the point

Why can't we see another's submission now ?

Crappy English in statements. In problem B where was it mentioned that you could take take some decks but when distributing badges, you only have to distribute from a single deck? I wasted 45 minutes figuring out on this, and later just assumed it to be that way got Accepted. Also the word "minimum" was missing before but I could not complain much about that because it was somewhat clear from the sample test cases.

Has someone link with results from official contest ?

Results

Problem D I got WA on test 224, someone pls tell me where I wrong

You should use more than 1 prime number to hash the number of ways.

But I failed that test case for both prime numbers, so I don't think that's problem

The probability that you will fail on both numbers at the same time is extremely low.

Moreover, 1e9 + 11 isn't prime.

If it's just the modulo, that doesn't have to be prime. Hashes modulo several numbers are equivalent to the hash modulo their LCM (because CRT). That shouldn't be a problem.

I got Accepted using only 1e9 + 7(During onsite). But I got WA122 with 998244353.

I got WA224 with 1e9+7 on this round, wtf

Congratulations to cerberus97 for having highest rating ever on Codeforces from India.

Lesson learnt: Always use 2 hashes.

And they don't have to be 1e9+7 and 1e9+9 at the same time...

Can someone explain why my code fails for test 20 for D? https://codeforces.com/contest/1214/submission/60018456

Vasya got off the ship in cell $$$(1,1)$$$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $$$(x,y)$$$ he can move ONLY to cells $$$(x+1,y)$$$ and $$$(x,y+1)$$$.

My wrong on 20 even i did what u r saying

Same pblm...can't understand why?

Correct answer — 0.

Congrats on Emdadul_Islam who got submission #60000000 in this contest!

Why so strict limit for problem

D? It is 1000 ms for 1 million chars input.I tried with Perl, but got TLE, and after contest I found only one solution with Python (PyPy3 996 ms). Was problem

adopted for Codeforces? Why not to limit by 2s or 4s? Or any bad solutions with C++ could pass?Can someone explain why my code for D fails for test 22.I used the code for articulation point.60033722

Seem like you didn't exclude some unreachable cells in finding articulation point part.

Thanks this helped.

A was harder than D

One of the best D. :p. A was so hard , harder than D

I'm a newbie, how to good at Competitive Programming and algorithms and Data Structures, I don't know where I have to start, please guide me.

Step 1: Learn how to Google before asking questions. Step 2: Step 1 will likely have answered your question.

Would someone tell me how to solve F? Thank u.

mango_lassi described it here.

Thank u!