We will hold Aising Programming Contest 2022（AtCoder Beginner Contest 255）.
- Contest URL: https://atcoder.jp/contests/abc255
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220611T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, physics0523, m_99, nok0
- Tester: math957963, nok0
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
Wow, this ABC feels so different(looking at B and C's unusual difficulty). Took 20 min for C, but 5 min for D...
E is really nice. How to solve E better than $$$O(N.M^2)$$$? My solution surprisingly TLEs on 12 cases with that complexity
Did you try treemap? $$$O(NM^2logN)$$$ is enough for E. My submission
Maybe its unordered map constant factor
Actually no. It's probably because
[]operator inserts the element into the map if it's not already present, with default value 0. So you should first check the element's presence and then only access it using[].Thanks, it removes the TLE. Lesson learnt. Solution
Edit: This is me from 13 months into the future. It's better to use M.find(x)!=M.end() instead of M.count(x) as the latter is actually O(number of elements in map)
There are two main observations:
If we fix the value of any element of $$$A$$$, then the value of all other elements can be determined easily.
Let us say we fixed the value of index $$$A_0$$$ = $$$0$$$, then if we increase $$$A_0$$$ by $$$1$$$, then all $$$j$$$ such that $$$j mod 2$$$ = $$$0$$$, value of $$$A_j$$$ will increase by $$$1$$$ and for other elements their value will decrease by $$$1$$$.
Now since we've already fixed the value of $$$A_0$$$, we can easily find the value of other elements of $$$A$$$. Now, to maximize the answer we will find the value by which $$$A_0$$$ should be increased (or decreased) such that $$$A_i$$$ becomes equal to $$$X_j$$$. After finding this for every possible $$$i,j$$$, we will just increase(or decrease) $$$A_0$$$ by the most frequent value and calculate our final answer.
Submission
Personal lesson from this contest: Read statements carefully. At first I tried to solve Problem E assuming $$$A_{i+1} = A_i + S_i$$$. When I was done, the sample didn't match and I realized my error. $$$head \rightarrow desk$$$
Went on to solve F instead, to forget my wrong assumptions.
Turned back to E, realized how to solve it when reading it correctly, but then the contest was over. Upsolved 10 minutes after the contest: Submission — It's basically the same idea as your's. I'm not entirely sure why your's takes only 668ms compared to 861ms from my cleaned-up version
As a 900-rated on AtCoder, I took 20 min for B, 40 min for C and 10 min for D. I think something must be wrong:(
Hey, guys! Could any of you help me and find a mistake in my code? 67 AC and 1 WA for problem C :)
Submission: https://atcoder.jp/contests/abc255/submissions/32404305
Thanks in advance!
\sout{Your mn can be greater than mx.}
How come? They can be at most equal.
oh, sorry. You are right. But you only check negative operation for remainder. Didn't check for the positive operation.
long long num works for a positive operation if I have got you right.
i.e. x-a = 7 and d = 3: the answer in the else statement will be min(1, 2).
Your answer gives -7. Correct answer is 2.
It gives 2 in my compiler however..
Do you have atcoder / CF setting (or whatever it is called) in your workspace? Probably my compiler skips this error, but I am not sure.
I ran your code on Leetcode Playground. Please give it a try there to see if you also see -7.
Even there it gives 2 :)
You have multiple submissions. The last submission or the link provided gives -7. When I clicked on another submission of yours and I can see the result is 2.
Oh, for some reason it linked different one, sorry.
Just use d = abs(d) before calculating "num" and you'll be fine
Yeah indeed, thanks.
I am not quite sure but maybe your 27/28 lines may lead to wrong answers if d<0.
B irritating statement, and C much more difficult than expected.
My E runs in O(N*M*log(N*M)) submission
Why do you use strange define cini?
That's 6 characters, but cin>> is 5.
cini also includes the variable definition, so its one whole statement less.
Can you please explain your solution in detail. It looks so clean!!!
It looks clean because of using cini, thanks ;)
Well, it is more or less same as explained above. The sequence A[] is determined by a[0]. If we increase/decrease a[0], all other elements change accordingly.
Since there are only max M=10 good numbers, we can check foreach A[i] the max 10 values for A[0], so that A[i] becomes a good number, and collect the frequency of these values.
Then we choose that value for a[0] that has the max frequency.
F is a common interview problem https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
B, C, and D are binary search. Nice!
yeah i did bs in all too !!
you don't need binary search for B and C.
Yeah i suck at maths .
how to solve B without binary search?
Maximum of minimum distances of all people from the people with lights.
*facepalm, thanks
The condition in F about the fact that the root of the tree must be node 1 does not make any sense. The check is trivial and does not affect the solution in any way, but you can accidentally skip it and get WA
Why add weird checks to the task?
I agree with you. But why do you get wa if this case is present in 2nd sample?
Sent in the last minutes and did not have time to check the samples)) It's my fault, I agree
How to solve problem D? I have no idea.
Binary search + prefix sum
thanks, bro. But I still don't understant :) wating for the editorial...
oh! I undertand now! How stupid I am !
Do atcoder count rank of unrated people too? like my rank was 2120 during the contest and after the system testing it still same
Atcoder don't have the system testing. And unrated people does count. If yuo want to remove them, select Standings — Standings — Customize — Show Rated Only.
I kept getting WA for problem F during the contest, and finally find the mistake after contest ends. I should always use array-P to construct both left and right child nodes. But unfortunately, I used array-I to build at least one of left/right child nodes in my every submission.
Anyway, the problems are quite great and really appreciate the work from atcoder team.
I have different solution for problem F and i think it's worth mentioning .
For each $$$P_i$$$ let's find it's parent node and it belongs to the left/right of parent node . Let $$$pos[P_i]$$$ denote position of $$$P_i$$$ node in array $$$I$$$ , then i'll do following :
If there exists $$$j<i$$$ such that $$$pos[P_j]>pos[P_i]$$$ and has left child untaken , pick such $$$P_j$$$ with smallest $$$pos[P_j]$$$ and assign $$$P_j's$$$ left child to $$$P_i$$$
Else if there exists $$$j<i$$$ such that $$$pos[P_j]<pos[P_i]$$$ and has right child untaken , pick such $$$P_j$$$ with biggest $$$pos[P_j]$$$ and $$$P_j's$$$ right child to $$$P_i$$$
Those operations can be done in $$$log(N)$$$ with set , so final complexity will be $$$O(Nlog(N))$$$ . During contest i didn't waste time on proving this , but now i think it's provable .
link to submission
Link
Getting wrong answer HELP me to debug for problem CD, the difference, may be negative. For this test case:
your solution gives 8. Since the good numbers are 10, 5, 0, -5, -10, the closest number to -2 is 0. The answer should be 2 instead of 8.
Any idea about how to solve constrained nim ?
You are aware of the editorial?
yes, but i guess this mathematics is beyond my scope. Can you please explain in a bit simpler manner, perhaps without the use of grundy numbers if possible.
I went through some codes but not able to get what is happening.
Sorry, I have no solution that is less complecated than the editorial.
no issues, thanks !!