chokudai's blog

By chokudai, history, 3 years ago, In English

We will hold UNICORN Programming Contest 2021(AtCoder Beginner Contest 225).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

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

Codeforces Problem C
Got this Problem at tha last moment of Contest. i think it can help for problem F

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

    Yup. That plus dynamic programming $$$dp_{i, k}$$$ where the states represent the possible lexicographically minimum string from choosing k strings from $$$a_i...a_n$$$ got me an AC.

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

    The problem you mentioned is on GFG as well, but the exact solution dosen't work as stated in the editorial. The editorial of problem F is quite descriptive, listed out quite a few incorrect solutions :)

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

Hints for E? No editorial published for it.

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

I'm wondering why double gets WA and long double gets AC in problem E. Did anyone encounter the same case as I did?

I found the angles for each pair of (x,y-1) (x-1,y) and treated them as segments. Then I used greedy to find the max number of non overlapping segments.

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

Any hints for problem G? Thanks a lot.

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

      I don't get it. Why/how does this work?

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

        This is the construction I learned from the solution to the "maximum density subset problem". You might be able to find some resources on it if you google.

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

        Here's another way to explain the same solution:

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

Lost stupid amounts of time on D due to output requiring a length descriptor. My fault for forgetting how to read again, but still annoying nonetheless... probably should've focused on E rather than continually trying wrong things on F in the time remaining... will have to find out in upsolve though.

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

how to solve problem D using DSU?

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

    Graphs alone are enough for D. To perform the first and second types of queries efficiently, we can use multisets instead of vectors for the adjacency list. Then we can build 2 graphs(the second graph will be a reversed graph of the first graph), one contains edges from y -> x and the other one contains edges from x -> y. To answer the third query, we can run a DFS on the first graph to find the deepest reachable node(say 'root' node) from node x, then run another DFS on the second graph starting from the 'source' node and print all the nodes we visit one by one.

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

      Thnx for replying , but i solved using the graph only.i want to know can do u using dsu too?

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

My solution for C was based on the idea that all numbers in the same row would differ by 1 and all numbers in the same column would differ by 7... But I am getting WA on 5 test cases. Anyone got any idea why?

Link to my submission https://atcoder.jp/contests/abc225/submissions/26968319

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

    You need to check the remainder when divided by 7 as well, the starting column of the original matrix is divisible by 7.

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

Sorry for necroposting, but I can't think of any better place to ask this.

In problem G, are there any solutions without max flows? I found a really neat idea that if we consider a chessboard coloring of the grid and rotate everything by 45 degrees we get 2 independent grids: one with black squares and the other with white squares (here new cells are adjacent if original cells were diagonally adjacent).

Now it is really easy to see that it is always optimal to only mark complete subrectangles in each grid, so one thing we can do is $$$O(n^5)$$$ subrectangle dp, which is too slow with long longs even after considering the low constant factor.

It's a cool idea and it's sad that it probably doesn't have a continuation.