chokudai's blog

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) Announcement
By chokudai, history, 19 months ago, In English

We will hold UNICORN Programming Contest 2022(AtCoder Beginner Contest 269).

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

We are looking forward to your participation!

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

Comments Comments (24)
| Write comment?
»
19 months ago, # |
  Vote: I like it -40 Vote: I do not like it

Probably my first time solving 6 problems in abc and quite early.

It seemed easier than usual.

I'll refrain from further thoughts until the end the contest.

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

    I'd like to know what could possibly incur codeforcers' wrath in this comment

    → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Even though it is one of the very few tims for me solving 6 problems in abc, I don't feel any sense of accomplishment. It felt boring tbh

A. Useless as always
B. Bruteforce, ok..
C. So standard that is googleable
D. Standard dfs/bfs problem. Adding hexagons to it changes nothing /:
E. It feels like the problem being interactive is the only dificulty here. Observation itself is on the level of typical D2B/D2C on codeforces
F. Here again the only challenge is not to get some off-by-one. But I guess it was fine
G. Was not able to solve. But feels like we should exploit the fact that most cards have be indistiguishable by (a- b) difference

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

    C. So standard that I used recursion for it ;-;

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

    A to F were the most low effort problems I've seen in a while

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

    can you share your implementation of E

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

    Observation in E is really trivial. I mean interactive==binary search, 10^3==10bits, 20 queries. Nobody ever solved an interactive prob can miss that. D2B/D2C requires usually some thinking.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    G is as standard as C

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

      Well, not exactly

      Like, yeah, knapsack with with many indisguishable items and this binary trick is fairly standard, I remember solving it before. But you need to do certain mental efforts to convert the original problem to this knapsack (well, not very substantial, but still) and I'm not sure how to google it except looking through all the standard knapsack problems.

      C on the other hand is literally you google "iterate submasks", you get the solution.

      But yeah, it was not very creative either

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Demolished by problem F. Maybe I just wasn't careful enough.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the observation on G? It looks like standard subset sum but bounds are linear:/

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

I made a mistake in E by querying the columns using the 'answer' for the row (where A==B). Instead I should use A=1 and B=N when querying the columns.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was not able to implement E within aprox 10 submissions caused by stupid erorrs like no '?' in query output.

There should be some option to prevent this, it feels wrong to fail at something like this.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    What really feels wrong is the fact that if you correct it, you will be penalized for those incorrect submissions . And on codeforces you are protected by the fact that fails on the first test do not count.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great problems F & E were cool

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

After reading editorials of problem G, I finally realize how many amazing tricks are involved there!

The first one is that: we compute S=a1+a2+...+an, and when flipping some card, it means S-(ai-bi). Thus, the problem is equivalent to: giving S, and d1=a1-b1, d2=a2-b2,..., we should find the minimum number of steps to reach some integer of S-di-dj-...

The second one is: we divide (d1,d2,...,dn) into several groups of (ni, vi), where ni denotes the number of values which are equal to vi among (d1,d2,...,dn).

The third one is: prove that there are at most O(M^(1/2)) distinct values of vi. I missed this observation though I guess that some kind of sqrt decomposition idea might be used during contest.

The final one is: decompose vi into "binary form" so that ni is reduced to log(ni). I really remember that I have seen this trick during my virtual participation, which is based on a knapsack problem, but, I am sorry that I have tried my best but still could not find out which problem it is. If someday I get it, I would like to share it with everybody.

Finally thanks to the problem writers for coming up with such clever problems.

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

How to solve Ex? Naive way is $$$dp[i] = \Pi_{u \in children[i]} dp[u]$$$ using NTT and then adding one to $$$dp[i][1]$$$ . How to optimise this?

→ Reply