maroonrk's blog

GCJ 2021 Round3 Discussion
By maroonrk, history, 3 years ago, In English

As of now, there is no blog, so I'll post this.

How to solve C Large without complex casework?

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

Comments Comments (38)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

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

All I could think of during the round: who hurt the problemsetter?

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

    For me the problems were mostly fine?

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

      Do you have clean solutions (i.e. not a shit ton of casework) to A/C large?

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

        For A there is a clean exponential solution (mine solution is some shit tho). In C there is not that much casework. However the solution idea I have is rather tedious to code even though I really like geometry. Not super bad though.

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

        A:

        N is odd: simple greedy

        N is even: Run backtracking. If the prefixes aren’t equal then greedy works (we know which number is greater, so it has to be as small as possible). If the prefixes are equal then consider all possible choices, but make sure that the digits in the equal prefixes are somehow sorted (in nonincreasing order for example).

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

          I pick a000...000 and b999...999 and try to append to head with equal pairs and tail likes the odd case.

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

        Odd length is simple. For even length, we will check all possible prefixes that will be shared for our numbers. For their first different digits, brute force all pairs that minimize the difference. The remaining suffix can be constructed greedily.

        The official analysis provides a $$$O(2^{N/2})$$$ but for the worst case where each digits from 1 to 9 has 4 occurrences, we can further improve it to $$$3^9$$$ cases (choosing 0, 1 or 2 pairs for each digit).

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

        N is odd: trivial.

        N is even: I sorted the digits, and used a recursion. In any recursion where we are trying to minimise difference, the leading digits must be adjacent in the sorted list. Try each adjacent pair, taking care not to use 0s in the first case. If the adjacent pair are the same, you repeat the recursion on the remaining digits. If the adjacent pair are different, you are then finding the smallest and largest possible numbers from the remaining set.

        I used memoization just to be sure but I probably didn't need to.

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

          I forgot memoization and got TLE, so probably you should.

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

            Yes I realise now why it's needed: you have 35 adjacent pairs, but in the worst case only 17 unique adjacent pairs (in the case 000011112222333344445555666777888999 for example).

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

    I don’t like C, but other problems were quite nice :)

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

Why Radewoosh dropped to 34th place from 2nd place after getting perfect 100? same with firefly?

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

I'm sorry to be so harsh but IMO A ruined the entire problemset.

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

Problem A was disgusting.

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

tfw you would have been able to submit B small to get within qual range if you just had one more minute :(

Not a fan of A at all, and the implementation for B small was a bit bashier than I would have liked, but I will note that D was a very nice problem--too bad that it was stuck at the end of the set!

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

I think that C large can be solved by first computing an arbitrary triangulation, and then flipping all edges that intersect the two constrained edges.

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

Screencast (without commentary this time)

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

Passed B Large with a strange algorithm:

  • Create a graph which satisfies the row/column constraints, regardless of squares.
  • Make a while loop to scan through the graph to find squares. Flip (slash to backslash and vice versa) any square(s) found.
  • Exit the loop if no squares found during one complete scan.

Seems most participants use network flow for B.

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

    I don't even need to search for squares which simplifies the code significantly. I just exhaustively check for 2 rows and 2 columns such that on their intersections I have
    /\
    \/
    and I flip all of these 4 cells.

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

    Flow is the easiest way to construct a grid with given constraints. I knew it can be found constructively in linear time, but didn’t want to bother.

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

    How could you create the satisfied graph without network flow?

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

      Wouldn't greedy (where for every row you mark the columns with the most marks still needed) work? Can't come up with a counter-example.

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

        It works. Proof: let's consider filling rows one by one. Suppose that for some row $$$i_1$$$, we put mark into column $$$j_1$$$ and don't into $$$j_2$$$, where in column $$$j_2$$$ we need to put strictly more than into $$$j_1$$$. Then in some of the next rows (say, $$$i_2$$$), we will have to put mark into column $$$j_2$$$ and not into $$$j_1$$$. Then we can instead put marks in $$$(i_1, j_2)$$$ and $$$(i_2, j_1)$$$ instead of $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$

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

      For each $$$D_j$$$, find the $$$D_j$$$ number of rows with the largest $$$S_i$$$. We place a slash in each $$$(i, j)$$$, and decrease the corresponding $$$S_i$$$ by $$$1$$$ afterwards.

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

        I also did this. Used priority queues to construct the initial grid row by row: if at any stage you run out, IMPOSSIBLE, otherwise you have a starting grid.

        Then my approach was similar except that I moved all /\ pairs to the ends of rows and columns and all \/ pairs to the start, and then repeated that 20 times to iteratively move any newly created problems leftwards/upwards until finally there were no problems left.

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

        They have mentioned this approach in "Flip Flop" section of the Analysis and show that it's finite and the asymptotics are enough. They didn't however mention greedy which makes this task even easier (since flows are only helpful if you solve the task the intended way I feel).

        This is the reason why I personally disliked this task since it clearly has two ways two go about it with one significantly easier than the other one. From reading the analysis I got the impression that they realized that there exists this alternative solution quite late in the problemsetting, and I'm not sure why the task was kept after that or not swapped with the first one.

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

Screencast (solved aBd, one step away from aBD) https://youtu.be/MDTHp_DA-lU

warning: sound is bad

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

My solution to A matches the editorial and it isn't tedious at all IMO. I guess most dislikes come from people with solutions not as clean.

My solution to C:

  • If there are no extra edges, pick the lower left vertex $$$v$$$, sort other vertices by polar angle, connect neighboring vertices in this order and also connect all of them to $$$v$$$. After that, run a Graham scan with stack to make the polygon convex, adding some outer edges in the process.
  • If there is one extra edge $$$u-v$$$, split all vertices into those to the left and to the right of the corresponding line ($$$u$$$ and $$$v$$$ included in both sets), solve the problem for these sets, merge their convex hulls into a single polygon, and do the same Graham scan to make it convex.
  • If there are two extra edges, do the same as in the case of one extra edge, but for the purposes of splitting the plane, pick the edge such that the other one is contained in one of the half-planes. Solve recursively (one half-plane will have 0 extra edges, the other will have 1), and merge.
→ Reply
»
3 years ago, # |
  Vote: I like it +189 Vote: I do not like it

rank 26...

Next time I will try to write small tests immediately on complicated problems such as C, D... (>__<)

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

Surprised to see all the hate for problem A. N odd was trivial, and N even could be tackled by a fairly clean recursion:

  • Sort the digits

  • Try each adjacent pair as the leading digit of the two numbers

  • If the adjacent pair are different, greedily fill the remaining digits. If they're equal, recursively solve for the remaining digits (allowing leading zeros after the first level of recursion)

  • Take the minimum of these

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

Congratulation to all 24 finalists. We will know in two months who is the 2nd place of GCJ 2021.

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

    I've a feeling that radewoosh might be 2nd only if mifafaovo doesn't go in god mode.

    → Reply