### MikeMirzayanov's blog

By MikeMirzayanov, 20 months ago,

• +86

 » 20 months ago, # |   +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.
•  » » 20 months ago, # ^ |   -84 https://codeforces.com/contest/1468/submission/102338964 Can you tell why this is giving runtime error in test 46 I am not able to figure it out..
 » 20 months ago, # | ← Rev. 2 →   -18 Nice editorial
 » 20 months ago, # |   -17 Thanks for this Tutorials, It was a very cool contest, But there were a lot of test cases, which caused the long queue.
 » 20 months ago, # | ← 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]
•  » » 20 months ago, # ^ |   +6 i can not understand editorial for A. can you explain?
 » 20 months ago, # |   -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$.
•  » » 20 months ago, # ^ |   -8 Yes, you are correct. Thank you!
 » 20 months ago, # |   -38 MikeMirzayanov is there an alternate to these explanations , it is difficult for me to understand this editorial.
 » 20 months ago, # |   -12 Please someone can explain similar sets(problem M) editorial.
 » 20 months ago, # | ← Rev. 5 →   -21 Thanks for good problems
 » 20 months ago, # |   0 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
 » 19 months ago, # | ← 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
 » 19 months ago, # |   0 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?
 » 19 months ago, # | ← 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
•  » » 19 months ago, # ^ |   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
•  » » » 19 months ago, # ^ |   0 Thanx. Now it was all clear to me
 » 19 months ago, # |   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.
 » 19 months ago, # |   0 Can anybody share the code of C. Berpizza
•  » » 19 months ago, # ^ |   0 See in my submissions
•  » » 19 months ago, # ^ |   0 #include using namespace std; typedef long long int ll; typedef vector vi; typedef vector> vvi; typedef vector vb; typedef pair pii; #define fo(i,s,e_ex) for(i=s;i=n;kb.second; } return a.first, decltype(&compForPair)> poly(compForPair); priority_queue > 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<>t; for(ll i=1;i<=t;i++){ solve(i); } return 0; } 
 » 19 months ago, # | ← Rev. 2 →   0 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: 105199970Approach: 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.
 » 19 months ago, # |   0 My code for question c is giving tle on test case 17 plz help!!!!!
 » 18 months ago, # |   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?
 » 16 months ago, # |   0 can someone explain how are we finding if it is possible to burst f crackers in problem D?
•  » » 15 months ago, # ^ |   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).
•  » » » 2 months ago, # ^ |   0 thank you, that was helpful
 » 15 months ago, # |   0 What did i do wrong in my code for question D? submission — My attempt
 » 15 months ago, # |   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 ??
•  » » 13 months ago, # ^ |   +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.
 » 7 months ago, # |   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.
 » 5 months ago, # |   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 1149971062
 » 3 months ago, # |   0 can anyone help me in problem C ,it is showing wrong answer on 40 test case 157287675