ch_egor's blog

Editorial of Codeforces Round #583 (based on Olympiad of Metropolises)
By ch_egor, 5 years ago, In English

Thanks for the participation!

1214A - Optimal Currency Exchange was authored and prepared by Helen Andreeva.

1214B - Badges was authored by jury and prepared by Chmel_Tolstiy.

1214C - Bad Sequence was authored by meshanya and prepared by GoToCoding.

1214D - Treasure Island was authored by meshanya and prepared by malcolm.

1214E - Petya and Construction Set was authored and prepared by voidmax.

1214F - Employment was authored and prepared by grphil.

1214G - Feeling Good was authored and prepared by isaf27.

1214H - Tiles Placement was authored and prepared by cdkrot.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +84
  • Vote: I do not like it

Comments Comments (60)
| Write comment?
»
5 years ago, # |
← Rev. 6   Vote: I like it +10 Vote: I do not like it

Alternative solution for D: Treasure Island if you're using a language where sets and tuples can be expensive (e.g. JVM), is to simply convert the grid to a 2D character array. Then you can iterate through the array twice, once in forward order, once in backward order. The first time, you mark $$$(1, 1)$$$ with e.g. a '0' character, and "spread" the '0' characters over the '.' characters. The second time, you do the same from the goal backward, except changing from '0' to '1'. Now the '1' characters represent the intersection of the two sets of accessibility.

It's basically a BFS/DFS variant that isn't actually either, but rather "reading-order first", taking advantage of the fact that successors always come later in reading order.

Sample code in Kotlin: #60063170

Problems like this and #1195E OpenStreetMap really makes me wish Project Valhalla was out already. Either that or it's time for me to learn another language :P

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

    I think your solution of D is same as the editorial solution

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

      It's the same basic idea, and represents the same things set-theoretically, but the implementation details (using arrays rather than hash-sets, stacks/queues, and tuples) make all the difference speed-wise.

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

        The editorial never said that it had used sets, stacks/queues, tuples :(

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

          It's implied by the suggestion to use DFS. To properly implement DFS, you need a stack (or a queue for BFS), and the most natural way to store the vertices (i.e. grid positions) is with tuples. My posted solution isn't a proper DFS nor a BFS; it takes advantage of the property for successors to always be later in "reading order".

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

            I don't know about everyone but if I want to run a dfs on this kind of grid, I will simply make a recursive call from cell(1, 1) and backward from cell(n, m) :)

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

              That's technically also a stack, except you're using the call stack rather than an explicit object. :P Which also may cause problems in the JVM due to small default call-stack size. (StackOverflowException anyone?)

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

An easier solution for D:

You just need to run a maxflow.

My code: https://mirror.codeforces.com/contest/1214/submission/59996918

Sorry for my poor English.

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

    Sorry for my poor English.

    Might as well put that in the comment template.

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

    Apologies, but I wouldn't call a max-flow solution "an easier one".

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

    You can implement Ford-Fulkerson implicitly in a simple way since all edges have infinite capacity and all nodes have 0/1 capacity: https://mirror.codeforces.com/contest/1214/submission/60080823.

    The find() function is called at most three times due to the observation that the min cut / max flow is at most 2.

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

    I think if you don't converting a Plane Graph into a Dual Graph and use Dijkstra,the complexity of the algorithm is not right.

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

      The flow is at most 2, so the complexity of Dinic is $$$\mathrm O(n+m)$$$.

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

    Can you please explain why you made edges with capacity 1/0 for nodes which are empty/forests. I thought just joining edges between nodes which have a path available with capacity 1, but then that is giving WA on tc 44.

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

A really simple solution for D: just run a dfs and check if the destination is reachable and mark all nodes you saw. For every path you find like this you can increase the result by one. 60075870

This solution works since the corresponding graph is planar, the start and destination both lie on the outer face, and the dfs is in fact a so called "right-first-dfs".

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

D can actually be easily solved using Dinic's algorithm in O(N*M). At first, it's clear that max flow from (1, 1) to (n, m) will be the answer, as max flow equals min cut, which is exactly what we need to find in the problem. Now, here's why Dinicz will find max flow in this graph in O(N*M). All the edges' capacity is 1, so one faze of the algorithm will work in O(M), where M is the amount of edges in the graph. The other thing is that Dinicz will stop after the first faze. Each faze lengthens the shortest path from S to T int the net, meanwhile in this one all the paths are the shortest.

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

    But that's hard to code unless you already have existing code for it. But its quite overkill imo

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

      Yeah it is. I didn't actually code it on the contest, just thought about it afterwords. This problem can really help understanding flows and Dinic's algorithm better though.

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

      Not overkill if you copy+paste and code the rest in 5 minutes

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

Was ternary search by the position of the pair of the first element in F an intended solution?

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

    Normal ternary search is just not correct. For example on test:

    10 20
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5
10 10 10 10 10 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4

    Solution 60008635 (AC on round) don't work. Because a lot of offsets give the same value, and this value is not optimal.

    However there are some other implementations, for example 60002491. There the search is for the number of people crossing 0=M bound, And for some values it calculates not the optimal score, but smth larger. And I'm curious how to challenge it :)

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

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

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

    Consider function $$$f(x)=\sum_{i=1}^{n}|a_i-x|$$$ , it's easy to see that $$$f(x)$$$ is a lower convex function.

    So the function $$$g(x)=\sum_{i=1}^{n}|a_i-b_{i+x}|$$$ is similar to $$$f(x)$$$ if $$$a,b$$$ are non-decreasing.

    And it's easy to transform the original problem to this : find the minimal value of $$$g(x)$$$ $$$(-n\leqslant x \leqslant n)$$$.

    Sorry for my poor English.

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

      I am sorry that I can't fully understand what's the meaning of f(x) and g(x).

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

        Consider a greedy mathods:

        transform $$$a_i$$$ to $$$a_i+m$$$, and $$$b_i$$$ to $$$b_1,b_2,\cdots ,b_n,b_{n+1}+m,\cdots, b_{2n}+m,b_{2n+1}+2m,\cdots,b_{3n}+2m$$$, after that the length of $$$b$$$ is $$$3n$$$.

        then let $$$g(x)=\sum_{i=1}^{n}|a_i-b_{i+x}|(0\leqslant x\leqslant 2n-1)$$$.

        it is a lower convex function because it's made up of $$$2n$$$ points in $$$f(x)$$$ from left to right.

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

          This time I understand, and why this greedy method works?

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

            this is the same as the official editorial, maybe you can check it out.

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

              Sorry, I find it's really hard to understand why this method it the same as the official editorial

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

An alternative solution for D:: Use top down or bottom up approach to find the points (r,c) which can access (n,m) => those points which can traverse freely to (n,m). At this point we do not care where to create blockages.

Then observe that if we block any of the diagonal (0,0) gets cut off from (n,m). We use this fact and the information we extracted earlier to find the ans. Then use BFS from (0,0). Create a diagonal list say dp[]. As we are traversing each element, if the element (x,y) can access (n,m) we add 1 to dp[x+y].

Then we recur over this dp and find its minimum. That is the answer. https://mirror.codeforces.com/contest/1214/submission/60144916

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

    that is exactly what the sample solution does?

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

For the problem 1214D - Treasure Island, I'm getting a TLE on test 19 — 60144500. Can somebody please help me identify the error?

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

    there are many things you should change (but the tle is probably due to huge constant factors...):

    try to avoid a set if it will contain 10^6 elements (which can happen if I understand your code correct). 10^6 elements in a set are really much...

    don't use new and delete in competitive programming. Use a vector and let it do the allocations. (this makes writing code much simpler)

    don't use pointers. Use references. (again this makes things for competitive programming easier to write and we almost never need pointers)

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

A can be solved in O(dlog(d))

My submission

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

Can A problem be solved in O(1)?

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

I problem D what is the meaning of this statement "f answer is one, there must exist such cell (x,y) that each path from (1,1) to (n,m) goes through that cell. Also we can notice that in each path the cell (x,y) goes on the (x+y−1)th place."

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

Isn't the pic from the H editorial incorrect? There is a path 1->2->1 on the left of the diametr. Overall the editorial isn't clear. When we repeat the algorithm recursively, do we proccess it on each subtree coming out of the diametr?

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

    This picture only illustrates the method of coloring...

    It's clear from the first statement that the answer is impossible for this case.

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

      Yeah it is I just don't get why would they use the wrong pic

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

Yet another solution to problem D — no graph algorithms required! Precompute $$$d_{i,j}$$$ — whether $$$(i,j)$$$ is reachable from $$$(1, 1)$$$. Now, greedily find two paths from $$$(n,m)$$$ to $$$(1,1)$$$, one where you prioritize moving along the x-axis, and another one where you prioritize moving along the y-axis. If these two paths intersect somewhere other than in $$$(1, 1)$$$ or $$$(n, m)$$$, you can block that cell and the answer is $$$1$$$, otherwise it's $$$2$$$.

Code: 60184416

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

    Nice solution!
    But why does it work?
    Can you please prove it (just the greedy part)?

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

      Proof by AC :)

      Just kidding, one direction is obvious, if this algorithm finds two disjoint paths, then clearly the solution is 2.

      The other part is not so obvious. It's enough to show that if the two greedy paths intersect, then every valid path has to pass through these intersection vertices. This is exactly the definition of a blocking vertex.

      I will show that all valid paths lie between the lowest and the highest path. Assume the contrary — some part of a valid path "sticks out", say, it sticks out below the lowest path. We can use this part which sticks out to find an even lower path, meaning that our original lowest path was wrong, a contradiction.

      This means that every path has to pass through every intersection vertex, because that's the only vertex between the two paths.

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

        Thanks a lot!
        Well, I find this solution the easiest to understand among all others.

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

For D, I have written a code which similar to "Permeability of soil" problem.

But I am getting WA. Can someone help me with it? 60012934

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

I have been trying to pass problem D with the following approach: Check if there is not a path between (0,0) and (n-1, m-1), then the answer is 0. Check if there is not a path between (0,0) and (n-1, m-1) without using articulation points, then the answer is 1. Otherwise the answer is 2. Submission: https://mirror.codeforces.com/contest/1214/submission/61191311

I can't figure out my mistake on code,can anyone help me?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Simple test
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      My code is actually giving the correct answer for this test case. Thank you.

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

        I'm sorry I forgot to say that I consider the edges in both ways when checking if there is a path between (0,0) and (n-1, m-1) without using articulation points.

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

        Are you sure? https://ideone.com/gc6HOQ

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

          I have tried with http://mirror.codeforces.com/contest/1214/customtest and C++ 17 and then i'm getting the correct answer which is 2.

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

            Maybe you somehow changed the code during testing? I get 1.

            Try this test too
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I tried it and my code outputs 2 for this test case. I have done the test using the custom invocation and c++ 17

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

                You are correct. My code and my solution are incorrect. Here is another test case in the same "style" as your test case: 5 5 ..... .#.#. .#.#. .###. .....

                I think that the problem with my solution is that i'm taking into consideration the entire graph, but to use this solution i should take into consideration only the graph with the paths between (0,0) and (n-1,m-1). Thank you very much.

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

Can anyone explain me B question. I can't understand the test case

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

    for 1st test case:-
    Boys-5(b),
    Girls-6(g),
    participants-3.
    Possibilities of participants:-
    1. 0b,3g
    2. 1b,2g
    3. 2b,1g
    4. 3b,0g
    so answer is 4

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

An alternate solution for problem D, Just block any whole path from ({1,1}->{n,m}) and if afterblocking all cells of that path you can reach target from source then answer can never be 1 it must be 2.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

251146527

My code is giving wrong answer for test case 11 and I can't figure out why. Please explain the error. I would highly appreciate the help. Also if my code is not understandable please let me know I will explain it.

→ Reply