doreshnikov's blog

By doreshnikov, history, 3 years ago, In English

Short information

Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.

About problem F:

I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.

I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!

The editorial

1607A - Linear Keyboard

Idea: doreshnikov, MikeMirzayanov

Tutorial
Solution

1607B - Odd Grasshopper

Idea: doreshnikov

Tutorial
Solution

1607C - Minimum Extraction

Idea: doreshnikov

Tutorial
Solution

1607D - Blue-Red Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1607E - Robot on the Board 1

Idea: MikeMirzayanov

Tutorial
Solution

1607F - Robot on the Board 2

Idea: doreshnikov

Tutorial
Solution

1607G - Banquet Preparations 1

Idea: doreshnikov

Tutorial
Solution

1607H - Banquet Preparations 2

Idea: MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +122
  • Vote: I do not like it

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

Thanks for an amazing round !

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

Correct me if I'm wrong but I believe there's a typo in the editorial to problem B. It says "coordinate −1 is even, jumping right to 2 leads to 2", when jumping right 2 from -1 should be 1 (2-1 = 1).

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

    The 2nd and 3rd statements should have been like this:

    2.coordinate −1 is odd, jumping right to 2 leads to 1

    3.coordinate 1 is odd, jumping right to 3 leads to 4

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

    Sorry, that's a typo, fixed

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

Thank you for fastn't editorial.

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

I finally know why so many people I know can't solve problem F.

But I get TLE because I forgot to push a tag XD.

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

doreshnikov Can you explain the following line in the editorial with an example for problem : Robot on the Board 1?

Since the robot breaks as soon as goes outside the field, if any command causes it to break, it either leads to its total shift relative to (r, c) of exactly c to the left or exactly m — c + 1 to the right, or, similarly, of exactly r up or exactly n — r + 1 down.

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

    If there's a moment in time when the robot moves to the left exactly c times more than to the right, it will fall off the left edge of the board. And the similar statements for each other direction.

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

can anyone share accepted java solution for problem C. mine is https://codeforces.me/contest/1607/submission/134305901 giving TLE

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

For the case n=10 and x0=10 in problem B, where x0 is the starting point and n is total number of steps, how the output is 11? From what I understood from the problem statement, I was getting 15.

10-1+2-3+4...+10 -> 15

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

    The correct sequence is 10-1+2+3-4-5+6...

    • 10 — even, then -1
    • 9 — odd, then +2
    • 11 — odd, then +3
    • ...
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why in problem F the solution with dfs gives MLE?

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

    Don't you see the reason in the post?Authors didn't suppose that participants will use DFS for solving this problem...

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

      No, I saw. I'm just wondering why the solution crashes and how I can optimize my dfs

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

        I'm kinda scared answering to such questions since my comments on the topic tend to get highly disliked (though, maybe, it's deserved in some way, I feel some people are just still unhappy with my existence) xD

        There are some solutions using dfs that passed. I can't guarantee that for your particular solution it will work, but you can try

        1. inlining local variables in dfs
        2. moving dfs parameters to the outer scope
        3. reducing the number of unnecessary arrays/vectors (for example, to implicitly store edges)
        4. submitting your solution under 32-bit g++ instead of 64-bit

        One of the testers' solutions used tail recursion, so maybe it was optimized by the compiler, but I'm not that familiar with the fact whether g++ can do such optimizations and if they are used by Cf's compilers.

        Sorry if I missed something, maybe someone else can help you a bit more. Good luck!

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

    I guess that's because the maximum recursion stack size is about 2e5, while in problem F there could be 4e6 recursive calls of dfs.

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

      Maximum stack size is not 2e5 -_-. Stop confusing people. Dfs with 4e6 size can pass.

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

        So what was the problem then?

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

          The problem is that your recursion takes up space. So if you have dfs with depth 4e6, it will take extra MBs.

          For example if your arrays and vectors use 80 megabytes. This dfs of size 4e6 will add extra 180 MBs. And total will be 80+180=260 which will get MLE. But if you optimize your dfs. Then it can use less memory.

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

            How to calculate the "180 MB", thank you a lot.

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

              there is no accurate way to do so. But it depends on the depth and number of variables that you initialize inside of it.

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

    Using iterative DFS instead of recursive DFS using stacks(or deque) bypasses the recursion stack limit problem: My Solution

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

I think the tutorial of problem C has a mistake:

The Words in the tutorial

I think $$$a_0$$$ should be [1,4,6,12,15].

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

what does "max[->]" mean in editorial of problem E

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

jj

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

problem H can also be thought of as segments on an X, Y graph. In this case the X coordinate is the amount of A left and the Y coordinate can be thought of as the amount of B left. Drawing this out one can observe that all such segments have slope -1 and thus only segments with the same y intercept can intersect with each other. It turns out this y intercept corresponds to the total amount of left over food across both A and B which is A + B — M. We can solve such a problem for each one of these intercepts separately and see that by rotating these lines to a slope of 0 we essentially have a problem where there are segments that may or may not overlap and we want to choose the minimum amount of points such that all segments are covered by these points. This is a well known greedy problem. Notice that we can just sort segment endpoints by the total amount of A left as when rotating this line to have slope 0, the order of these endpoints will not change if they are sorted by the X coordinate for these points.

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

Hi, could someone figure out why my submission for Problem F is TLEing? A runtime analysis of this shows that it should only be O(mn) — the size of the board, which theoretically should pass. Thanks a lot!

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For F question(Robot on the Board 2), I submitted this code but it is giving wrong answer on test 2 — test case 223. Can anyone help me out with the mistake?

Checker comment is: wrong answer number of steps in the output is 6 but in fact it's 7 (test case 223)