We will hold UNICORN Programming Contest 2022(AtCoder Beginner Contest 269).
- Contest URL: https://atcoder.jp/contests/abc269
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220917T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: physics0523, Nyaan
- Tester: nok0, Kodaman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
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.
I'd like to know what could possibly incur codeforcers' wrath in this comment
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
C. So standard that I used recursion for it ;-;
A to F were the most low effort problems I've seen in a while
can you share your implementation of E
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.
G is as standard as C
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
Demolished by problem F. Maybe I just wasn't careful enough.
What's the observation on G? It looks like standard subset sum but bounds are linear:/
I feel this could help.
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.
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.
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.
great problems F & E were cool
What in the world is great about E apart from the fact that you apparently were able to solve it?
Was E binary search ?
Yes
Binary search column
Binary search row
Print
great != super hard , the idea was cool
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.
Can someone please explain the final trick? Unable to understand it from the editorial
I think this https://codeforces.com/blog/entry/49812 will help a lot, and you can find many details there. This blog is first mentioned above from ceciver (sorry to disturb you here), and let's thank him for such great help.
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?