We will hold Polaris.AI Programming Contest 2025（AtCoder Beginner Contest 429）.
- Contest URL: https://atcoder.jp/contests/abc429
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20251025T2100&p1=248
- Duration: 100 minutes
- Writer: math957963, sounansya, physics0523
- Tester: yuto1115, MMNMM
- Rated range: ~ 1999
- The point values: 100-200-300-425-450-525-625
We are looking forward to your participation!
ATC is not Simple.
good bro
Why is the announcement downvoted before the contest starts?
Why the point values of ABC don't always the same？
wdym
ohh
GL&&HF!
Is the new judge system being launched from today?
Doesn't look like so.
see this:https://atcoder.jp/posts/1586
111
As a participate, SHAW!
problem G is so hard
org
Can anyone tell me why my solution is giving wrong
Submission Link
Most probly the issue lies that while storing the state in the set as (dist, par)
and then updating the top two min distances inside the dfs, it does not save from which sourse ('S'), the first minimum dist came from so it may happen that both the min distances may have originated from the same source 'S' . Although I dont have the proof, it would be heplful if someone explains here .
PS : I guess i had the same issue im my implementation and making the above changes got an AC
Here are the submission links :
WA Submission :- I didt track the sourse of first min dist https://atcoder.jp/contests/abc429/submissions/70496319
AC Submission : https://atcoder.jp/contests/abc429/submissions/70498043
The prev Node from which the curr Node is coming should not matter as per my approach as it is a set and dist insert is 0 at start and even if i find two path to reach a node only the closest from s will come first and it does not matter if 2 or 3 paths are there.
I want to know where this thing is failing.
As I said your implementation did not store the source of first minimum hence it may happen that first two min dist are from same source
Your Code fails on this case :-
For Node 4 the ans will d(1, 4) + d(4, 7) = 2 +3 = 5 but your code gives 4
Got it thanks
What is E? I have no idea how to find $$$k$$$ shortest distances to some set of vertices.
What I managed to AC:
I have no idea:
And F also seemed difficult btw. Only good observation that for all vertical line you either cross it 1 or 3 times.
OK F really stupid... If you cross vertical line 3 times you could've crossed it once and it is strictly better. After that it's clear that you kind of want prefix and suffix achievability DP's and merge them together on updates — that's a classic dp-in-segtree trick.
This does not seem correct for E. I instead store for each vertex the 2 shortest paths to a safe vertex (where 2 safe vertices are different). I propagate this throughout the graph using a priority queue.
Maybe try replacing your queue with a priority queue, and keep k=2? Here is my submission https://atcoder.jp/contests/abc429/submissions/70442777
Edit: I'm unsure why priority queue was needed instead of just queue like BFS since distances are 1, but I originally had WA until I replaced it.
We can do it with queue too. My Submission
Ok this is kind of the same what I had in mind when coding my first submission https://atcoder.jp/contests/abc429/submissions/70450122, but instead of checking = with INF, i just was applying min= in array of distances. Still dont understand what's the difference. Apparently I don't know BFS...
I had same approach in mind but thought it will get TLE and didn't code it
I know no one really cares at this point but i figured out the difference between AC and not AC in E:
because when you do vertices you propagate both best and second to best distance and break bfs order for some updates that wait in the queue. And probably you can override something while doing so. Because of that, doing =inf check in bfs seems to not work at all, and min= with multiple repetitions seems to work good enough to be AC with some random shenanigans.
Had similar approach with small variations
did multi source bfs from s and marked there dist as very INF then did ms-bfs and calculated all possible distance coming on d and selected the smallest 2.
can you help me in figuring out what is wrong .
submission: https://atcoder.jp/contests/abc429/submissions/70453717
G is a very standard problem, but I never know the specific approach.
To be precise, I know it is an $$$O(\sqrt{M})$$$ algorithm, but I cannot write it correctly.
Don't know why, but I found d was easy in visualizing, but hard to implement. Took me 3 attempts.
Yeh it took one wrong answer for me but finally get AC in last
good round. E is simple, but F seems hard and I don't know how to solve it.
Don't put mysterious math problem at G
OMG! I wonder whether there can be a Kind-hearted person who worked out problem G tell me how to work out it.
G is so hard... It's so lucky that I've read the blog before, or else it's impossible for me to solve G :)
problem F is hard if you don't know such trick.it took me 1h but I couldn't solve it...
which trick
I think we can put classic questions like F on the practice list instead of in the competition?
A good contest is meant to enhance thinking and skills, not to expand knowledge.
what is the solution for F ?
I used a segment tree to solve it. I put matrix
data[3][3]in each node,data[j][k]means the shortest distance to travel from rowjof the segment’s left column to rowkof its right column. When merging two segments, I combined their matrices usingdata[j][k] = min( left.data[j][t]+right.data[t][k]+1 ).You can refer to my solution
Sorry for everyone.I said some negative comments yesterday.
Now I'm staying calm. The quality of this contest is good, and a good contest is also meant "Learning new knowledge".
I sincerely regret my mistake in yesterday's comment, can everyone forgive me once?
You're not wrong. There's too many classical tricks or templates (even problems already appeared on other onlinejudges) in ABC. It's bad for the quality of contests.
so difficult!
Why can't I submit after the contest?
what's the solution of E?i spent nearly 1h to think it but failed at last...
Why are there not solutions？When are there?Or who could teach me E?