We will hold HHKB Programming Contest 2025(AtCoder Beginner Contest 388).
- Contest URL: https://atcoder.jp/contests/abc388
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250111T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, cn449, physics0523
- Tester: sotanishy, toam
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-550-575
We are looking forward to your participation!
First**
How to turn off the sound on contest page?
I just refreshed the page and it turned off
Not working for me.I moved to the japanese version and pause the youtube video there and reverted back to english version,no sound now.
Mute PC:) or you can mute google chrome or any browser by (win+G)->Audio. i don't know about macbook.
what sound?
Hope to get 900
Cake walk A-E.
Give a thumbs up to ABC this time! The question is very concise.
I think D is much harder then E.
Why D and E giving TLE and RE tried using difference array and BFS technique. BFS tried to optimize using DP but failed, why man ?
Ask after contest end.
Difference array is suffice to get AC and E is too cute to talk now
D was really educational on how to use Difference Array Dynamically with prefix sums which something i never encountered
Kindly share your approach in Problem D and E.
For D each person will have to give something to next indices and he will be getting something from the previous indices
the amount he will give will be give=min(arr[i],n-i-1) and add "1" in the range (i+1,i+give) and after that each time you have to update your new value based on your previous congratulatory gift and with this new value repeat the above process
for range adding use Difference Array and for updating the new value based on previous congratulatory gift use prefix sums
below is my implementation https://atcoder.jp/contests/abc388/submissions/61606087
I have a better approach for D, maintain a multiset which will contain indices till which a particular guy can distribute his stones once he is adult.
So if i am at an indice i: i first keep popping of indices from mutliset until ms.begin()>=i, after which the total stones ith guy has: ms.size()+what he started with, now you find until what indice he can distri a stone: min(n-1,total stones), and push that index in multiset.
it was kinda an event based approach.
can you share you code?
https://atcoder.jp/contests/abc388/submissions/61567810
Only $$$8$$$ contestants solved all the problems without any penalties. The symbol $$$\color{red}{(x)}$$$ is almost everywhere!
How to do E? welp
Binary search for the answer
Can you explain your approach?
Assume some m <= n//2. Check if first m elements can be mapped with last m elements of the given array. If yes, k should be >= m. Else k should be < m. Binary search for the maximum m.
how would you pair the elements optimally for any given m? For example for 2 4 5 9 the matching is weird.
You only have to map the first m elements with the last m elements in order. If (i, j) is a valid pair, then (i, j + 1) is also a valid pair.
start from pairing the middle one to the smallest one and keep on doing this
I did it with Binary Search, just search for the maximum length of prefix and suffix for which the condition holds
Can you explain the pairing algo for a given prefix and suffix length
if you have fixed a length (lets say m) then we will try to pair similar type of elements from the prefix and suffix i.e maximum of prefix (MaxP) with maximum of suffix (MaxS) ..and so on. this works because lets say 2*MaxP > MaxS, then there is no way that another element from suffix could support MaxP.
Use two pointer.
E is too easy for E and the difficulty gap between E and F is not reflected in the point value at all. F is a great task btw.
Can you explain E?
Binary search the answer. To construct x double-cakes greedily take first smallest cakes for the top part and x largest cakes for the bottom part.
I tried greedy by iterating from left to right and using a multiset ,if for any index j, the smallest element in multiset satisfies the condition i just pair them up.I had the idea to binary search but then why not greedy? So can you tell me why binary search if we need to just pair them up greedily?
Try this example: 1 3 5 9. Greedily pairing 1 and 3 does not give optimal answer.
Can you explain your approach?
How did you solved F ? I figured out that if there exist a range whose size is greater than the maximum step i can take , then the answer should be No
Solve it for $$$N \le 10^6$$$. Then think which cells are reachable if you have a big gap between bad segments.
Can you explain how to cover the big gaps? I couldn't figure out how
Handle $$$a = b$$$ separately, now assume $$$a < b$$$. Consider only steps $$$a$$$ and $$$a + 1$$$. With two such steps, you can reach cells $$$2a, 2a+1, 2a+2$$$. With three such steps, you can reach cells $$$3a, 3a+1, 3a+2, 3a+3$$$. Try generalizing this before reading the next paragraph.
With $$$a$$$ such steps, you can reach cells $$$a^2, a^2 + 1, a^2 + 2, \ldots, a^2 + a$$$. With $$$a + 1$$$ such steps, you can reach cells $$$a^2 + a, a^2 + a + 1, \ldots a^2 + 2a + 1$$$. Notice how the two ranges overlap. From here on* all cells are reachable. Therefore, you can 'skip' every gap of length $$$\ge a^2 + 20$$$.
What exactly it means to 'skip' a gap depends on how you handle small gaps. I used a BFS, so skipping means pushing $$$l-20, l-19, \ldots, l-1$$$ into the queue. Submission, LL244-249. A 'skip' may translate into code differently if you use DP.
Alternatively, you could apply the Chicken McNugget Theorem with $$$n = a$$$, $$$m + a + 1$$$ to immediately conclude that all numbers $$$\ge a (a+1) - a - (a+1) + 1 = a^2 - a$$$ are reachable for a slightly tighter bound.
Yo, that's a wonderful explanation considering it makes me feel like I could have come up with it if I tried more. Thank you!
My solution for problem F:
If the transition between two reachable squares passes a bad square, then it need to have an exact number between $$$A$$$ and $$$B$$$. We will now focus on the squares within a good segment.
For each good segment, if N is reachable, it must use one of the first B squares, same for the last B squares. So we only need to consider those squares.
The problem now is how to transit if the segment is large. If $$$A=B$$$, then just check if the distance is a multiple of $$$A$$$. Now consider $$$A<B$$$, let $$$a=A,b=A+1$$$, observe $$$ax+by=c, c>ab-\epsilon$$$ always have a positive int solutions for $$$x,y$$$. So for steps>400 it's always possible, for the smaller range we can build a lookup table.
problem E is the same as this one:
https://codeforces.net/problemset/problem/372/A
Did anybody else get WA on 2 tests in F? How did you fix it
So much can go wrong in this problem, but I would first look into the case $$$a = b$$$.
Happened to me. Maybe check if you're handling $$$A=B=1$$$ correctly.
Liked the contest. Thanks !
Can anyone HELP debug this solution of F?
Why it is giving wrong answer
I am just finding the pair element for the element present at the beginning and remove the first element and the paired element , i am going to do this until s.is exhausted() or i can not find paired element for my current element which indicates that if there is no elemnet for me then all the lements after me is bigger than me then for them also there is no elment in the set.
Now i edited it to make it as follows:-
Traversing from the last of the set and finding the paired element for it .
If found remove last element and paired one
IF not found remove last element Do it until I have elements in the set
Any help would be grateful
my approach was very similar but consider the case 2, 5, 6, 10
This fails for the case:
Expected output is 3.
If you are wondering how to solve, you should binary search for the answer, and to check for some k, you should take first k elements and find pair for every one of them. My solution
Fkd up on D clutched on E . D was so annoying
I dont understand why my upper bound solution doesn't work for C.
you need to remove this condition if(upper == v.end()) break; because if the upper == v.end that's mean any value in v works,
and you don't need to sort the array because it's sorted in the input.
you should also make the cnt as long long.
The problem is actually long long...
thanks for the great contest
I solved problem G 10 minutes after the contest ended
how to solve G? i know i have to use SGT,but im stuck what to store in the SGT
distance from index $$$i$$$ to the index $$$j$$$ which is the first index where $$$a[j]/a[i] \ge 2$$$
Can u please elaborate ur approach
https://atcoder.jp/contests/abc388/submissions/61610027
Why E and G have (basically) same statements but different constraints? I solved G first, then got RE on E because of keeping the size of arrays $$$2\times10^5$$$...
Problem F and G are good
In D first make every element give to its right and take it from left, some values will be negative now then just iterate and every negative value a tells to reduce 1 from last a elements. ex 2 9 1 2 0 4 6 7 1 5 make it -7 2 -4 -1 -1 5 9 12 8 14 then first make last 7 elements reduce by 1-> 0 2 -4 -2 -2 4 8 11 7 13 now for 2 do nothing now for -4 make last 4 elements reduce by 1 and same until last index it gives correct answer but i am not getting how to implement this in linear time, try to help
let me rephrase the problem to make explanation easy
there are $$$n$$$ person
let person $$$i$$$ has $$$x$$$ coins
person $$$i$$$ will give his coins from person $$$i$$$ to $$$i + a[i]$$$
consider an array $$$b$$$
do $$$b[i + 1] += 1$$$ and $$$b[i + x + 1] -= 1$$$
now we can calculate $$$x$$$ (coins of person $$$i$$$) $$$ = a[i] + b[1] + b[2]..b[i]$$$
$$$b[i] + b[2]..b[i]$$$ $$$=$$$ $$$prefb[i]$$$
for better understanding you can search scanline technique.
Thanks I got this approach my comment was to know how my approach would be implemented
can anyone explain in G why are we checking for the max value of j- i; such that a[j]>=2*a[i] and j>i? i came across one explanation that said that L+K−1+(max(j-i) for all i<L+mid and i>=L) <=R, but why is it so?
from range $$$L..R$$$ we can choose on $$$k$$$ pairs if and only if
for each $$$i$$$ from $$$L$$$ to $$$L + k - 1$$$
$$$2 * a[i] <= a[R - (L - i)]$$$ holds, that is if we can make pairs from first $$$k$$$ elements to last $$$k$$$ elements
let $$$j$$$ be the nearest index to $$$i$$$ such that $$$2 * a[i] <= a[j]$$$
so we can choose $$$k$$$ pairs if for all $$$i$$$ in $$$L..L + k - 1$$$
$$$j <= R - (L - i)$$$ holds
$$$j - i <= R - L$$$
$$$max(j - i)$$$ for all $$$i$$$ should be $$$<= R - L$$$
How to solve G?
I think problem F is really a brain storm, and thank you atcoder team for providing such a nice problem!
I solved it as follows. I set E = 22, and at first have lvr = [1]. Then, for each given interval [l, r], we first check which points from [l — E, l — 1] can be reached from points belonging to lvr, and this can be done by some simple mathematical computing. We denote these points as xvr. Next, we can use BFS to check which points from [r + 1, r + E] can be reached from xvr. Then, we update lvr according to these points, and move on to the next given interval.
The key idea is that for two given intervals, we only care about some of their neighboring points, at most 22(maybe 20), and for other points, we should deal with them by mathematical computing quickly.
How to check this ?
This can be done as follows. Assume that we have lvr=[lvr[1],lvr[2],..], (remember that lvr has at most E = 22 elements), and for each integer belonging to [l — E, l -1], denoted as y[j], we enumerate every element of lvr, and check whether there is some p, so that, lvr[i] + p * a <= y[j] and y[j] <= lvr[i] + p * b. As long as there is at least one valid value of p, then we can reach y[j].
Problem C with two pointer WA??? :(
atcoder is overrated
Will the english editorials be released for this contest?
Will there be the editorial in english??