Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя maroonrk

Автор maroonrk, история, 3 года назад, По-английски

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

How to solve C Large without complex casework?

  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +215 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    For me the problems were mostly fine?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

        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).

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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).

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +16 Проголосовать: не нравится

            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).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +99 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

Problem A was disgusting.

»
3 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Screencast (without commentary this time)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    How could you create the satisfied graph without network flow?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

        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)$$$

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

warning: sound is bad

»
3 года назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

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.
»
3 года назад, # |
  Проголосовать: нравится +189 Проголосовать: не нравится

rank 26...

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +221 Проголосовать: не нравится

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