We will hold Japan Registry Services (JPRS) Programming Contest 2025#1 (AtCoder Beginner Contest 392).
- Contest URL: https://atcoder.jp/contests/abc392
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250208T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, kyopro_friends, ynymxiaolongbao
- Tester: nok0, MMNMM
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-500-600
We are looking forward to your participation!
Planned post contest discussion
Update: VOD Twitch YouTube
Great!
My Rating is 980 now,I hope to get 1000 or more Rating from this contest!
My Rating is exactly 1000 now!What a lucky day!
Hope to get my Rating 1500!
I think there is no point in the Atcoder Beginner Contest now(in terms of rankings). like today a lot of submissions are purely AI generated.
Ok after the contest. Please explain F and G.What should I study todo such problems.
F is more of an observation-based problem. Hint: Try to do it in reverse.
My implementation sucks fr
In this round, almost all the problems examine only the basic application of algorithms.
What's more, AI still occupies the rank list.
There are 392 Atcoder Beginner Contests. But now ABC is in the face of the difficulty of adapting to the trend of the times. We wouldn't like to see ABC become AI Beat Contestants.
Just focus on having fun solving the problems. Worrying about AI 24/7 is only going to lessen your enjoyment of CP. The problems were fun and interesting and that's all that matters.
Fully agreed, I mean people come here and yap 24/7 how AI will ruin CP and erase it from the face of the world, but look at Chess, Kasparov lost to IBM's AI, some 20+ years ago, it's still pretty relevant, just have fun lads!
https://tlx.toki.id/contests/tsoc-april-fools-2024/problems/F
problem G is the same as this :>
Problem F: The position where element
iends up (call itpos = a[i]), we iterate fromi + 1till end and incrementposwhenevera[i] <= pos. But how to implement this?It's difficult to handle in the forward direction. I think you can process it in the reverse direction, which would make it easier to use a BIT or segment tree for maintenance.
ABC -> AI Beginner Contest
I felt that E is harder than F. I spent most of my time on E, and was lucky to have enough time to do F lol.
Isn't E just straight forward DSU ?
Yeah, but the implementation is kinda heavy. F's implementation is much simpler.
I'm not sure if you overkilled it, but my solution isn't implementation heavy.
I guess there is a lot of room for overcomplecating things, on how to connect the components using the "free" edges.
As I did, maintaining a priority queue of components ordered by number of available edges... also updating that queue is a pain. And actually not really needed for this problem.
How the hell did so many people solved F and G? I don't think ABC is POSSIBLE in this AI era.
My screencast in Rust
The first accepted of problem D is named "ReasoningModel" and their affiliation is "DeepSeek & OpenAI" LMAO
UPD: user removed
F and G need some complex algorithms(At least i used them), which is friendly to AI, not beginners.
E is good, I think.
I could be wrong, but isn't it straight-forward DSU, with just maintaining the ends for any extra-edges that create a cycle in a single component ?
It seems that you can sort the components by the number of extra-edges, and simply store available edges.
But what good will the sorting do ? If there are N components, you'd need N-1 extra edges. Irrespective of which component you choose to remove extra edges from you'd always have N-1 operations. So I don't get the sorting ?
store the extra-edges in prefix conponents after sorting
Anyway i don't think AI can solve it easily...
What can I say?
I accepted the problem ABCDEF, but my performance was only around 1500, which was much lower than ever.
The contest took about ten minutes of AK, and it was done by a black-name user, and its code looked like it was coded in AI. Is that right?
I hope you get more ratings than ever before.
Before this competition, when I took the question ABCDEF, I would get above 1600.
But today, everything has changed.
I don't know how to do fft, but AI does.
Today's FG is the most simple FG that I solved in ABC.
Yeah, this is true. The problems today is very classical (especially FG) that I think many AI can solve them in <=10mins.
I hope the quality of ABC can be improved. It should at least better than this.
how G? teach me plz!!! o(〃'▽'〃)o
For a < b < c, by enumerating b, for every valid pair (a, c), there must exist a + c = 2b. You can directly use NTT to handle this.
thank you
use FFT/NTT.
let $$$A[i]=1$$$ if and only if $$$i$$$ appears in $$$S$$$, and $$$B=A*A$$$(* means convolution). Compute $$$\sum(B[2S_i]-1)$$$
thank you too
I don't think it's a good idea to put G here.
I believe a major reason that so many people solved G is that AtCoder provides function to calculate convolution, and one can solve this problem by simply calling this function.
So I think we can call this contest AI Beginner Contest :)
ac-library beginner contest
More than 500 people AK this contest. It seems that I was a joker QWQ
Can someone help me, what's wrong in this. only one test case is not passing https://atcoder.jp/contests/abc392/submissions/62569728
In line 13, "ans += ( (long long) (p.second * b[key]));" -> "ans += ( (long long) (p.second) * b[key]);"
why 1 testcase is not passing in D problem
mySubmission
In line 35, "v[i][x.first] * x.second" can be very big, you can use long double.
Can Anybody please tell why this fails , https://atcoder.jp/contests/abc392/submissions/62571244
For problem F, I figured out a AC solution, but still don't understand why a libstdc++ rope solution like this would TLE. I tried inserting at the beginning/end/
size()/2in custom test withN=5e5in custom test and it ran quickly. Is it actuallyO(n)?Can anyone explain why this solution of E fails. My method: I created a data structure named extra which stored the self loops edges , multiple edges between two same node and nodes needed greater than size — 1 of that component with their indices and then I sorted the leaders of the connected components in decreasing order of the number of extra edges the connected component contains.
Then I just had to form a tree assuming a component of a tree to be a node . and add the edges . But its failing
can anyone explain why or provide a counterexample? Code
Shouldn't time complexity of F be O((logN)^2*N) according to the editorial? Binary search on fenwick/segment tree?
Bro, I’m with you. I’m just here to look for a comment like yours.
No, it's possible to do the search while traversing the tree, instead of traversing multiple times and adding an extra log.
AI making me feel bad about this contest, but I think figuring out EF on your own is strong. F took me way too long to figure, cause once I saw it I realized it isn't super difficult. I came up with a solution that would be O(Nlog^2(N)), with a rough outline of using reverse iteration, Fenwick tree and binary search.
WHAT'S THE PURPOSE OF SETTING MORE AND MORE DS (OR ALGORITHM PROBLEMS WITHOUT BRAIN) AND SOLVE IT SIMPLY BY ATCODER LIBRARY???
G is sh*t! (Becasue it can be solved easily through AtCoder Library.)