We will hold AtCoder Beginner Contest 417.
- Contest URL: https://atcoder.jp/contests/abc417
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250802T2100&p1=248
- Duration: 100 minutes
- Writer: math957963, MMNMM, tatyam
- Tester: physics0523, sounansya
- Rated range: ~ 1999
- The point values: 100-200-300-425-475-500-625
We are looking forward to your participation!
The difference in difficulty between question F and question G is a bit big today, but it doesn't affect my ability to do the question (after all, I am lucky to be able to do question F)
A-F too easy, but G too hard. This is completely a speed contest.
I agree with you,G is too hard to me!
I kinda felt like question D was too hard. Am i stupid? I only managed to solve A-C Normally I am able to solve 4 questions.
I usually solve A-C, but this time I solved also D. Just with prefix sum of B. if x > sum(b) + max(p), the answer is x — sum(b). Otherwise, I got the index idx where to begin iterating through presents, beginning with mood value
x — prefixsum[idx — 1] (idx is the max possible so that this expression still > 0)
and also caching known answers. I thought this solution would get TLE, but it passed.
I do think that D is harder than E and F.
Can we finally ban a new "talent" from India binaryphoenix?
He is blatantly cheating in different platforms. And he has links posted in linkedin profile(with 2.5k followers btw). He got top1 in recent codechef round but wasn't be able solve C1 in last div1 round. I guess it's very convenient to know what problem is chat gpt proved but at this point it's getting ridiculous. atcoder_official Dominater069
Does banning him increase your odds of solving more problems?
No. It's slightly decreased. Without him I wouldn't be able to know what problems chatcpt can solve lol. I guess he's doing great work representing llm capabilities. Actually, we need more guys like him.
Buy chatgpt pro. Cheat in every round. And even then, you're going to find a fellow defender from your country.
Then why not just focus on solving problems and getting better? Instead of tagging a new guy everytime and getting him banned is a waste of efforts from your side, people are already doing their work whomsoever you tag everytime.
Focus your energy on the right thing!! Best of luck.
I think that if we turn a blind eye to cheaters it's totally unfair to other participants...
Easy F, hard G. There's a GAAAAAAAAAP between F and G :(
why was F no brainer? or is it just me, it took me more time to solve D than to solve F.
Problem G can solve with balance tree. Wow
edit: the balance tree call WBLT, https://en.oi-wiki.org/ds/wblt/
Why did you use L[i], R[i] in G :((. I solved for concatenating the subarray of strings from L[i] to R[i]. X[i]/Y[i] would have been better imo.
G is well known persistent treap problem?
Or i am just dumb and just try to submit something that should not work?
How do you do it with treaps?
My solution: Moving to bigger of the L[i], R[i] and maintaining sort of binary lifting should work. Similar to Heavy-Light decomposition which would also solve for subarray L[i] to R[i] instead of just two points
node stores value 0 or 1, create two nodes S0 and S1
If size(root[l]) >= 10^18 just copy else just merge(root[l], root[r])
print(root[i], pos)
Merging in persistent treaps takes O(log(size)) in time and in number of nodes, so it can store string of length 10^18 with only ~120 nodes and each merge of two such nodes will create <= ~240 new nodes, so its fast enough
However, there might be a problem where we unite one small(of size 10^18 — 1) node and one node of size 10^18, we create smth of size 2 * 10^18, and then we add another 10^18 — 1 and so on, so max size of str stores is at most 10^23, looks bad, yet, out persistent treaps will store it in log(10^23) nodes which should be good enough
However, I was not able to figure out why I get 1/2 AC 1/2 RE during round
I had the same problem and was not able to figure it out during the contest too.
It's simple memory limit i guess. Even if we assume that we allocate about $$$120$$$ nodes per operation, we have $$$5 \cdot 10^5$$$ operations so we allocate about $$$60 \cdot 10^6$$$ nodes, which leaves us about $$$16$$$ bytes per node. And we at least need to store two pointers to left and write which alone would be $$$16$$$ bytes (in case we do not write treap on arrays where we can use int32_t as a "pointer").
I made an experiment with exit(0) in my submission when i allocate more than $$$15 \cdot 10^6$$$ nodes and got rid of the RE, so it's just one of those cases when the judgement system confuses RE and ML.
I've skimmed through some submissions sorted by memory limit by decreasing value, and it turns out it is possible to squeeze into the memory limit, but one has to be quite careful (e. g. https://atcoder.jp/contests/abc417/submissions/68172571).
And it also seems that $$$30 \cdot 10^6$$$ nodes is enough (but i have no idea why, it's only 60 nodes per operation...).
I just wrote a test that keep merging two treap with size 10^18, and turns out it use around $$$\frac{4 \times 10^7}{Q} \approx 2\ln(\text{10^18})$$$ per merge operation. Though I'm not sure how to analysis it properly.
Btw, I didn't think that much and just create as many node as possible under ML when submitting it then pray it works lol
Screencast with commentary (once it is processed)
Didn't solve G though
For problem D, my solution is failing one test case. Can anyone point out the problem?
Submission Link for D
UPD: Found the problem. Never Mind!
SpeedCoder Beginner Contest. Wasn't able to solve G (TLE on testcases starting with "random2_") and solved A-F too slow, then got negative delta.
Also, long judge queue near the end of the contest.
How the Hell does this O(Q * N) code even passes????
Is that so ?
One of my friends' $$$O(nq)$$$ code also passed. I guess the test data is random. And here is the hack:
Can anyone help me how to solve D and E ?
For D, we maintain two sets of queries:
Since both Ai and Bi are ≤ 500, at most 500 elements can move from one set to the other during a single update operation. After each update, we must rebalance the two sets accordingly. We also maintain two variables:
While balancing the sets, we need to handle these values( first find the current value then remove the effect of another set).N*Ai*log(Q)68158783
Set will give TLE, so use priority_queue.
My submission for E keeps exceeding time limit for one testcase again and again. Could somebody please tell me if it's because my complexity is bad or if it's because my logic is flawed somewhere and so some loop doesn't break somewhere? My submission : https://atcoder.jp/contests/abc417/submissions/68172945
Finished my code of G, but considered as bot, cannot submit
My code got 30 WAs on G. Can somebody help me plz? submission
Upd: I considered $$$X_i$$$ as an int value. AC now :)