ko_osaga's blog

By ko_osaga, history, 21 month(s) ago, In English

Hello!

XXII Open Cup. Grand Prix of Seoul will be held in 2022/07/17 Sunday, 17:00 KST (UTC+9).

The contest was used as a Day 2 Contest for ByteDance Summer Camp 2022.

Problems were authored by jh05013, molamola., jihoon, ainta, pichulia, chaeyihwan, evenharder, TLEwpdus, applist, Cauchy_Function.

Special thanks to myself for translating the statements and editorials.

Enjoy!

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

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Ready to get destroyed by data structures and cacti.

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

Could you please provide the link to the contest?

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for the exciting contest! How to solve M and F?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    M: notice that if we replace min by max, then this is L_{\inf} distance, and it's equivalent to the Manhattan distance after rotating everything by 45 degrees. And for Manhattan distance, the sum separates into two sums that can be computed straightforwardly.

    And then we notice that min+max=sum, so we can subtract the above from the sum of sums (which is again finding the sum of Manhattan distances, but without rotating by 45).

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, thank you for such an amazing explanation with observations Petr !

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

    F: notice that in a group of consecutive stones of the same color, we can get at most one weight, and we can get no weights from the first and last groups. It turns out that we can always get any ceil(k/2) maximum weights from k non-first-and-non-last groups (because we can always find a group that we want adjacent to a group that we don't want, and remove both).

»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Seems the contest has been finished.

It's my favorite set in the ByteDance Camp 2022. Really enjoyed problem B, G, I and L. Thanks to the author!

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Could someone share a solution code for L? I tried to upsolve it in the ByteCamp but failed. My solution has the same complexity as the model one but it keeps getting TLE.

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

    Here's my code, 2.8/3s :) (I've removed includes and modint from ACL to make it smaller)

    Code
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just sped it up to 0.3s with the following diff:

        -      for (int step = 0; step < MAX_JUMP; ++step) {
        +      while (offset < res) {
        
        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          Note that you can also shave off a log factor entirely.

          Instead of using jump pointers with binary search, we can build a suffix array and query LCP in linear time. I'm not sure of it's possible to build a suffix array on a tree in linear time (I think DC3/SAIS might still work?), but instead we can also observe that this functional graph consists of only a single large cycle with paths of the form $$$22\ldots22$$$ or $$$22\ldots21$$$ hanging off of it. Thus, we can handle those paths in a special case, and build a suffix array on just the cycle (doubled). Together with linear-time RMQ to query LCP efficiently, this gives an $$$O(N + Q \log N)$$$ solution.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I uploaded the tester's solutions to the Gym. They should have no TL issues in Yandex, I think.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    I believe L also could be solved in $$$O((n + q) \log n)$$$ for any graph, not a specific one given in this task.

    It is somewhat similar to DFA minimization algorithm. Let's first split all vertices into two groups by color. Then do at most $$$n$$$ iterations of splitting groups into smaller ones. We can maintain the property that after $$$k$$$ iterations two vertices are in the same group iff they cannot be distinguished by $$$k$$$ moves.

    Naively on each iteration, we can split vertices into new groups by key (current group id, [current group id of the $$$i$$$-th children of current vertex] for all $$$i$$$).

    But it can be done in a lazy way. We could recalculate the group for a vertex only if one of its child groups changed in the previous step.

    Also, we can apply optimization — if, on some step we want to move more than half of the vertices of some group to the same new group, we can leave them in the current group, and move others. This way every time a vertex is moved to another group, group size is reduced at least by a factor of two, so each vertex is moved at most $$$O(\log n)$$$ times.

    Here is my implementation: 164708181, it is $$$O(n \log^2 n)$$$ because it uses sets to maintain groups, but it can be easily optimized to $$$O(n \log n)$$$.

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

Hyeong ko_osaga, can you share the test cases?

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

What was the approach for problem M?

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

Is there any editorial? Or plz someone give me solution of I.

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

Indeed, thanks for the amazing round!

How to solve B and K?

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    K: For a board, if $$$n,m\ge 2$$$ you delete the last column and the last row, and delete empty columns and rows at the same time, it will be the same as the original board. That's because if one player move the piece to the last column or the last row, the opposite can do $$$\ge 1$$$ operations.
    If every board has $$$n=1$$$ or $$$m=1$$$, the answer can be get easily.

»
20 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

I enjoyed this contest very much, thanks for round!

Solving some problems were helped by AtCoder's past problems

K: https://atcoder.jp/contests/abc229/tasks/abc229_h

M: https://atcoder.jp/contests/nadafes2022_day2/tasks/nadafes2022_day2_e

»
20 months ago, # |
  Vote: I like it +62 Vote: I do not like it

Thank you for the participation!

Editorial

Gym

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

Btw anyone knows how to import Ghosts from Yandex Standings? Wow, now I know how

»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

The solution to the problem K in the editorial is very cool in its simplicity and integrity. I did not want to think in such manner and applied some theory I know. Interestingly enough, what I obtained is a seemingly other solution. The editorial solution should imply that mine can be simplified further, but here is what I implemented.

My solution of problem K
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I also did all of that (on paper), but I didn't believe I would be able to implement that, so I found a simplification:

    I was going through (anti-)diagonals instead of rows, there we also have several arithmetic progressions with step 2. There will be one arithmetic progression (I called them segments) which is closest to 0, it will become wider with time, while other segments will shrink (at least on the side closer to the "main" segment). In terms of the initial picture the main segment covered some upper-left part of the plane, while segments below it covered some segments of rows (below that upper-left part) and segments above covered some segments of columns (to the right of that upper-left part). But since we are only interested in the value in the top-left corner, all the areas except for the main upper-left part are not interesting to us! Thus we can ignore all the segments except the main one. Moreover, new segments can only appear when some cell doesn't have the neighbour to the right or below AND the value we would assign there normally is not correct, but in this case we will assign 0 to this cell, which means that this cell will become the corner of the new main zone. In the end the solution is very simple: traverse both borders, maintain the current corner of the main zone, if encounter a cell with only one neighbour which would have incorrect value, make it the new corner of the main zone.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I implemented a similar but different solution. I traversed by rows from bottom to top and keep only the leftmost surreal number in each row.

      When we go up, if the left border stays the same we simply minus 1 (the cells on the right won't affect the value), otherwise in the top-left adjacent cell we plus one and max with zero (no cell under it) and for the cells on the left we plus 1 in each step. This is not exactly correct since the existence of right border (rightmost value is at most 0) so we need to cap it with the length of that row.

      If this sounds impossible to comprehend here's the code:

      int w=1,o=m;
      for(int i=n;i>=1;--i) {
          // suppose the i-th row is from L~R
          --w; // walk up
          if(o!=L) {
              w=max(w+1,0); // walk one more step left
              w+=o-L-1; // then the remaining lefts
              o=L;
          }
          w=min(w,R-L); // cap with the right border
      }
      
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why ML in problem I is 32mb?

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

    This is to guarantee that simplex would MLE.

    No reference solutions are close to 32MB ML, my tester solution came in under 4MB and I think only one tester had a solution above 8MB.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hm, interesting. Do you have a solution using simplex? If so, could you please explain, why simplex will return an integer solution and why it would fit into the time limit?

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

        There are MLE simplex solutions that were prepared, this is not a theoretical exercise. Since the intended solution wasn't simplex, and the intended solution comfortably fits in the claimed ML, there should be no issues, right?

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Of course, it is not theoretical problem. I'm just interested in the fact that the is a solution with simplex which moreover returns the integer solution, wow)