Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

atcoder_official's blog

By atcoder_official, history, 4 weeks ago, In English

We will hold AtCoder Beginner Contest 391.

We are looking forward to your participation!

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

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

The first AtCoder race in this lunar year!

Good luck!

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

    As the weakest one of all the pigeons, good luck!

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

Good luck and have fun!

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

Good luck and have fun!

Now it is Spring Festival in China. Happy new year!

»
4 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

this contest was brutal

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Is F some kind of a well-known problem or it's just really simple? Didn't solve it, but 1k+ submissions is quite a lot for F.

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

can anyone explain the solution for E?

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

    Create a dp and use recursion , the recursion takes l and r as input (the left and right indices within which the answer is to be computed) and then returns the max appearing element in that range and how many elements need to be swapped to reverse that max appearing element , if l + 1 == r at any stage , meaning there is only one element in the string , then what should be the answer ?? Clearly, the max appearing element is the s[l] — '0' (the only element left in the string) and to reverse this max element we need to reverse this element itself , so the min number of elements to reverse is 1 , for example if (l = 1 , r = 2) at any stage then we are only trying to compute the answer for s[1] , so lets say s[1] = '1' , then answer is (1 , 1) else its (0 , 1) , now for each iteration , compute the answer for its 3 subparts , lets say mid = (r — l)/3 , then for each iteration , compute it for (l , l + mid) , (l + mid , r — mid) and (r — mid , r) , now there are 2 cases :

    1] All three of these subparts give the same max element

    2] any two of the three elements give the same max element

    Case 1 is pretty simple : if all these 3 parts give the same answer , then to reverse the max appearing element , you need to take the 2 minimum counts from these 3 (counts means the min number of swaps required in those subparts , i.e we are returning a pair<int,int> in dp , representing the max appearing element and counts)

    Case 2 is also simple : if any 2 of these 3 elements are returning the max appearing element then we need to swap any 2 of these 3 in order to reverse the max appearing element at this stage , so just check which 2 of the 3 are returning the same max element and take the min. counts from those 2. Here's my submission , feel free to ask further doubts. https://atcoder.jp/contests/abc391/submissions/62319929

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

Is D really so easy to implement? I keep getting WA on 21 testcases :(

Help me out please. Where am I going wrong? Submission

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

    Yep, It was kinda implementation , I did this !!

    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){
        int N  , W;
        cin >> N >> W;
    
        vector<vector<int>> bars(N + 1);
        map<array<int , 2> , int> blockId;
        for(int i = 0 ; i < N ; i++){
            int xi , yi;
            cin >> xi >> yi;
            bars[xi].push_back(yi);
            blockId[{xi , yi}] = i + 1;
        }
        for(vector<int> &bar : bars) sort(bar.rbegin() , bar.rend());
    
        vector<int> endTime(N + 1 , -1);
        for(int tot = N ; tot > 0 ; tot -= W){
            int ymax = -1 , isComplete = 1;
            for(int i = 1 ; i <= W ; i++){
                if(bars[i].size() > 0) ymax = max(ymax , bars[i].back());
                else isComplete = 0;
            }
            if(isComplete){
                for(int i = 1 ; i <= W ; i++){
                    int id = blockId[{i , bars[i].back()}];
                    endTime[id] = ymax;
                    bars[i].pop_back();  
                }
            } 
            else break;
        }
    
        int Q ; cin >> Q;
        while(Q--){
            int ti , id;
            cin >> ti >> id;
            if(endTime[id] == -1 || endTime[id] > ti){
                cout << "Yes" << endl;
            }
            else{
                cout << "No" << endl;
            }
        }
        return 0;
    }
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah it's very easy with priority_queue and your code is too difficult to understand. (maybe just for me?)

    Here's my solution!

    Choose the lowest blocks in each column and their move-away time is the altitude of the highest one among them!

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

      But some blocks will have to wait in the last row no? So during that time the upper blocks will also have to wait and so on?

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

        Yes.

        But if there's no blocks in a column, the blocks was't moved away won't move away forever. The while will break so their move-away time is still INT_MAX.

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

    This fact simplifies the implementation significantly:

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

    I don't think is necessary to use maps and sort, it makes the code more complicated, i didn't use them at least. Just try to answer, when will the first row dissapear, and after that, when will the rowi+1 dissapear knowing when the rowi dissapears. Also the problem inputs X first, and then Y, maybe that is a problem.

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

      Yeah pretty much same. I was having some complications while implementing the simple solution so I just commented everywhere which made is easy here I think it's one of the most readable at in my opinion

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

So ,is rank 1 legit?

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

Why does everyone think E is easier than D but I do not think so?

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

    For me, E is a simple divide and conquer problem. But I didn't bother to try D despite having 1 hour left, because of its complexity.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

G seems like a too well known problem for 200+ submissions.

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

    I went through all of the Indian Submissions and almost all seem AI generated. Hopefully the admins take strict action.

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

      Yeah I realised that when I saw low rated people solving G within 20 minutes and most of my friends not being able to solve it.

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

anyone who was able to solve problem D with priority queue? (at each column)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    
    #define i64 long long
    #define rep(i,l,r) for(int i=(l);i<=(r);i++)
    #define fdn(i,r,l) for(int i=(r);i>=(l);i--)
    #define pii pair<int,int>
    using namespace std;
    
    typedef long long ll;
    typedef double db;
    typedef __int128 i128;
    
    std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
    std::mt19937_64 rnd64(std::chrono::steady_clock::now().time_since_epoch().count());
    
    const int fyy=0;
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
        ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
        int N,W;
        cin>>N>>W;
        vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>> q(W+1);
        vector<int> ans(N+1,(int)1e9+24);
        rep(i,1,N)
        {
            int X,Y;
            cin>>X>>Y;
            q[X].push({Y,i});
        }
        bool zxq=1; // 张修齐:是否可进行下一轮
        while(zxq)
        {
            int _max=fyy;
            rep(i,1,W)
            {
                if(q[i].empty())
                {
                    zxq=fyy;
                    break;
                }
                _max=max(_max,q[i].top().first);
            }
            if(!zxq) break;
            rep(i,1,W)
            {
                ans[q[i].top().second]=_max;
                q[i].pop();
            }
        }
        int Q;
        cin>>Q;
        while(Q--)
        {
            int T,A;
            cin>>T>>A;
            if(T>=ans[A])
                cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
    
    // 路虽远行则将至,事虽难做则必成。

    https://atcoder.jp/contests/abc391/submissions/62291264

    u can think the block i with first pos (Xi,Yi) will be disappear after Yi. Then consider do it in loops and get the max of Y. (sorry for poor English)

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

is there someone indea using ai so banned by atcoder?what's his name?

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

Please help me modify this code. I spent a long time debugging it during the exam.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,w,sc[N],su=INT_MAX,q;
struct zz
{
	int high,id,yl;
};
vector<zz>mp[N];
bool cmp(zz a,zz b)
{
	return a.yl<b.yl;
}
int main()
{
	memset(sc,-1,sizeof(sc));
	cin>>n>>w;
	for(int i=1,x,y;i<=n;i++)
	{
		cin>>x>>y;
		mp[x].push_back((zz){0,i,y});
	}
	int flag=1;
	for(int i=1;i<=w;i++)
	{
		sort(mp[i].begin(),mp[i].end(),cmp);
		int cnt=0;
		for(int j=0;j<mp[i].size();j++)
		{
			mp[i][j].high=j+1;
			if(mp[i][j].high==mp[i][j].yl)
			{
				cnt++;
			}
		}
		flag&=(cnt==mp[i].size());
	}
	for(int i=1;i<=w;i++)
	{
		su=min(su,(int)mp[i].size());
	}
	for(int i=1;i<=su;i++)
	{
		for(int j=1;j<=w;j++)
		{
			sc[mp[j][i-1].id]=i+1;
		}
	}
	cin>>q;
	while(q--)
	{
		int t,a;
		cin>>t>>a;
		if(t)t+=flag;
		if(!t)
		{
			printf("Yes\n");
		}
		else if(sc[a]==-1)
		{
			printf("Yes\n");
		}
		else
		{
			if(sc[a]<=t)
			{
				printf("No\n");
			}
			else
			{
				printf("Yes\n");
			}
		}
	}
}
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Quality problems(which I start to struggle from) starts with E. E seemed like implementation heavy and I was not very fond to address the string of size upto 1e7 in my recursion so after 20 minutes on it I left it. I start F. I did almost completed it, but time's up.

I am new to Atcoder and I have a question. How do you guys attempt Atcoder? Do you start from F and G and go in backward direction so that you have maximum time for quality problem or I am just slow and rusty and most people are at the start of a new skill or you select any problem which seems interesting from A to G? How you make sure you do that most quality and get the most value out of a contest? Or is it that currently I am really slow?

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

why is the editorial of problem D with complexity O(n log n)? it can be solved in O(n)

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

    as for the code:

    with complexity O(n+q)

    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    struct block{
        int x,y;
    }a[N];
    int n,w,q;
    int id[N],idx[N],cnt[N],tl[N];
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(NULL),cout.tie(NULL);
        cin>>n>>w;
        for(int i=1;i<=n;++i){cin>>a[i].x>>a[i].y;}
        cin>>q;
        for(int i=1;i<=n;++i){
            id[a[i].x]++;
            idx[i]=id[a[i].x];
            cnt[id[a[i].x]]++;
            tl[id[a[i].x]]=max(a[i].y,tl[id[a[i].x]]);
        }
        while(q--){
            int t,pos;
            cin>>t>>pos;
            if(cnt[idx[pos]]!=w){cout<<"Yes\n";}
            else{
                if(t<tl[idx[pos]]){cout<<"Yes\n";}
                else{cout<<"No\n";}
            }
        }
        return 0;
    }

    in fact, we don't need to sort

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

Hey i have a question. I have heard lots of people talk about how good the ABCs are ? Can anyone tell me why they are good ? Thanks. I am a newbie so dont know a lot of stuff

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

How to do E ?

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

Can anyone tell how to solve the problem C please ?

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

I don't konw F. Why it's enough to look at ijk <= K? Who could teach me why.

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

    Say length is n, indexing is 1 and f(x,y,z) is the actual computation for tuple (x,y,z) and you sorted it in descending order then f(i,j,k) will be always be more than f(i+1,j,k), f(i,j+1,k) and f(i,j,k+1). So essentially going from any i to i+1 decreases the value of overall of f.

    For each i, there are jk possibilities and they are actually maximum because of sorted property. I hope it helps. Example take i = 1 and j, k = n then there are n2 arrays

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

F is easy, but I didn't solve it during the contest qwq