### gridnevvvit's blog

By gridnevvvit, 4 years ago, translation, ,

Hello!

Soon (on June 8 at 19:30 MSK) you are lucky to participate in Codeforces Round for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaly (gridnevvvit) and Danil Sagunov (dans).

We want to thank Gerald for help in preparation of this round, Delinur for translation of statements and MikeMirzayanov for marvelous Codeforces and Polygon systems.

Scoring will be next 500 — 1000 — 1500 — 2000 — 2500.

Contest finished, congratulations to winners!

Editorials will be there

Good Luck!

•
• +115
•

 » 4 years ago, # |   +14 Hope this round to be a bridge to be a div1 contestant for the first time , just hope
•  » » 4 years ago, # ^ |   +1 gl & hf
•  » » 4 years ago, # ^ |   +4 another hope not back to green :(
•  » » » 4 years ago, # ^ |   +7 you will be down by around 95, so not green :)
•  » » » » 4 years ago, # ^ |   +1 how do you calculate the rating change ?
•  » » 4 years ago, # ^ |   0 Why does my 6839434 for A fail?
•  » » » 4 years ago, # ^ |   +8 Because you have WA
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 you break out of the loop but you don't handle the rest of input in that loopEx: 3 50000, 1 50000, 3 100000 1 110000, 3 120000 110000 120000,Your code it will read it as if the 3rd k = 110000 because you break after the 1 in the 2nd
•  » » » 4 years ago, # ^ |   +1 Because you used break;So, you did not ignore the remaining entries of that seller, and the next entry (which was to be ignored) was taken as the number of products with next seller and that ruined your code. your code works fine iff either no one has cheap product or only last product is cheap.
•  » » » 4 years ago, # ^ |   +1 fixed 6850039
•  » » » » 4 years ago, # ^ |   0 Thanks, guys!
 » 4 years ago, # | ← Rev. 2 →   +3 Good luck with preparing your second contest , Keep going for more =) and I hope that the problems and the editorial will be reach with new and useful things to learn
•  » » 4 years ago, # ^ |   +30 This round is not second. This round is the ninth my round
•  » » » 4 years ago, # ^ |   +4 The 236 round was your first round for both divisions and not your first round for Div2 only , now I seethanks for clarification =)
•  » » » 4 years ago, # ^ |   0 Are there many hacks?
•  » » 4 years ago, # ^ |   +8 You rating curve is so interesting~
 » 4 years ago, # |   0 Hope everyone good luck and success for the this contest
 » 4 years ago, # |   0 can any one give me the links of other contests DIV2 made by gridnevvvit :) thanks
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +3 I have never been able to solve Div-2 C type questions during contest... I hope i do solve it this time :) Good luck everyone
•  » » 4 years ago, # ^ |   +10 start with C. This worked with me, hope it works with you also.
•  » » » 4 years ago, # ^ |   0 very nice suggestion :)
 » 4 years ago, # | ← Rev. 2 →   +14 I guess that someone black will win this round again.249 div 2 only247 div 2 onlyUPD: yeah, I'm right.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 I think they are people which already have an old account at Codeforces but they just build a new account to become candidate master in 1 contest!
•  » » 4 years ago, # ^ |   +20 let them I think making another account to compete in a div2 contest and be from top 10 ,that's the result of competing at div1 and lose every time or you can't make a significant score so you leave the real competing at div1 and try to stretch your muscles on a div2 players :)
•  » » 4 years ago, # ^ |   +43 Black? Dat's racist.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 I don't think that what he was aiming to . Black is the non-rated contestant as he didn't enter any contest just as the color of your accountAnd give me a break , you are putting Hitler photo and talking about racism ? =D
•  » » » » 4 years ago, # ^ |   +24 I think
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +28 Hey, It's Hitler himself, Not just putting his photo.
 » 4 years ago, # |   +4 A question: Why everybody says that the scoring will be announced later?! Couldn't they publish it earlier?!
•  » » 4 years ago, # ^ |   +5
•  » » » 4 years ago, # ^ |   +4 Thanks :)
•  » » 4 years ago, # ^ |   +23
•  » » » 4 years ago, # ^ |   +3 please upvote the above.
•  » » 4 years ago, # ^ |   0 NO.
•  » » 4 years ago, # ^ |   +3 so mainstream ;)
 » 4 years ago, # |   -28 give me '-' pls
•  » » 4 years ago, # ^ |   +7 Sure. ^_^
•  » » 4 years ago, # ^ |   0 I think that's a bad idea according to amount of trolls around :D
 » 4 years ago, # |   0 Gd luck every one, hope I rise my rating this time :3 :D
 » 4 years ago, # |   +9 Great round! Pretty interesting problems :)
 » 4 years ago, # |   -10 Very hard D and E :(
 » 4 years ago, # |   +4 Statements was unclear.
•  » » 4 years ago, # ^ |   +7 What thing is unclear for you in the statements? I will try to do better statements in the future
•  » » » 4 years ago, # ^ |   0 A problem, i read three times to understand statement. B problem, i didn't now is possible to collect any number of fruits(
•  » » 4 years ago, # ^ |   0 Did you find the exit you asked for?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 oh, i was nervous,i have made stupid mistake in A problem(i set INF 10^5 instead of 10^6)
•  » » 4 years ago, # ^ |   0 wasn't unclear ... just a little bit hard to understand . ;)
•  » » 4 years ago, # ^ |   0 yaap... statement was not clear to me too... :/ but the notes after each problems helps me a lot... thanks to author for that... :)
•  » » » 4 years ago, # ^ |   0 I agree, notes was useful.
 » 4 years ago, # |   +3 How to solve problem D?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +11 There were a few key points :1) Number of swaps needed to make a permutation an identity permutation are N-C, where N is the number of elements and C is the number of cycles in the permutation. This can be proved using the statement 2 and 3 below (that it is unoptimal to swap outside cycle) and that a cycles of size M needs M-1 swaps to be sorted (provable by induction on M).2) Swapping two numbers in the same permutation cycle increases the number of cycles by 1. This can be proved constructively (take a cycle C, swap two elements and see that two new cycles are made.)3) Swapping two number from different permutations decreases the number of cycles by 1. Again, constructive proof.We have some number of cycles in the given permutation P, and we need N-M cycles in the target permutation Q. Hence keep on making an inter or intra cycle swap depending on which is bigger; and greedily choose the smallest index for lexicographically smallest solution. Complexity O(N2)
•  » » » 4 years ago, # ^ |   0 The problem is tagged with disjoint-set unions. How can dsu's be used in this problem? What I did was to calculate the new disjoint cycles of the permutation resulting from every optimal intra/inter cycle swap.
•  » » » » 4 years ago, # ^ |   0 DSU can be used, for example, for joining cycles to cycle containing vertex 1 (The first case in editorial).
•  » » » 4 years ago, # ^ |   0 Can you please provide a code where you have implemented the above idea ? Thanks.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   -17 #include #include #include #include #include #include using namespace std; bitset<4000> vis; int phi[3000]; vector > v; priority_queue pq[3000]; int ind[3000]; int cyc; int n; void process(){ for(int i=0; i tmp; while(!vis[j]){ tmp.push_back(j); ind[j]=v.size(); pq[v.size()].push(j); if (tmp.size()>2) pq[v.size()].pop(); vis[j]=1; j=phi[j]; } v.push_back(tmp); } } int main(){ scanf("%d",&n); vis.reset(); for(int i=0; icyc){ int diff=m-cyc; printf("%d\n",diff); for(int it=0; it
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Here is my implementation of the above idea, as requested.
 » 4 years ago, # |   0 How to solve B?
•  » » 4 years ago, # ^ |   0 you must sort your trees by days and then model situation
•  » » » 4 years ago, # ^ |   0 i stored the number of fruits on tree i in pp[i-1] and then iterated from 0 to n, picking as much fruits as possible. this is the submission http://codeforces.com/contest/441/submission/6845290 why is this approach wrong?
•  » » » » 4 years ago, # ^ | ← Rev. 5 →   0 Because you are summing the fruits you can collect to the Nth day... Here in your code — Line 22 : for (int i = 0; i < n+1; ++i) { ... Should be : for (int i = 0; i <= 3001; ++i) { ... UPD: That is one of your mistakes, but not that you got WA for.
 » 4 years ago, # |   0 Did everyone run the loop till the maximum day value for problem B? :P It was a pretty good hack.
•  » » 4 years ago, # ^ |   0 so what is the good test to hack them?
•  » » » 4 years ago, # ^ |   0 For example: 1 100 3000 200
•  » » 4 years ago, # ^ |   +1 Till max day + 1 of course :))
•  » » » 4 years ago, # ^ |   +1 Yes, till max day + 1 :D The best way was to run it till <=3001
•  » » 4 years ago, # ^ |   0 Good hack.. But in my room almost everybody run till <=3001 :) I have hacked only 3 submission.
•  » » » 4 years ago, # ^ |   0 Well, I ran till N :) Nobody hacked me, and I failed just on 26th test. How unfortunate.
 » 4 years ago, # |   +10 system testing is faster than usual .
•  » » 4 years ago, # ^ |   +2 Hope that the rating system's to!
•  » » 4 years ago, # ^ |   0 congrats for that
 » 4 years ago, # |   +18 I'm new to CF and I read problem E first...
•  » » 4 years ago, # ^ |   +51 I'm old to CF and I also read problem E first...
 » 4 years ago, # |   0 what was the correct way to solve DIV 2 B problem.i approached by first solving for day[i-1] and then for day [i] ...but got wrong answer on pretest 5 http://ideone.com/mWCTzM
•  » » 4 years ago, # ^ |   0 at first you should sort them by day.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 have three integer variables curPicked, prevDay and curDay. Then try to pick as many fruits as possible from the trees of prevDay and curDay while making sure that curPicked<=v.In my solution I created an array of 3000 elements for the days and for each day I saved all the different amounts of fruits that can be gathered on that day specifically. Note that the order doesn't matter. then it's just a matter of using the above 3 variables and the array effectively while taking care of the corner cases.Total time complexity: Θ(max of n)
•  » » 4 years ago, # ^ |   0 Some days may be missing.
•  » » 4 years ago, # ^ |   0 I see no reason, why you assumed that only for any particular day x, only one tree will have fruit at that day. Given your piece of code, day[st[i].day]=st[i].cap;.
•  » » » 4 years ago, # ^ |   0 my mistake...at starting i remembered it but at last i forgot it.. AC by changing to day[st[i].day]+=st[i].cap; :'(
•  » » 4 years ago, # ^ |   0 corrected...the days were repeated...did'nt noticed it just changed day[st[i].day]=st[i].cap; to day[st[i].day]+=st[i].cap; and AC :'(
•  » » » 4 years ago, # ^ |   0 same for me
 » 4 years ago, # |   0 waiting for editorials....
•  » » 4 years ago, # ^ |   0 me too
 » 4 years ago, # | ← Rev. 2 →   +1 Problem-C : Code implementation finished....contest 1 min remaining , when compiled--- several errors . After correcting errors...15 sec remaining>>>> finally, couldn't submit during contest !!!! Bad luck.. Anyways, contest problems are nice :)
 » 4 years ago, # |   0 Yeah. Finally solved three problem again..Thanks for this round... :)
 » 4 years ago, # |   0 what about editorials?
 » 4 years ago, # |   0 after solving probelm, A I could have solved problem B but I went for E because I found it really interesting but i failed to solved it in the end. Was it a wrong decision?
•  » » 4 years ago, # ^ |   +1 yes
 » 4 years ago, # |   0 Can Any body tell me where is the main differnce between those two codes..??? I use max value for the last limit for first one. And Use 3000 as last limit in 2nd one... Why I got WA... Cant find it.....
•  » » 4 years ago, # ^ |   0 I guess in the first code, you can still collect fruits that became available on day 3000, on day 3001, which you never visit, the second code, allowed for this case to occur, by having +2 beyond the maximum day.
•  » » » 4 years ago, # ^ |   0 Thank you.... Feeling like i am the biggest idiot in the world... thanks for pointing the mistake out....
•  » » 4 years ago, # ^ |   0 Edited code of your first one : 6849997 just written 3001 instead of 3000. Hope, you have got the point.
 » 4 years ago, # |   0 Rating is Updated
 » 4 years ago, # |   0 I have a bad day , i had WA on test 1 in problem C because i was use printf %d with a long long int without noticing , i don't know that it really cause many problems , in my local compiler the answer was the expected but in codeforces test no.
 » 4 years ago, # |   +3 Hope to back ( green ) soon :)
 » 4 years ago, # |   0 That was a really fun round, thank you gridnevvvit!!
 » 4 years ago, # |   +9 i_love_gridnevvvit Why unrated?
 » 4 years ago, # |   0 Anybody help me out with C?
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 I tried solving the problem greedilywe need k tubes, each with size >=2. Now k-1 tubes will be of size 2 and the remaining points will be the last tube. However I didn't have enough time to figure out how to print the final tube in a way that satisfies the condition for any integer i (1 ≤ i ≤ r - 1) the following equation |xi - xi + 1| + |yi - yi + 1| = 1 holds;
•  » » » 4 years ago, # ^ |   0 I made it that way :) 6844587
•  » » » 4 years ago, # ^ |   0 I did it the same way. But got TLE.
 » 4 years ago, # | ← Rev. 2 →   +3 why the hacks list is not shown yet ??Edit: Now they appeared :D
 » 4 years ago, # |   0 Would you please tell me what is wrong for this code? It is for 441B — Valera and Fruits :http://codeforces.com/contest/441/submission/6850959
•  » » 4 years ago, # ^ |   0 Got it!, this is not optimal, because I should go for the trees that are getting rotten first.
 » 4 years ago, # |   0 Problem D was very nice for me; guess I learned about permutations solving it more than my recent abstract algebra course :D though I couldn't manage to debug my code in time :(Thanks for the round!
 » 4 years ago, # |   0 Not sure what is wrong in — http://codeforces.com/contest/441/submission/6844819I am getting the correct answer while running on 'GNU GCC version 4.7.2'. Please let me know.
•  » » 4 years ago, # ^ |   0 Replies please
•  » » 4 years ago, # ^ |   0 try to initialize the variable "selected" to Zero at the beginning
•  » » » 4 years ago, # ^ |   0 ohh I am sorry I wanted to give an up arrow and clicked down instead. I will change it .Thanks a lot it works now — http://codeforces.com/contest/441/submission/6855224 Can you tell me what was the reason. It worked good when I tested in my compiler. Thanks again hellcoder
 » 4 years ago, # |   +29 Round Stats P.S. Take a look on the match winner (kuangbin10) and these accs: kuangbin9 kuangbin8 kuangbin7 kuangbin6 kuangbin5 kuangbin4 kuangbin3 kuangbin2 kuangbin1 kuangbin
 » 4 years ago, # |   +5 6844888 I don't know why I get WA on test 11,I think my output at least in this test is correct.
•  » » 4 years ago, # ^ |   +5 Oh,I am sorry,I didn't understand the meaning of the problem C last night.
•  » » » 4 years ago, # ^ |   +1 Me too, I didn't understand the problem C
 » 4 years ago, # |   0 I solve the problem B with O(n^2) (for 1 -> max_day {for 1 -> n}). If have test max_day = 3000 , n = 3000 then it will work O(3000*3000) = O(9000000), but it not TLE. I am surprising about this. Because this, I hacked some people with test 3000, 3000 and all unsuccessful. I am sad about this
•  » » 4 years ago, # ^ |   0 9000000 operations it is very small amount to recieve TL.
•  » » » 4 years ago, # ^ |   0 gridnevvvit , O(10^6) works in 1s ? If not, how much second for working O(10^6) ?
•  » » » » 4 years ago, # ^ |   0 Yes, it works. see my solution: 6850502
•  » » » » » 4 years ago, # ^ |   0 Thanks much !
 » 4 years ago, # |   0 Why can't I vote twice on a comment. It may happen that I voted somebody down by mistake but now I want to revert or give up
•  » » 4 years ago, # ^ |   0 You can only vote once on a comment. So as need think carefully before vote for 1 comment. Good luck !
•  » » » 4 years ago, # ^ |   +3 can we not have a feature to change the vote