We will hold AtCoder Beginner Contest 369.
- Contest URL: https://atcoder.jp/contests/abc369
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240831T2100&p1=248
- Duration: 100 minutes
- Writer: yuto1115, math957963, ynymxiaolongbao
- Tester: toam, sounansya
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-500-600
We are looking forward to your participation!
this round like div.3 or div.4 at codeforces?
Like Div. 2.5, but the problems are more classical.
Let's go, can't wait for this contest!
Omg the first time I solve all 7 problems!
problem E was great, but implementation was long
Not sure if reconstructing the path in F added anything to the problem, but it wasn't too bad I guess
i agree lol, i spend like 10 minutes to implement the "counting" part and like 15 minutes to implement "back-tracking" part
Was F some sort of 2D Segment Tree?
You can do it with a regular segtree if you process all coins with lowest rows and rightmost columns first
you can also use fenwick tree, no need to compress the coordinate :D
Oops, somehow I tricked myself into thinking that coordinates are up to $$$10^9$$$ lol (and it wouldn't even make sense then to try and output the whole path in a non-compressed manner)
I liked the problem E very much.
how can I solve G? anyways, why have there been no official tutorials in English recently?
This problem is similar to https://codeforces.me/problemset/problem/1615/E, but we only have weights on edges. Main idea is greedily expand the chosen set of vertices with such vertex that maximizes distance to current set of vertices. And when we add some vertex, we also need to put all vertices to set on path btw set and chosen set. From start set contains only root.
Thanks!
How to maintain the tree and find the vertex that maximizes distance from the chosen vertices fast?
1976F - Remove Bridges
Well, you can use segtree, where you store for each vertex a length of the path from it to chosen set. And when you add some vertex u to set, you should decrease all lengths of such v that in subtree of u(it can be done via euluer tour). We also need to get maximum over all vertices(segtree allows us to do it). Now we know that each vertex will be modified exacly one time, then our compexity will be O(nlogn).
One dfs and std::sort
Thanks to you both!
I saw 1976F but forgot about it entirely. Exactly what I needed.
Don't English tutorials always arrive slightly late? I couldn't spot any recent rated contests without an editorial in English.
Oh I see it, in the past it appeared as soon as the contest ended.
E was exhausting, great question.
F**k ABC,G has an original problem.
Again!!!!
how to solve C I didn't got a single idea which was working brute was only which I could think of and d also anyone if someone can help me please
The logic is to find all contiguous subarrays that form an arithmetic progression (AP). For each starting index l, the code finds the longest subarray ending at r where the difference between consecutive elements is constant. It then counts the number of valid subarrays within this range and accumulates the total count. This is done by extending the subarray as far as possible while maintaining the AP property and calculating the number of subarrays for each segment. The process is repeated for each possible starting index in the array.
so we need to find the subarrays I was stuck in finding subsequences :( shittt I could have done it easily
can anyone please tell how to practice dp and trees,graphs question like i can solve dp of difficulty till 1500 and above it its diffcult.
You can start from here. It will guide you.
atcoder_official Hey there. I got a -89 rating change in ARC183, but I didn't even participate in the contest (was only registered). Can you look this up? I'm sure it might've been a mistake. My atcoder username is "Bruteforcekid"
You would be rated even if you just register and didn't submit anything, so it's better to register right before the contest next time :)
is there any other solution to E other than brute force? like if we a problems where we don't have any queries. we just have to pass some bridges but the number of bridges can be large(large enough to not bruteforce maybe). How will we solve that version of this problem?