### ch_egor's blog

By ch_egor, 3 years ago, translation,

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

• +224

| Write comment?
 » 3 years ago, # |   +62 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
•  » » 3 years ago, # ^ |   +41 We are not TC, so this thing won't happen :)
 » 3 years ago, # | ← Rev. 2 →   +3 Excellent time for Chinese participants! waiting for a good round.
 » 3 years ago, # |   +15 Unusual Time.
•  » » 3 years ago, # ^ |   +10 Hope it will give an unusual experience!
•  » » » 3 years ago, # ^ |   0 Of Course.
 » 3 years ago, # |   +59 I have rating $583$ before Codeforces Round $583$. See how much it will be after the round.
•  » » 3 years ago, # ^ |   +49 Maybe 584 for next contest
•  » » 3 years ago, # ^ | ← Rev. 2 →   +57 Obviously, (before Edu Round 72 div 2) you'll have a rating of $72/2 = 36$.
•  » » 3 years ago, # ^ |   0 Maybe you can get "+1" rating (Then your rating will be 1583) and you can become specialist.:)Good luck!
•  » » » 3 years ago, # ^ |   +3 You tried and that's all that matters
 » 3 years ago, # | ← Rev. 2 →   -31 Good
 » 3 years ago, # | ← Rev. 2 →   0 The problems in ( Div-1 & Div-2 ) combined contest are always interesting....
 » 3 years ago, # |   -6 Waiting for a nice problems!!
 » 3 years ago, # |   +160 US participants be like
•  » » 3 years ago, # ^ |   0 Really fact
 » 3 years ago, # |   0 is this contest like manthan?
 » 3 years ago, # |   -57 We are from China, everyone that i am fighting is fucking from China, china, china #Drdisrespect
•  » » 3 years ago, # ^ |   0 That is racist
 » 3 years ago, # |   +5 I believe that the main contest have problems go with subtasks. Will there be any mirror that we can gain points by solving subtasks?
 » 3 years ago, # |   -13 This round is rated for div 2 ?
•  » » 3 years ago, # ^ |   +8 Rated for both div 1 & div 2 .
 » 3 years ago, # |   -25 is the round rated for everyone?
•  » » 3 years ago, # ^ |   +18 Yes
 » 3 years ago, # |   +77 where is score distribution
•  » » 3 years ago, # ^ |   +6 It will be added later.
 » 3 years ago, # |   0 Solve E is Enough :D, time for relaxing
 » 3 years ago, # |   0 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.
 » 3 years ago, # |   +6 What is test case 16 in D?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 This didn't work for my solution: 4 4 .... ..#. #... .... The answer should be 2
•  » » » 3 years ago, # ^ |   0 yeah got it.
 » 3 years ago, # |   +4 What was pretest 10 for F?
 » 3 years ago, # |   +3 What is pretest 12 in Problem D
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I think this test is very similar to 12. 5 7 ....... ....... ..#.### ..#.... ..#....
 » 3 years ago, # |   +2 what's in case 8 in D?
 » 3 years ago, # |   +2 How To Solve D...?
•  » » 3 years ago, # ^ |   0 Basically we have to find cut vertex if I am not wrong . Answer can be 0,1,2
•  » » » 3 years ago, # ^ |   0 How to avoid TLE in case 16?
•  » » » » 3 years ago, # ^ |   +3 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
•  » » » » » 3 years ago, # ^ |   0 This can overflow easily, right?
•  » » » » » » 3 years ago, # ^ |   +3 Yeah .I forgot about that . WA on test case 175
•  » » » » » » » 3 years ago, # ^ |   +4 I was watching your solution being judged, FeelsBadMan :/
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 3 years ago, # ^ |   0 Can You Elaborate regarding minCut ?
•  » » » 3 years ago, # ^ |   +9 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?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +1 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)$.
•  » » » » » 3 years ago, # ^ |   0 Aaah, got it. Thanks mate!
•  » » » 3 years ago, # ^ |   +14 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: 4 4 ...# .... .#.. .#.. 
•  » » » 3 years ago, # ^ |   0 Seems quite overkill, but a cool idea!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » 3 years ago, # ^ |   +3 did you mean The answer is 0 iff there is no path from (1, 1) to (n, m)?
•  » » » » 3 years ago, # ^ |   +1 Oh yes, my mistake. Thanks for the correction)
•  » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ |   +14 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.
•  » » » 3 years ago, # ^ |   +3 can we solve D using concept of articulation point and bridges? Im getting TLE at 16th test case
•  » » » » 3 years ago, # ^ |   +1 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
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 3 years ago, # ^ |   0 can you share your code, i didn't get the complete intuition
•  » » » » 3 years ago, # ^ |   +1 http://codeforces.com/contest/1214/submission/60006023In the code I make the second path (B-path) greedily rightward but it's not necessary.pt() just prints the map for debug.
• »
»
»
»
»
3 years ago, # ^ |
Rev. 2   0

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

•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » 3 years ago, # ^ |   +1 60023871In 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.
 » 3 years ago, # |   +26 A was much harder than C
 » 3 years ago, # |   +1 How to check wheter blocking 1 cell is enough in D?
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +1 Can we find articulation point in directed graph?
•  » » » » 3 years ago, # ^ |   0 I wasn't able, but I was trying to consider all the edges bidirected. I recieved TLE 16.
•  » » » » 3 years ago, # ^ |   0 No, you have to make it undirected.
•  » » » » » 3 years ago, # ^ |   0 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?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 3 years ago, # ^ |   0 Yes, we can use dominators tree.
•  » » 3 years ago, # ^ |   0 check for both cases by blocking one by one.
•  » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ |   +23 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.
•  » » » 3 years ago, # ^ |   0 Can you please explain why this works? Or what's the intuition behind it?
•  » » » » 3 years ago, # ^ |   +2 Similar to this just that all the cells at same distance from (1, 1) form a diagonal.
•  » » » » » 3 years ago, # ^ |   +1 Thank you so much, Sir. This was a neat observation.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +76 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.
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » » 3 years ago, # ^ |   0 I have done exactly the same thing, yet I still get TLE :p
•  » » » » 3 years ago, # ^ |   0 You can refer this code. 60043962
•  » » 3 years ago, # ^ |   +8 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.
•  » » » 3 years ago, # ^ |   +5 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 -_-.
•  » » » » 3 years ago, # ^ |   0 Oh my god... I got passed by using 4 random modulos among the 7 I chose. You are so unlucky....
•  » » » » 3 years ago, # ^ |   0 I got the same result. I guess your modulos are 1e9+7 and 1e9+9.
•  » » » » » 3 years ago, # ^ |   +11 Yup, changing any mod to 1e9+11 gets accepted :(
•  » » » 3 years ago, # ^ |   0 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
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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
•  » » 3 years ago, # ^ |   +4 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.
 » 3 years ago, # |   0 Problem H "Thinking is very very easier than coding"
 » 3 years ago, # |   +8 Any hints for E???
•  » » 3 years ago, # ^ |   +9 Try to place bulbs with indexes 2,4,6..2n in the line in order of decreasing di corresponding to each bulb.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +5 Can someone explain me what exactly B was trying to ask?
•  » » 3 years ago, # ^ |   0 It's confusing!sample inputs doesn't output minimum number!!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I'll explain to you the second sample : 5 boys 3 girls5 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 .
•  » » » » 3 years ago, # ^ |   0 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!!
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   +1 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; cin >> b >> g >> n ; for(int i=0 ; i<=n ; x++,i++) { y=n-x; if(x<=b && y<=g) c++ ; } re cout<
 » 3 years ago, # |   +4 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +11 I think this might be the case: 4 4 ..#. .### .... .... 
•  » » 3 years ago, # ^ |   +26 Probably because you count useless cells? 4 4 ...# .... .#.. .#.. 
•  » » » 3 years ago, # ^ |   0 Ooops, that's the hack! Thanks
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » » 3 years ago, # ^ |   0 It works if you count number of cells in intersection, rather than in forward/backward sets separately.
•  » » » » » 3 years ago, # ^ |   0 Sorry that my explanation was not clear here. Yes, I mean to count only the cells reachable from both directions.
•  » » » » 3 years ago, # ^ |   +11 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.
 » 3 years ago, # |   +41 I think I saw Um_nik on scoreboard but cannot see him now, Why?
•  » » 3 years ago, # ^ |   -34 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).
•  » » » 3 years ago, # ^ |   +19 What do you mean ?
•  » » » » 3 years ago, # ^ |   +43 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 ?
•  » » » » » 3 years ago, # ^ |   +39 Lol.It means he knew some problems beforehand. Hence, he asked mike to remove him.
•  » » » » » » 3 years ago, # ^ |   +15 Not exactly, but on basic level that is what has happened, yes.
•  » » » » » » 3 years ago, # ^ |   +14 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?
•  » » » » » » » 3 years ago, # ^ |   0 rating police has arrived
•  » » » 3 years ago, # ^ |   +10 ah man, that's some rick level shit
•  » » » » 3 years ago, # ^ |   0 morty when is the next season coming morty
 » 3 years ago, # |   -9 when we can see the Editorial ????????????????????????
•  » » 3 years ago, # ^ |   +2 I just wanna see the data
 » 3 years ago, # | ← Rev. 2 →   +18 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, remove the bitset from the ordered list, and check if the bitsets on its either side form a valid pair modify the bitset. This can be done by just xor-ing it with precalculated bitsets with some prefix set to 1 re-add the bitset, then check if it forms a valid pair with the bitset on its left or the bitset on its right while the top entry of the valid pairs is not valid, pop the top entry if no entry is valid, output -1, otherwise find some valid rectangle from the top pair and output that 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. code#include #include #include #include #include using namespace std; const int M = 2000; const int N = 2000; bool works(const bitset& a, const bitset& b) { return abs((int)(a.count() - b.count())) < (a ^ b).count(); } pair get(const bitset& a, const bitset& b) { bitset x = a & (~b); bitset y = (~a) & b; return {x._Find_first(), y._Find_first()}; } bitset prefs[M+1]; bitset bts[N]; set> act; vector> valid; void remove(int i) { int cou = bts[i].count(); pair ap = {cou, i}; act.erase(ap); auto it = act.lower_bound(ap); int x = -1, y = -1; if (it != act.end()) x = (*it).second; if (it != act.begin()) { --it; y = (*it).second; } if (x != -1 && y != -1) { if (works(bts[x], bts[y])) valid.push_back({x, y}); } } void add(int i) { int cou = bts[i].count(); pair ap = {cou, i}; auto it = act.lower_bound(ap); if (it != act.end()) { int j = (*it).second; if (works(bts[i], bts[j])) valid.push_back({i, j}); } if (it != act.begin()) { --it; int j = (*it).second; if (works(bts[i], bts[j])) valid.push_back({i, j}); } act.insert(ap); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // n: number of bitsets // m: number of bits in each set int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= m; ++i) { prefs[i] = prefs[i-1]; prefs[i][i-1] = 1; } for (int i = 0; i < n; ++i) add(i); // Two bitstrings form a rectangle iff neither is a subset of the other // How to maintain whether this property holds? // Sort bitstrings by size. it is enough to compare back-to-back ones. for (int qi = 0; qi < q; ++qi) { int i, l, r; cin >> i >> l >> r; remove(i-1); bts[i-1] ^= prefs[r] ^ prefs[l-1]; add(i-1); bool found = false; while(!found && !valid.empty()) { int x1, x2; tie(x1, x2) = valid.back(); if (works(bts[x1], bts[x2])) { int y1, y2; tie(y1, y2) = get(bts[x1], bts[x2]); if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); found = true; cout << x1+1 << ' ' << y1+1 << ' ' << x2+1 << ' ' << y2+1 << '\n'; } else { valid.pop_back(); } } if (! found) cout << "-1\n"; } } Edit: 60020107 so seems to work
•  » » 3 years ago, # ^ |   +10 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.
•  » » 3 years ago, # ^ |   +3 maybe try increasing the percentage of mango next time
 » 3 years ago, # |   +70 The problem F was absolutely the same as 2006-2007 Summer Petrozavodsk Camp, Petr Mitrichev Contest 1 problem H.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » 3 years ago, # ^ |   0 so you have to solve it with min cost max matching? Could you detail the solution?
•  » » » » 3 years ago, # ^ |   +21 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +27 I see a submission using ternary search in F, why is it works?60035603
 » 3 years ago, # |   +19 TLE on Test 189 of problem D, that hurt!
•  » » 3 years ago, # ^ |   0 Same here. Any idea how to pass it?
•  » » » 3 years ago, # ^ |   +5 I was using a map to keep track of visited points, submitted just now using a vector for the same, and it got accepted.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 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!
•  » » 3 years ago, # ^ |   +4 I can feel you :(
•  » » 3 years ago, # ^ |   +3 Same code + C++17 + pragmas = magic 60021780
•  » » » 3 years ago, # ^ |   +3 It hurts even more now.
 » 3 years ago, # |   +75 Please open the test cases...
•  » » 3 years ago, # ^ |   +5 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
 » 3 years ago, # |   +2 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.)
 » 3 years ago, # |   0 Is It me only or problems B and C were easier than A?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +14 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.
•  » » » 3 years ago, # ^ |   0 You're right.Can you tell me how did you approach both A and D?
•  » » » » 3 years ago, # ^ |   +15 I use maxflow to solve D,but I think their have an easy way to solve it.
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   +10 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.
•  » » » » » » 3 years ago, # ^ |   0 Thanks a ton! This is easiest to code.
 » 3 years ago, # |   +5 What is test 44 of problem D?
 » 3 years ago, # |   +9 No tall, thin grids in pretests for D? Sad.... I guess I'm used to assuming n, m <= 1000
 » 3 years ago, # |   0 how to approach problem A? i used ans= min((n%d)%(5*e), (n%5*e)%d) and failed -_-
•  » » 3 years ago, # ^ |   0 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; } 
•  » » 3 years ago, # ^ |   0 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 imin(d,5*e) you've dp[i] = min(dp[i-d],dp[i-(5*e)]). Ans will be dp[n]
•  » » » 3 years ago, # ^ |   0 It wont fit in TL since n ~ 1e8
•  » » » » 3 years ago, # ^ |   0 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!
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 The TL is 1.5 sec not 2 sec. PS -: I tried it and got TLE. Look at 59986638
 » 3 years ago, # | ← Rev. 2 →   -30 Very weak pretests. In every single page of standing you can see several fails!
•  » » 3 years ago, # ^ |   +1 that's the point
 » 3 years ago, # |   +29 Why can't we see another's submission now ?
 » 3 years ago, # | ← Rev. 2 →   +32 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.
 » 3 years ago, # |   0 Has someone link with results from official contest ?
•  » » 3 years ago, # ^ |   +4
 » 3 years ago, # |   0 Problem D I got WA on test 224, someone pls tell me where I wrong
•  » » 3 years ago, # ^ |   0 You should use more than 1 prime number to hash the number of ways.
•  » » » 3 years ago, # ^ |   0 But I failed that test case for both prime numbers, so I don't think that's problem
•  » » » » 3 years ago, # ^ |   0 The probability that you will fail on both numbers at the same time is extremely low. Moreover, 1e9 + 11 isn't prime.
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 I got Accepted using only 1e9 + 7(During onsite). But I got WA122 with 998244353.
•  » » » » 3 years ago, # ^ |   0 I got WA224 with 1e9+7 on this round, wtf
 » 3 years ago, # |   -36 Congratulations to cerberus97 for having highest rating ever on Codeforces from India.
 » 3 years ago, # | ← Rev. 2 →   +8 Lesson learnt: Always use 2 hashes.
•  » » 3 years ago, # ^ |   +16 And they don't have to be 1e9+7 and 1e9+9 at the same time...
 » 3 years ago, # |   0 Can someone explain why my code fails for test 20 for D? https://codeforces.com/contest/1214/submission/60018456
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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)$.
•  » » » 3 years ago, # ^ |   0 My wrong on 20 even i did what u r saying
•  » » 3 years ago, # ^ |   0 Same pblm...can't understand why?
•  » » » 3 years ago, # ^ |   0 7 7 ....... ####..# ###..## ##..### #..#### ..##### ....... Correct answer — 0.
 » 3 years ago, # |   +13 Congrats on Emdadul_Islam who got submission #60000000 in this contest!
 » 3 years ago, # |   0 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?
 » 3 years ago, # |   +6 Can someone explain why my code for D fails for test 22.I used the code for articulation point.60033722
•  » » 3 years ago, # ^ |   0 Seem like you didn't exclude some unreachable cells in finding articulation point part. 3 4 .... .... .#.. 
•  » » » 3 years ago, # ^ |   0 Thanks this helped.
 » 3 years ago, # | ← Rev. 2 →   -14 A was harder than D
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +1 Step 1: Learn how to Google before asking questions. Step 2: Step 1 will likely have answered your question.
 » 3 years ago, # |   0 Would someone tell me how to solve F? Thank u.
•  » » 3 years ago, # ^ |   0 mango_lassi described it here.
•  » » » 3 years ago, # ^ |   0 Thank u!