When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ch_egor's blog

By ch_egor, 5 years ago, translation, In English

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!

  1. jqdai0815
  2. gina0605
  3. never_giveup
  4. Radewoosh
  5. 244mhq
  6. cz_yixuanxu
  7. ko_osaga
  8. mango_lassi
  9. GoForIt
  10. ksun48

Editorial will be published soon.

UPD2: Editorial

  • Vote: I like it
  • +224
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Unusual Time.

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

Good

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Waiting for a nice problems!!

»
5 years ago, # |
  Vote: I like it +160 Vote: I do not like it

US participants be like

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is this contest like manthan?

»
5 years ago, # |
  Vote: I like it -57 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

This round is rated for div 2 ?

»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

is the round rated for everyone?

»
5 years ago, # |
  Vote: I like it +77 Vote: I do not like it

where is score distribution

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solve E is Enough :D, time for relaxing

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What is test case 16 in D?

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What was pretest 10 for F?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is pretest 12 in Problem D

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

what's in case 8 in D?

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How To Solve D...?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to avoid TLE in case 16?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This can overflow easily, right?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              I was watching your solution being judged, FeelsBadMan :/

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can You Elaborate regarding minCut ?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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
      ...#
      ....
      .#..
      .#..
      
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems quite overkill, but a cool idea!

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      did you mean The answer is 0 iff there is no path from (1, 1) to (n, m)?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

A was much harder than C

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can we find articulation point in directed graph?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, you have to make it undirected.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, we can use dominators tree.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check for both cases by blocking one by one.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +76 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can refer this code. 60043962

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem H "Thinking is very very easier than coding"

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Any hints for E???

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's confusing!

    sample inputs doesn't output minimum number!!

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 4   Vote: I like it +1 Vote: I do not like it

          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<<c,0;
          
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    I think this might be the case:

    4 4
    ..#.
    .###
    ....
    ....
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Probably because you count useless cells?

    4 4
    ...#
    ....
    .#..
    .#..
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ooops, that's the hack! Thanks

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        deleted

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

I think I saw Um_nik on scoreboard but cannot see him now, Why?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      What do you mean ?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +39 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +14 Vote: I do not like it

            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?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      ah man, that's some rick level shit

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • morty when is the next season coming morty
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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

solution? to G

Edit: 60020107 so seems to work

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    maybe try increasing the percentage of mango next time

»
5 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

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

    60035603

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

TLE on Test 189 of problem D, that hurt!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here. Any idea how to pass it?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like 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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like 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!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    wa126I can feel you :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +75 Vote: I do not like it

Please open the test cases...

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

How to solve problem A? Can someone please help.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right.

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 4   Vote: I like it +10 Vote: I do not like 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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks a ton! This is easiest to code.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is test 44 of problem D?

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;
    }
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It wont fit in TL since n ~ 1e8

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

»
5 years ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has someone link with results from official contest ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        Moreover, 1e9 + 11 isn't prime.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Lesson learnt: Always use 2 hashes.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My wrong on 20 even i did what u r saying

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same pblm...can't understand why?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      7 7 ....... ####..# ###..## ##..### #..#### ..##### .......

      Correct answer — 0.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain why my code for D fails for test 22.I used the code for articulation point.60033722

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    3 4
    ....
    ....
    .#..
    
»
5 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

A was harder than D

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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