atcoder_official's blog

By atcoder_official, history, 11 days ago, In English

We will hold HHKB Programming Contest 2025(AtCoder Beginner Contest 388).

We are looking forward to your participation!

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

»
11 days ago, # |
  Vote: I like it -6 Vote: I do not like it

First**

»
10 days ago, # |
  Vote: I like it +18 Vote: I do not like it

How to turn off the sound on contest page?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just refreshed the page and it turned off

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Mute PC:) or you can mute google chrome or any browser by (win+G)->Audio. i don't know about macbook.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what sound?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get 900

»
10 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Cake walk A-E.

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Give a thumbs up to ABC this time! The question is very concise.

»
10 days ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

I think D is much harder then E.

»
10 days ago, # |
  Vote: I like it -25 Vote: I do not like it

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 ?

»
10 days ago, # |
  Vote: I like it +2 Vote: I do not like it

D was really educational on how to use Difference Array Dynamically with prefix sums which something i never encountered

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Kindly share your approach in Problem D and E.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Only $$$8$$$ contestants solved all the problems without any penalties. The symbol $$$\color{red}{(x)}$$$ is almost everywhere!

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to do E? welp

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Binary search for the answer

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your approach?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          how would you pair the elements optimally for any given m? For example for 2 4 5 9 the matching is weird.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    start from pairing the middle one to the smallest one and keep on doing this

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it with Binary Search, just search for the maximum length of prefix and suffix for which the condition holds

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the pairing algo for a given prefix and suffix length

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use two pointer.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain E?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Try this example: 1 3 5 9. Greedily pairing 1 and 3 does not give optimal answer.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Solve it for $$$N \le 10^6$$$. Then think which cells are reachable if you have a big gap between bad segments.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain how to cover the big gaps? I couldn't figure out how

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
          Rev. 2   Vote: I like it +5 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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!

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
10 days ago, # |
  Vote: I like it +28 Vote: I do not like it

problem E is the same as this one:

https://codeforces.net/problemset/problem/372/A

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anybody else get WA on 2 tests in F? How did you fix it

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    So much can go wrong in this problem, but I would first look into the case $$$a = b$$$.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Happened to me. Maybe check if you're handling $$$A=B=1$$$ correctly.

»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Liked the contest. Thanks !

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone HELP debug this solution of F?

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

void solve(){
	int n;cin>>n;
//	int arr[n];
	multiset<int>s;
	for(int i=0;i<n;i++){
		int val;cin>>val;
		s.insert(val);
	}
     int ans=0;
     while(s.size()){
		
		
		// check if 2*val is there or not 
		auto it = lower_bound(s.begin(),s.end(),*s.begin()*2);

		if(it!=s.end()){
			 
			//cout<<"removing "<<*beginIt<<" and "<<*it<<'\n';
			s.erase(s.begin());
			s.erase(it);
			
			ans+=1;}

		else{
             // no 2*val is ofund
			 break;
		}

		 
	}
	cout<<ans;

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	// int a, b, c; cin >> a >> b >> c;
	// cout << "The sum of these three numbers is " << a + b + c << "\n";
}

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

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

void solve(){
	int n;cin>>n;
//	int arr[n];
	multiset<int>s;
	for(int i=0;i<n;i++){
		int val;cin>>val;
		s.insert(val);
	}
     int ans=0;
     while(s.size()){
		
		
		// check if 2*val is there or not 
		auto it =s.end();
		--it;
		int val = *it;
		auto it2 = lower_bound(s.begin(),s.end(),val/2);

		if(it2!=s.end()){
			 if(*it2==(val/2)){
				 s.erase(it);
				 s.erase(it2);
				 ans+=1;
			 }else{
				   //check if 
				   if(it2==s.begin()){
                     // all are bigger than half of it
					 s.erase(it);
				   }else{
					   --it2; // as lower bound points to at leas tgreate rthan val/2
					    s.erase(it);
				 s.erase(it2);
				 ans+=1;

				   }
			 }
		}
        else{
             // no 2*val is ofund
			 break;
		}

		 
	}
	cout<<(ans);

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	// int a, b, c; cin >> a >> b >> c;
	// cout << "The sum of these three numbers is " << a + b + c << "\n";
}

Any help would be grateful

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    my approach was very similar but consider the case 2, 5, 6, 10

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This fails for the case:

    7
    1 1 2 2 4 4 4
    

    Expected output is 3.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Fkd up on D clutched on E . D was so annoying

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont understand why my upper bound solution doesn't work for C.

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    
    std::vector<int> v(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int cnt = 0;
    for(int i = n - 1; i >= 0; i--) {
        int k = v[i] / 2;
        auto upper = std::upper_bound(v.begin(), v.end(), k);
        if(upper == v.end()) break;
        if(upper != v.begin()) upper--;
        
        if(*upper <= k)
            cnt += std::distance(v.begin(), upper) + 1;
    }
    std::cout << cnt;
    return 0;
}
  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you should also make the cnt as long long.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the great contest

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved problem G 10 minutes after the contest ended

»
10 days ago, # |
  Vote: I like it +27 Vote: I do not like it

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$$$...

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem F and G are good

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks I got this approach my comment was to know how my approach would be implemented

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve G?

»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we first check which points from [l — E, l — 1] can be reached from points belonging to lvr

    How to check this ?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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].

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C with two pointer WA??? :(

#include <bits/stdc++.h>
using namespace std;
#define MAX 500000


int a[MAX + 1];


int solve(int l, int r) {
    int start = r, end = r, cnt = 0;
    while (start >= l && end >= l) {
        if (a[start] * 2 > a[end]) {
            start--;
        } else {
            cnt += (start - l + 1);
            end--;
        }
    }
    return cnt;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n);
}
»
8 days ago, # |
  Vote: I like it -19 Vote: I do not like it

atcoder is overrated

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the english editorials be released for this contest?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be the editorial in english??