fried-chicken's blog

Unofficial discussion of 2020-2021 ACM-ICPC, Asia Seoul Regional Contest
By fried-chicken, history, 4 years ago, In English

Since there isn't an existing one, I'm writing this blog for discussion of this wonderful contest, feel free to share any thoughts or solutions about this contest.

For me, how to solve the problem L?

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

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

L is a direct copy-paste....

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

    Totally understand it, thx.

    Btw, the origin problem looks like at least a middle-hard problem in 2017-WF, but now it seems already easy for many people.

    Bonus: the origin problem in 2017-WF is firstly solved by Seoul National University, while this contest is exactly the regional of Seoul

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

I just solved problem K with a nice, but tedious approach (300+ lines) and was curious to see whether there was an easier way. I looked at some other submissions and found out that some fairly simple greedy passed. I tried running another accepted submission (that uses simple greedy) on the following test case:

5

11011

11011

01010

01010

01110

and I think it failed. On the other hand, I think this is a valid input which also has a valid solution. Could anyone explain what is going on? Am I missing something? (Sorry if I'm missing something trivial.)

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

    Maybe a link to this solution so that we could know what does "simple greedy" mean?

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

      Good point, a link to the greedy submission: https://codeforces.me/gym/102920/submission/105509314

      But maybe only people who solved the problem can view this submission, this is actually weird. Hmm, I'm not sure if I can just copy paste that code here, as that one is not by me. But the main idea in a nutshell is:

      Visit every row from top to bottom and every cell from left to right within the current row. If the current cell is a '1' (and not covered yet), then try fitting a horizontal 1x2 starting from this cell. If you cannot, but the previous 2 cells were covered with a 1x2, change that to a 1x3 horizontal. If you can't do this either, try fitting a vertical 3x1 starting from the cell. If you still can't do that, fit a 2x1 vertical starting from the cell.

      I think this greedy is tricky, I almost believed it, but then I found this counter-example. So now I'm still confused about the situation.

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

        Since I have the coach mode, I can view this submission and I think it's wrong and the original tests were weak :(

        It's even wrong on simpler test like maybe:

        3

        000

        111

        001

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

          Thanks for your reply! I was also suspecting this, but just wanted some confirmation from others. It was a great problem anyway, I certainly enjoyed it! :)

          Edit: actually your example is not valid, as each '1' cell should have at least 2 '1' neighbours.

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

    I was able to "hack" with TLE the first place solution (and some in upsolving with w.a) with this case:

    5

    11100

    10100

    11100

    10100

    11100

    I think the case is valid, maybe I misunderstood something in statement

    How to properly solve problem K?

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

      Your example is not valid, because the polyomino cannot contain any 'holes'. (I also thought about your example first before I came up with the one I showed above which 'hacks' some solutions.)

      Also, I can try to explain the main idea of my solution (there might be significantly easier ones though):

      Let's call a cell critical if it is a '1' and there is no 2x2 square of only '1's that contains this cell. Let's call a cell normal if it is a '1', but it is not critical. Now we can find the connected components of normal cells in the graph. Then we will remain with a tree structure with connected components and some 'channels' going between them formed by the critical '1's. (Note that this is something very similar to doing biconnected components, but not exactly. Also note that we used here that there are no 'holes' to get a tree)

      Claim 1: every component here can be just tiled greedily with either only vertical tiles or only horizontal ones. (You can prove this by showing that it is impossible in a component to have a cell with no vertical neighbours and can do the same for horizontal... and we can use the fact that any 1 x K can be tiled when K > 1)

      Claim 2: given a component and a critical cell that is adjacent to it, you can tile this greedily. (if the extra cell is vertically connected to it, the vertical greedy will work, otherwise the horizontal greedy.)

      Now we can just root our tree at one of the components and recursively do the following:

      • tile our component using either Claim 1 or Claim 2.

      • start recursively tiling all adjacent channels with 1x2 dominos (note that these channels can be uniquely covered with 1x2 dominos greedily)

      • when a channel 'arrives' to another component, we have two cases: if the last cell of the channel did not have a pair, we can just tile it with that component using Claim 2. Otherwise, we can just only tile the component with Claim 1 and follow the recursion from there.

      So it's some kind of a dfs. Hope this makes sense more or less.

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

    My code for this problem is also quite long, but there is a simple take on this problem. Interestingly, it doesn't differ radically from other "tedious" approaches I'm aware of :)

    In most cases, as there are no corners, you can simply fill each connected rows by $$$1 \times 2$$$ or $$$1 \times 3$$$ blocks: If the length is even, just fill it with size 2, otherwise, replace the last one to size 3. This always works except the single tricky case: connected rows with size 1. Let's call such case as a "bottleneck".

    Now do a "hybrid" DFS. Do a depth-first search, where you label every cell as "horizontal" or "vertical": Horizontal blocks will be filled horizontally, and vice versa. In this sense, the above algorithm naively tries to fill every cell into horizontal and fail. In the improved algorithm, you also usually try to fill everything horizontally, but if you meet a bottleneck you should flip the strategy and fill vertically for the bottleneck and the areas past there. Recursively do that, and if you meet a vertical bottleneck do the same thing.

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

      Ohh, that's a very nice way of approaching it :) Thanks for your explanation!

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I got into some problems in solving problem I. I tried to use the decompose with BIT to solve this problem but I got WA on test 4 for many times. So could you please help me with my code ? Or anybody can give me the data of test 4? Thanks so much!

My code: https://codeforces.ml/gym/102920/submission/109009957

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

    From your submission, I guess you mean the problem I?

    Test 4 is a long one so I can't copy-paste it here. But maybe I can describe it.

    The first 2 lines is:

    6 441

    -5 2 3 5 -1 4

    Then, the 441 queries can be described as:

    for i in [1,6] : for j in [i,6] : for k in [-6,14] : print(i,j,k)

    And the checker said: wrong answer 149th words differ — expected: 'NONE', found: '-5'.

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

Korean solution writeup

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

What's the complexity of the problem D ?

I think it is O(n^3) ,but the Tutorial says it is O(n^2log(n))

Could someone explain it to me?

Like how to build the graph?(I make it in O(n^3)

→ Reply