Блог пользователя MikeMirzayanov

2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) — Tutorials
Автор MikeMirzayanov, 3 года назад, По-английски

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...
  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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]

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody share the code of C. Berpizza

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    See in my submissions

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится 
    #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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"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?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain how are we finding if it is possible to burst f crackers in problem D?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i dont know if you have figured it out, but f is min(distance between the cop and hooligan,total number of crackers).The reasoning behind it is that the distance between hooligan is either decreasing or constant. And whenever he bursts a cracker, the cop comes one step closer to him, which means that at max he can burst Dist crackers(unless of course m is smaller than Dist). (Dist = distance between cop and hooligan).

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you get to the conclusion that only collinear but oppositely facing vision vectors will make eye contact in problem f. How to prove that any other vision vectors wont make it ??

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Consider a straight line between 2 persons. So, if they will ever make eye contact then only if they both have a vision on that line heading towards each other. Now the degree both persons rotate must be equal, you can observe that it is only possible if both vectors are collinear and have opposite directions.

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A note on problem $$$M$$$: it's actually better to set the bound to be $$$400$$$ as opposed to $$$\sqrt{N}$$$. My solution improved from $$$900$$$ ms to $$$700$$$ ms using this better bound.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know this is extremely late, but for problem D, you don't even need to do binary search. All you need to do is sort the firecrackers. Then iterate from the firecrackers with largest time to smallest time. For firecracker i, check if the space between the hooligan and the cop plus the space between the hooligan and the end is greater than the time of the firecracker and that the hooligan isn't caught yet. Then increase your answer by 1

149971062

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem $$$M$$$ has a bipartite graph and asks if there is a cycle of length $$$4$$$.

Given any bipartite graph if we want to find if there exists a cycle of size $$$N$$$. Where $$$N$$$ is even. Is there any general solution for this?

→ Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem F. Can someone prove the fact that two persons will make eye contact during 360 rotation if their initial vision vectors are collinear and oppositely directed.

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Easy code for C Berpizza. 210647965

→ Ответить