ch_egor's blog

By ch_egor, 2 weeks 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 _kun_.

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
  • +81
  • Vote: I do not like it

»
2 weeks 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

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

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

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks 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".

          • »
            »
            »
            »
            »
            »
            2 weeks 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) :)

            • »
              »
              »
              »
              »
              »
              »
              2 weeks 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?)

»
2 weeks 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://codeforces.com/contest/1214/submission/59996918

Sorry for my poor English.

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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".

  • »
    »
    2 weeks 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://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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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)$$$.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really preferred to use dp in A...

»
2 weeks 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".

»
2 weeks 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.

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks 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.

    • »
      »
      »
      2 weeks 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

»
2 weeks 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?

  • »
    »
    2 weeks 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 :)

»
2 weeks 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

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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).

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 days 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.

            • »
              »
              »
              »
              »
              »
              »
              9 days 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

»
2 weeks 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://codeforces.com/contest/1214/submission/60144916

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that is exactly what the sample solution does?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They are completely two different ways to implement the same idea you could say.

»
2 weeks 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?

  • »
    »
    2 weeks 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)

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

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

My submission

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can A problem be solved in O(1)?

»
2 weeks 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."

»
2 weeks 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?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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

»
2 weeks 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

  • »
    »
    2 weeks 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)?

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

»
2 weeks 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