We will hold AtCoder Beginner Contest 451.
- Contest URL: https://atcoder.jp/contests/abc451
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260328T2100&p1=248
- Duration: 100 minutes
- Writer: KumaTachiRen, harurun4635, toam
- Tester: cn449, sounansya
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-500-600
We are looking forward to your participation!
Rank 1(first comment)
standings looks broken nowadays
Yep, with unrated participant getting top 1, 2, 3.
啊a~
help~~~
How to do D, wasted 1 hour trying to observe any sort of pattern
You can generate every good number using backtrack, then sort the list.
But there are lot of numbers no ?
You can still generate all of them without getting TLE.
strangely enough, 128 can also be formed by concatenating '1', '2', and '8', so there will be duplication during backtracking. My solution runs under 100ms still
I used set for that.
Actually, this problem can be solved even if the integer range is 1E18, which is how I did it.
In fact, there are only about 1e6 eligible numbers in total.
But didnt in teat case there is query where n >=1e7
The constraints of the test cases are:
You can check the editorial here.
I tried Bs + digit dp to count number <=x I can make using power of 2 as string, Dp started over counting and i spent whole contest debugging
Wasted way too much time on a randomized solution for E, didn't have enough time to solve G despite looking easy :( I'm guessing there was something obvious I missed
for E , i connected nodes with minimum distance first like a minimum spanning tree, and then did a dfs to generate distance matrix and checked whether it matched with given one.
I literally guess this and luckily it AC hooray
I spent 40 minutes for D, and the same time for E+F.
I tried to build a DP, but it turned out to be a brute force.
Really confused with my behavior
The exact same thing happened to me (except i didn't even get close to doing e or f)
I used mt19937 to solve E,no hacking!!
For D, even if you don't delete any of the multiple numbers, there are only 1404832.
And you see in the sample, 1099898-->819264512, close to 1e6-->1e9.
According to our feeling, the numbers rarely be the same.
Only something like "1"+"2"+"8" and "128" would be like that, but these are few.
E = 472D
yo they just banned my acc for no reason (i write 3 question a, b, c lol) i dont understand :(
G's editorial english translation is missing the definition $$$W'_e = W_e \oplus A_u \oplus A_v$$$ in the spanning tree $$$T$$$
I think F is a very good educational problem for learning disjoint-set-union which maintains extra information. If you have not yet learnt it, I strongly recommend try this problem.
has anyone solved E without resorting to tree construction?
i don't understand why finding a $$$k$$$ for every $$$i \lt j \space$$$ s.t. $$$\space A_{ij} = A_{1i} + A_{1j} - 2A_{1k} \space $$$ and $$$ \space A_{ij} = A_{ki} + A_{kj}$$$ isn't enough