atcoder_official's blog

AtCoder Beginner Contest 429 Announcement
By atcoder_official, history, 6 months ago, In English

We will hold Polaris.AI Programming Contest 2025（AtCoder Beginner Contest 429）.

We are looking forward to your participation!

  • Vote: I like it
  • +47
  • Vote: I do not like it

»
6 months ago, hide # |
 
Vote: I like it -22 Vote: I do not like it

ATC is not Simple.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -22 Vote: I do not like it

good bro

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Why is the announcement downvoted before the contest starts?

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Why the point values of ABC don't always the same？

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

GL&&HF!

→ Reply
»
6 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Is the new judge system being launched from today?

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

111

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

As a participate, SHAW!

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

problem G is so hard

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

org

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my solution is giving wrong

Submission Link

→ Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 months ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        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 :-

        7 7
1 2
1 3
2 4
3 4
4 5
5 6
6 7
SDDDDDS

        For Node 4 the ans will d(1, 4) + d(4, 7) = 2 +3 = 5 but your code gives 4

        → Reply
»
6 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

What is E? I have no idea how to find $$$k$$$ shortest distances to some set of vertices.

What I managed to AC:

  • store top-$$$k$$$ optimal distances for different points (d + color)
  • do bfs where you push different colors altogether, and do it levit-style, ie until everything is stabilized
  • when you have more than k distances stored, do prune
  • (might be not important) remember if you removed something at some stage to consider when calculating answer
  • (important) shuffle original queue
  • (important) take k = 10 and not k = 5 or k=2, otherwise WA

I have no idea:

  • Why it works in time
  • Why different $$$k$$$ matters in terms of WA — like I drop something that should be used later?

And F also seemed difficult btw. Only good observation that for all vertical line you either cross it 1 or 3 times.

→ Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +14 Vote: I do not like it

    I know no one really cares at this point but i figured out the difference between AC and not AC in E:

    • queue has vertices: not AC
    • queue has {vertex, dist, root}: AC.

    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.

    → Reply
»
6 months ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

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.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Don't know why, but I found d was easy in visualizing, but hard to implement. Took me 3 attempts.

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

good round. E is simple, but F seems hard and I don't know how to solve it.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Don't put mysterious math problem at G

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

OMG! I wonder whether there can be a Kind-hearted person who worked out problem G tell me how to work out it.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like 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 :)

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

problem F is hard if you don't know such trick.it took me 1h but I couldn't solve it...

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -19 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    what is the solution for F ?

    → Reply
    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      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 row j of the segment’s left column to row k of its right column. When merging two segments, I combined their matrices using data[j][k] = min( left.data[j][t]+right.data[t][k]+1 ).

      You can refer to my solution

      → Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

so difficult!

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why can't I submit after the contest?

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what's the solution of E?i spent nearly 1h to think it but failed at last...

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why are there not solutions？When are there?Or who could teach me E?

→ Reply