atcoder_official's blog

AtCoder Beginner Contest 470 Announcement
By atcoder_official, history, 4 weeks ago, In English

We will hold JPRS Programming Contest 2026#2 (AtCoder Beginner Contest 470).

We are looking forward to your participation!

  • Vote: I like it
  • -26
  • Vote: I do not like it

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope I can solve A to D.

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

I am from India, so I can participate in this contest, right?

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

I hope I can solve D to F.

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

I hope that I can solve 5 problems, even 6! Of course, good luck to everyone!

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

I am Chinese,I can fly!!!

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

I hope I can solve A to D.Good luck to me,and good luck to everyone!

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

This is my first time to participate ABC contest,hopefully I can solve A to D,good luck to everyone!

I am Chinese,I can fly!!!

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

I am Chinese,I can fly!!!

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

I hope I can solve D ~ E

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

I hope I can solve A to E.

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

I hope to do the E question.

(cross out)(I'm Chinese, I can fly.)

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

I hope I can solve A to F.

And, I am Chinese, I can fly!!!

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

I hope I can solve A to B.

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

C is much harder than regular C (i skipped it and did D)

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

I think the difficulty of problem C is more than 600.

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

After many days, I finally came back to play the game.

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

rubbish task C, it should be task D. Downvote.

→ Reply
»
4 weeks ago, hide # |
← Rev. 2  
Vote: I like it -18 Vote: I do not like it

why D is EZer than C???? and I am Chinese,I can fly!!!

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

Why C is too hard

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

Good problems, but I took too long to solve $$$C$$$ and $$$D$$$.

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

Are we sure C was actually a C problem??

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

How is the answer for testcase 2 of $$$F$$$ = 18?

{1, 2, 3} and {4, 5, 6} are the components.

{1, 2, 3} = 3! / (1 * 1 * 1) = 6 permutations {4, 5, 6} = 3! / (1 * 1 * 1) = 6 permutations

6 * 6 = 36 is the answer?

→ Reply
»
4 weeks ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

C was so weird, it was a constraint analyzation problem, a pruned brute force works.

    cint(n, q);
    vi a(n);
    unordered_set<int> ind;
    int xr = 0;
    while (q--) {
      cint(type);
      if (type == 1) {
        cint(x);
        xr ^= a[x - 1];
        if (a[x - 1] == 0) {
          ind.insert(x - 1);
        }
        a[x - 1]++;
        xr ^= a[x - 1];

      } else {
        vector<int> ele;
        for (auto it : ind) {
          xr ^= a[it];
          if (a[it] == 1) {
            ele.push_back(it);
          }
          a[it]--;
          xr ^= a[it];
        }
        for (auto it : ele) {
          ind.erase(it);
        }
      }
      cout << xr << "\n";
    }
  }
→ Reply
  • »
    »
    4 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    People who doesn't even know what is a time complexity and who can calculate time complexity very well could solve it very easily. It's so funny that you need to be low skilled or high skilled to be able to solve this task, and if you wil be in the middle you will struggle a lot.

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

Rubbish C and hard E.Trash round.Downvote it please.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

C was OK I think. But G is too classical and E<F<G is unacceptable.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I feel that question G is quite similar to this one.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I dont know if this contest has tester or not, since its prepared by JPRS. But the problem position isnt sorted from easy to hard. Looking at the distribution of the solved number for each problems, its clear that D < C and F < E, not considering E < C because people can take too much time solving C and not looking at E for once.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

In fact, we might be overthinking C. If you know that things like 'std::set' or 'std::vector' can optimize away the empty values (**only storing the ones that exist**), then you can just directly simulate it according to its idea and it works. It looks terrifyingly like O(n^2), but in reality it's only O(q)

I deal with it at 1h 20min!!!

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

plz ban zyf2026,his code is actually from ai

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

G is HDU4747.

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

Anyone explain problem C ...

→ Reply
  • »
    »
    4 weeks ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +3 Vote: I do not like it

    if you maintain what positions have positive values and iterate over those positions when an operation of the second type happens, update XOR, and remove the values that become 0 from this list, for each iteration you do you cancel one operation of the first type, so basically operations of the first type will be applied O(q) times and will be cancelled O(q) times

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

      my code:

      int n, q;
cin >> n >> q;
vector<int> a(n);
vector<int> changed;
int XOR = 0;
for (int i = 0; i < q; ++i) {
	int type;
	cin >> type;
	if (type == 1) {
		int j;
		cin >> j;
		--j;
		XOR ^= a[j];
		XOR ^= ++a[j];
		if (a[j] == 1) {
			changed.push_back(j);
		}
	}
	else {
		for (int j = (int)changed.size() - 1; j >= 0; --j) {
			int idx = changed[j];
			XOR ^= a[idx];
			XOR ^= --a[idx];
			if (a[idx] == 0) {
				swap(changed[j], changed.back());
				changed.pop_back();
			}
		}
	}
	cout << XOR << '\n';
}
      → Reply
»
4 weeks ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

fuck the C problem

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

Worst performance, i couldn't even solve C. :(

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

ai can do this. The editor says that we can use set to protect the array of index which > 0. At the same time,we can protect the XOR sum.ai says that we can use 0/1 trie(the knowledge of e or upper one), or fenwick tree+protect the bits array(the knowledge of f or upper one).In a word,f**k the people who made this problem. I will share the 0/1 trie code which coded by deepseek. 

Your code here...
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_BIT = 19; 
struct Trie {
    struct Node {
        int ch[2];
        int cnt;
        int xor_val;
        Node() : ch{0, 0}, cnt(0), xor_val(0) {}
    };
    vector<Node> nodes;
    int root;
    Trie() {
        nodes.reserve(12000000);
        nodes.emplace_back();
        nodes.emplace_back(); 
        root = 1;
    }
    void update(int u) {
        int l = nodes[u].ch[0], r = nodes[u].ch[1];
        nodes[u].cnt = (l ? nodes[l].cnt : 0) + (r ? nodes[r].cnt : 0);
        nodes[u].xor_val = 0;
        if (l) nodes[u].xor_val ^= (nodes[l].xor_val << 1);
        if (r) nodes[u].xor_val ^= ((nodes[r].xor_val << 1) | (nodes[r].cnt & 1));
    }
    void insert(int u, int bit, int val) {
        nodes[u].cnt++;
        if (bit == MAX_BIT) return;
        int b = (val >> bit) & 1;
        if (!nodes[u].ch[b]) {
            nodes.emplace_back();
            nodes[u].ch[b] = nodes.size() - 1;
        }
        insert(nodes[u].ch[b], bit + 1, val);
        update(u);
    }
    void erase(int u, int bit, int val) {
        nodes[u].cnt--;
        if (bit == MAX_BIT) return;
        int b = (val >> bit) & 1;
        erase(nodes[u].ch[b], bit + 1, val);
        update(u);
    }
    void sub_all(int u, int bit) {
        if (u == 0 || nodes[u].cnt == 0) return;
        if (bit == MAX_BIT) return;
        swap(nodes[u].ch[0], nodes[u].ch[1]);
        if (nodes[u].ch[1]) sub_all(nodes[u].ch[1], bit + 1);
        update(u);
    }
    void remove_all_zero(int u, int bit) {
        if (u == 0 || nodes[u].cnt == 0) return;
        if (bit == MAX_BIT) {
            nodes[u].cnt = 0;
            nodes[u].xor_val = 0;
            return;
        }
        remove_all_zero(nodes[u].ch[0], bit + 1);
        update(u);
    }
    int xor_sum() const {
        return nodes[root].xor_val;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> s(N + 1, -1);
    int offset = 0;
    Trie trie;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            int v = (s[x] == -1) ? 0 : max(0, s[x] - offset);
            if (v > 0) trie.erase(1, 0, v);
            int nv = v + 1;
            trie.insert(1, 0, nv);
            if (v == 0) s[x] = offset + 1;
            else s[x]++;
        } else {
            offset++;
            trie.sub_all(1, 0);          
            trie.remove_all_zero(1, 0);  
        }
        cout << trie.xor_sum() << '\n';
    }
    return 0;
}
→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hava a better solution then official about Problem D: My solution link

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

Every time there is a competition, I can see several users with black usernames on the first page of the leaderboard, and after a while, they disappear.

I hope that situations like the AI Beat Contest will not occur in the future. However, some people still try to use AI even though they know the chances of evading detection are slim.

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

I feel that C is harder than D ， does anyone agree? ：(

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

in my view, C is odd for its placement, E is verbose and hard to grasp, and G is simply too typical; the others are reasonably good though.

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

such nice problems, especially C,D

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

I think that C>>>>>>>>>>>>>>>>>>>>>>>>D

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

F > G > E hmmm....

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I quickly completed problems A to D and started working on F, but I forgot to check the modulo answers, so I ultimately failed F

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

My first G, although it took me 97 minutes :)

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

C is quite hard to think, I thought like that,would store indices of >=1 , but did not implement it, because I thought that it would give tle , because iterate over each value of index

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

I believe I can solve A to E in future.And if I am lucky,I can get into my dream high school by competitions! And good luck to everyone who reads this comment! Also,I am a Chinese,I can fly!!!

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

I C I F

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

No cheating but accounts were banned. :(

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

The C solution code of 0/1 trie coded by real human, me!

#include<bits/stdc++.h>
//#define int long long
#define rk(i,l,r) for(int i = l;i<=r;++i)
#define l(x) x<<1^inv(p)
#define r(x) (x<<1|1)^inv(p)
using namespace std;
const int N = 5e5+10,M=20;
signed n, q,op,x,dx,a[N];
struct trie{
	signed v=0,cnt=0;bool inv=0;
	#define v(x) tr[x].v
	#define cnt(x) tr[x].cnt
	#define inv(x) tr[x].inv 
}tr[N*M];
void update(int p)
{
	cnt(p)=cnt(l(p))+cnt(r(p));v(p)=0;
	if(cnt(l(p)))v(p)^=v(l(p))<<1;
	if(cnt(r(p)))v(p)^=(v(r(p))<<1)|cnt(r(p))&1;
}
void cg(int p, int u, int v, int step)
{
	cnt(p)+=v;
	if(step>=19)return;
	int b = (u>>step)&1;
	cg(p<<1|(b^inv(p)),u,v,step+1);
	update(p);
}
void sub1(int p, int step)
{
	if(step>=19)return;
	if(cnt(l(p)))sub1(l(p),step+1);
	inv(p)^=1;
	update(p);
}
void re0(int p, int step)
{
	if(step>=19){cnt(p)=v(p)=0;return;}
	if(cnt(p))re0(l(p),step+1);
	if(cnt(p))update(p);
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	while(q--)
	{
		cin>>op;op--;
		if(op)sub1(1,0),re0(1,0),dx++;
		else
		{
			cin>>x;
			int k= max(0,a[x]-dx);
			if(k)cg(1,k,-1,0);
			cg(1,k+1,1,0);
			if(!k)a[x]=dx+1;
			else a[x]++;
		}cout<<v(1)<<'\n';
	}
	return 0;
 }
→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i think this C is hard i used 1 min to solve A,3 mins to solve B,but used 40 mins to solve C MIND YOU，I'm Chinese i can fly

→ Reply