MikeMirzayanov's blog

By MikeMirzayanov, 4 months ago, In English

You can view PDF version of the tutorial by the link.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +86
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +37 Vote: I do not like it

That trick for pairs in problem M is just awesome... During the whole contest we were struggling to remove that logn factor but couldn't find the way.

»
4 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Nice editorial

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Thanks for this Tutorials, It was a very cool contest, But there were a lot of test cases, which caused the long queue.

»
4 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I think that there is a mis-written part in problem A in editorial: a[posi−1]≤a[posi]≥a[posi+1] should be a[posi−1]≤a[posi]≤a[posi+1]

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

    i can not understand editorial for A. can you explain?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I think there is an error in tutorial for L. "If there are no more than 2 such integers" (second sequence) should be "If there are no more than 1 such integers" or "If there are less than 2 such integers". Because in next paragraph $$$k_i > 1$$$ implies that $$$p$$$ can be important if there are 2 numbers of form $$$p^q$$$.

»
4 months ago, # |
  Vote: I like it -38 Vote: I do not like it

MikeMirzayanov is there an alternate to these explanations , it is difficult for me to understand this editorial.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Please someone can explain similar sets(problem M) editorial.

»
4 months ago, # |
Rev. 5   Vote: I like it -21 Vote: I do not like it

Thanks for good problems

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

for problem c, i just used two different sets, one for each operation type, sorting elements as either (i, m) or (m, i), where m is the estimated money and i is the customer number. this makes finding which customer is served much easier, as you can take from the front of the first set for the 1st operation and from the back of the second set for the 2nd operation

»
4 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

For M, how is finding all pairs (x,y) not time complexity (k^2)? How exactly do you create a separate array for each integer x and then add all values y to it

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

For L, I'm getting wrong answer on test case 99 (because I'm only able to find a sequence of 994 items, not 1000). Is this happening to anyone else?

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

In problem C Berpizza why I am getting tle on test case 12 My code please let me know and also how to resolve it

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I notice that you are sorting the vector every time a monocarp or polycarp query is done. This is probably making it slow. You can instead try using sets as they are implemented using binary-search trees and will be faster (O(log n) vs O(n logn) per query). My submission using sets

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem M's tutorial, does it mean that: For every small sets, we find all pairs, which is O(k^2) where the k is the size of the sets. There are M/k sets so that their are O(M*k) pairs in total? How should I implement it? I tried 2 dimension unorderedmap but TLE.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody share the code of C. Berpizza

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See in my submissions

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #include<bits/stdc++.h> 
    using namespace std;
    typedef long long int ll;
    typedef vector<ll> vi;
    typedef vector<vector<ll>> vvi;
    typedef vector<bool> vb;
    typedef pair<ll,ll> pii;
    #define fo(i,s,e_ex) for(i=s;i<e_ex;i++)
    #define Fo(i,k,n) for(i=k;k<n?i<=n:i>=n;k<n?i+=1:i-=1)
    #define endl '\n'
    #define MOD 1000000007//998244353
    #define setbits(x) __builtin_popcountll(x)
    #define pbb push_back
    #define mpp make_pair
    #define ff first
    #define ss second
    #define all(x) x.begin(),x.end()
    #define mset(arr,val) memset(arr,val,sizeof(arr))
    vi guest(500005,1);
    bool compForPair(pii a,pii b){
    	if(a.first==b.first){
    		return a.second>b.second;
    	}
    	return a.first<b.first;
    }
    void solve(ll caseno){
        ll i,j,q;
    	ll type,m=0,guestNo=1;
    	priority_queue<pii, vector<pii>, decltype(&compForPair)> poly(compForPair);
    	priority_queue<ll, vi,  greater<ll> > mono;
    	cin>>q;
    	while(q--){
    		cin>>type;
    		if(type==1){
    			cin>>m;
    			poly.push(mpp(m,guestNo));
    			mono.push(guestNo);
    			guestNo++;
    		}else if(type==2){
    			while(true){
    				ll gtorem = mono.top();mono.pop();
    				if(guest[gtorem]==1){
    					cout<<gtorem<<" ";
    					guest[gtorem]=0;
    					break;
    				}
    			}
    		}else{
    			while(true){
    				ll gtorem = poly.top().second;poly.pop();
    				if(guest[gtorem]==1){
    					cout<<gtorem<<" ";
    					guest[gtorem]=0;
    					break;
    				}
    			}
    		}
    	}
    }
    int main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
    	ll t=1;
    	//cin>>t;
    	for(ll i=1;i<=t;i++){
    		solve(i);
    	}
    	return 0;
    }
    
»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C, can anyone tell me why my code is failing in the seventh test case that too by swap of two digits(136 in place of 133 and 133 in place of 136)? source: 105199970

Approach: I have used two priority queues with pairs to store customer id and price sorted with respect to id in ascending order for monocarps queries and sorted with respect to price in descending order for polycarps queries. And I have used unordered_map to check which id's have already been served.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for question c is giving tle on test case 17 plz help!!!!!

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Can someone help me with problem K. I am not able to figure out where I am doing mistake?

Your code here...
#include<bits/stdc++.h>

using namespace std;
#define ull unsigned long long
#define ll long long
#define f first
#define S second
#define mod 1000000007


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    // freopen("input.in", "r", stdin);
    // freopen("output.in", "w", stdout);
    int t;
    cin>>t;
    while(t--)
    {
      string s;
      cin>>s;
      int c = 0;
      for(int i=0;i<s.length()-1;i++)
      	if(s[i]!=s[i+1])
      	{
      		c = 1;break;
      	}
      if(c==0)
      	{
      	if(s[0]=='L')
      		cout<<-1<<" "<<0<<"\n";
      	else if(s[0]=='R')
      		cout<<1<<" "<<0<<"\n";
      	else if(s[0]=='U')
      		cout<<0<<" "<<1<<"\n";
      	else if(s[0]=='D')
      		cout<<0<<" "<<-1<<"\n";
      	continue;
      	}
      	vector<pair<int,int>>left(s.length()+1);
      	vector<pair<int,int>>ryt(s.length()+1);
      	for(int i=0;i<s.length();i++)
      	{
      		left[i+1] = left[i];
      		if(s[i]=='L')
      			left[i+1].f -=1;
	      	else if(s[i]=='R')
	      		left[i+1].f +=1;
	      	else if(s[i]=='U')
	      		left[i+1].S+=1;
	      	else if(s[i]=='D')
	      		left[i+1].S-=1;

      	}
      	for(int i = s.length()-1;i>=0;i--)
      	{
      		ryt[i] = ryt[i+1];
      		if(s[i]=='L')
	      		ryt[i].f-=1;
	      	else if(s[i]=='R')
	      		ryt[i].f+=1;
	      	else if(s[i]=='U')
	      		ryt[i].S+=1;
	      	else if(s[i]=='D')
	      		ryt[i].S-=1;
      	}

      	vector<int>inx(s.length());
      	for(int i=0;i<s.length()-1;i++)
      	{
      		if(s[i]!=s[i+1])
      			inx[i] = i+1;
      		else
      		{
      			if(i!=0 && inx[i-1]>i)
      				inx[i] = inx[i-1];
      			else
      			{
      				int j = i+1;
      				while(j < s.length() && s[i]==s[j])
      					j++;
      				inx[i] = j;
      			}
      		}
      	}
      	int b = 0;
      	inx[s.length()-1] = s.length();
      	for(int i=0;i<s.length();i++)
      	{
      		if((left[i].f + ryt[inx[i]].f==0 && left[i].S + ryt[inx[i]].S==0))
      		{
      			if(left[i+1].f!=0 || left[i+1].S!=0){
      			cout<<left[i+1].f<<" "<<left[i+1].S<<"\n";
      			b = 1;
      			break;}
      		}
      		
      	}
      	
      	
   

      	if(b==0)
      		cout<<0<<" "<<0<<"\n";







  

    }

    return 0; 

}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"Now, we can note that each a[i] is either minimum in LaIS or i = nxt[j] for some other element a[j]".

Can someone give me a proof of that?