### piloop's blog

By piloop, 9 years ago,

Hello everyone,

We are glad to invite you to participate in today’s round.

Problems have been prepared by poopi, Mohammad_JRS, Gerald and me. The hero of our contest is called “PMP”. It is actually the base of our team name through the last five years. The stories are metaphoric, but they have some traces in truth.

This Codeforces round, is the last round before the incoming ICPC world final. Our best wishes for all participants of that contest, too.

I want to specially thank Gerald for his helps and advices in problem preparation, Delinur for translation of statements into Russian and MikeMirzayanov for this great system.

And we have a modified version of Burunduk1 ’s advice: “to make the round even more interesting for us, read the statements of ALL problems.” :)

We hope you enjoy the problems and have high ratings.

Update: Contest is over. Thanks to everyone for taking part and congratulations to the winners of both divisions, specially peter50216 for being the only who solved all the problems of division 1! :)

Update: Editorial

• +211

 » 9 years ago, # |   -85 "PMP"? Why not "PIMP"? Sounds cool(waiting for lots of minuses)
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 Hi Rebecca :)
 » 9 years ago, # | ← Rev. 2 →   +20 Please let us know about the point distribution and difficulty ordering of problems also.
•  » » 9 years ago, # ^ |   +29 we'll have standard points distribution in both divisions.
•  » » » 9 years ago, # ^ |   0 Is problems sorted by difficulty?
•  » » » » 9 years ago, # ^ |   +5 yes, they are.
 » 9 years ago, # |   +18 How is the main character (PMP) supposed to be pronounced? The closest I got was "pimp".
•  » » 9 years ago, # ^ |   +9 I thought about same thing but got lots of negative votes. Does it mean people pronounce it another way?
•  » » » 9 years ago, # ^ |   +1 Hah, your comment was hidden, but now I saw you said the same. Nah, I suppose they just didn't like the joke =/
•  » » » » 9 years ago, # ^ |   +20 You should pronounce it same as "ACM", "ICPC", "MST", "MSC" and all other abbreviations. Thanks for your point.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +25 (waiting for lots of minuses) You got what you wanted.
 » 9 years ago, # |   +13 hope it's not three consecutive unrated rounds
•  » » 9 years ago, # ^ | ← Rev. 2 →   +8 I wish you not to change opinion after round :)
•  » » 9 years ago, # ^ |   +8 The third is the charm, right =)
•  » » 9 years ago, # ^ |   +9 That peter50216 solved all the problems gains me some belief about a rated round :)
 » 9 years ago, # |   +3 I hope it will be very interesting!!!;)
 » 9 years ago, # |   0 I Like PMP!!!
•  » » 9 years ago, # ^ | ← Rev. 2 →   +24 I Like PvP!!!
•  » » » 9 years ago, # ^ |   0 I Like PtP!!! ;)
 » 9 years ago, # | ← Rev. 2 →   -28 I hope every one will solve at least 1st problem!!! xD
•  » » 9 years ago, # ^ |   -25 first from the end or from the beginning?
•  » » » 9 years ago, # ^ |   -10 Break stereotypes — solve the first from the end!
•  » » » » 9 years ago, # ^ |   -6 and be bad guy!
•  » » 9 years ago, # ^ |   +4 at least 1 problem
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 It was not fair to put -59 for my reiting, i have solved 1 problem
 » 9 years ago, # |   -7 I've heard that Iranians are especially strong in Maths. Should we expect some maths problems?Anyway, hope everyone enjoys this round.
 » 9 years ago, # |   +8 I read the notes of Div1.E Heaven Tour.
 » 9 years ago, # |   +30 The problems were great, thanks!
 » 9 years ago, # |   0 Как решалась А div 1
•  » » 9 years ago, # ^ |   +3 Ну заметим, что еси уж мы цифру перекладываем, то так, как нам нужно.Посмотрим, сколько можно не перекладывать: это кол-во чисел от начала a, которые содержаться в правильно порядке(возможно с чем-то между) в b
 » 9 years ago, # |   +2 Thank. Very interesting contest.
 » 9 years ago, # |   +5 How to solve problem C?
•  » » 9 years ago, # ^ | ← Rev. 3 →   +6 I don't know yet if this solution is correct. Binary search by q. Lets Check if we can get to t from s using q steps: Starting bfs, from all marked verticies,storing DSU, go to the no more than q step from each. If we get to vertex, where we was, check, if dist[current]+dist[vertex where we was]+1<=q, than join their sets in DSU. Finally, if set[s]==set[t], than we can use current q. P.P.S. Correct, simple bug..
•  » » » 9 years ago, # ^ |   +3 binary search is not needed.
 » 9 years ago, # |   +48 Awesome and interesting problems, thank you very much!
 » 9 years ago, # |   0 It was fun : )
 » 9 years ago, # | ← Rev. 2 →   0 Am I the only one who doesn't understand the second problem for the Div 2?With this input: 4 4 I see 9 rhombus who has coordinates like (x,y) (x+1,y+1) (x-1,y+1) (x,y+2) and 1 rhombus who has coordinate (0,2) (2,4) (4,2) (2,0)Where am I wrong?
•  » » 9 years ago, # ^ |   +1 It seems that you are only counting the ones with equal diagonals. Those with unequal diagonals are also possible.
•  » » » 9 years ago, # ^ |   0 Yes you're right, I was so stupid thinking during the contest that "sides equals <=> diagonals equals"... Thanks!
•  » » 9 years ago, # ^ |   0 (x,y) (x+1,y) (x-1,y) (x,y+2) is not a rhombus: 3 vertex on one line.
•  » » » 9 years ago, # ^ |   0 Sorry, I have edited there are some minutes.
 » 9 years ago, # |   +12 Did anybody open club of losers?Last 15 minutes I've tried to debug my B (div 1), and I can't find a mistake. But 3 minutes after end of the contest I've realised that there was j < i instead of j < 3...If noone open such club, I will open it. I invite everybody, who was unlucky today.)
•  » » 9 years ago, # ^ |   0 It reopens every contest by someone
•  » » 9 years ago, # ^ | ← Rev. 9 →   +13 Let's open! I've created array of 100010 elements instead of 200010 (thx Edvard (**fixed**) for hack =) )
•  » » » 9 years ago, # ^ |   0 Let me in! Let me in!
•  » » » 9 years ago, # ^ |   +18 That was not me, that was homo_sapiens.
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   0 Sorry! >_< Too many red coders in room.
•  » » 9 years ago, # ^ |   0 Let me in: I tried to hack really wrong solution A div 2, but failed to find 3 numbers a,b,n: n-a % b != 0, n-b % a != 0, n % (a+b) == 0.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +9 Try using a code ;) for(int c=1;c<1000;c++) for(int c2=1;c2<1000;c2++) for(int c3=1;c3<1000;c3++) if((c-c2)%c3!=0&&(c-c3)%c2!=0&&c%(c2+c3)==0) std::cout<
•  » » 9 years ago, # ^ |   +6 Me too, too! Since I'm naive, I believed k ≤ 1000 is important, and iterated 1000 times instead of 60 in B. Never again will doubt myself on these things. >_<
•  » » 9 years ago, # ^ |   +8 I made a tiny silly mistake in problem D (div2), but it was accepted the pretest. In stead of f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v]), it was f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v])... It was too late when I realised the mistake 5 minutes after the contest finished. It was failed the system test.
•  » » » 9 years ago, # ^ |   +1 I made the same mistake.
•  » » 9 years ago, # ^ |   0 I tried to hack this code 2 times during contest but it passed somehow! (Div2 A)http://codeforces.com/contest/189/submission/1673396It ran for 18sec in my PC to produce output of this case: 4000 2 2 2
•  » » » 9 years ago, # ^ |   0 Compiled with right keys? It works for 13 seconds on my PC without optimisation, and 1.7 with O2.
 » 9 years ago, # |   0 How to solve problem D in div2?
•  » » 9 years ago, # ^ |   +9 First, precalc time(i,j) = min time for moving from i to j without changing car. Second, use dynamic: time2(i,j,k) = min time for moving from i to j with changing car <= k times. Base: time2(i,j,0) = time(i,j). Step: time2(i,j,k+1) = min(time2(i, j, k), min_l(time2(i,l,k) + time2(l, k, 0)) (not sure, that first argument in external min is necessary). When you go from i to j, you change car last time in city l, and move from i to l with changing car <= k times, and from l to k without changing car.
•  » » » 9 years ago, # ^ |   0 Thanks!
 » 9 years ago, # |   0 How to solve problem C div.2?
•  » » 9 years ago, # ^ |   0 I used binary search.
•  » » 9 years ago, # ^ |   +3 смотри выше
•  » » 9 years ago, # ^ |   0 Number of fixed points = max {i| b[:i] is subsequence of a}
•  » » 9 years ago, # ^ | ← Rev. 3 →   0 for the every element a[i] in first array:Consider all numbers that are to the left in first array... = set A Consider all numbers that are to the right in second array...= set B (after a[i])if(A ^ B != {empty}) this is bad for our element (i.e a[i]) That yields that starting from a[i] to the a[n] all elements must be affected, giving us the answer n-i
 » 9 years ago, # |   0 Is there something special in Test 11 of problem B-div1? It's too large to understand what's wrong. I noticed that I wasn't the only participant who failed on that test.
•  » » 9 years ago, # ^ |   +11 I think your Floyd algo is wrong
•  » » 9 years ago, # ^ |   +11 replace  timer[i][j][k] = min(timer[i][j][k], timer[i][j][f] + timer[i][f][k]); to  timer[i][k][f] = min(timer[i][k][f], timer[i][k][j] + timer[i][j][f]); 
•  » » » 9 years ago, # ^ |   0 Thank you for your help! For some reason I was sure that there are two possible places for the cycle through intermediate vertex: inside and outside other two cycles.
•  » » » 9 years ago, # ^ |   0 Thank you. My implementation of Floyd was wrong also, and got the same error. I really shouldn't try to save memory:(
•  » » 9 years ago, # ^ |   +8 My code was wrong on test 11 because of this line: f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v]... I resubmitted the code after replacing it by f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v] and got accepted.
•  » » » 9 years ago, # ^ |   +11 this part is ok in his code
 » 9 years ago, # |   +14 Thanks poopi & piloop for your great and hard contest!It was an honor for me to participate in a contest whose Problems were prepared by Rivals of my brother in ACM of Tehran Regional!Hope you the best in World final! ;)
 » 9 years ago, # |   +8 Div1-C Weak Memory : I was going in the right direction and thought a BFS with Distance array and pushing a vertex again into the Q when visited with smaller distance will TLE. But it worked fast in practice now. What is the worst case complexity of each such BFS ?
•  » » 9 years ago, # ^ |   +3 Yeah! I spent some 20 minutes during the contest trying to analyze the time complexity, but didn't get anywhere :(Any help on how to do it?..
 » 9 years ago, # |   +6 когда рейтинг пересчитают! :(
•  » » 9 years ago, # ^ | ← Rev. 2 →   -26 нееееееееееееееееееееееееееееееет..........[спойлер]
 » 9 years ago, # |   +1 My code got TLE in DIV-1 B in the 12th case. After contest, I changed my 'long long' variables to 'int' and it passed. I know 64bits datatypes will be slower than the 32bit ones, but is it slow enough to give TLE? specially in a fast judge like CF?
•  » » 9 years ago, # ^ |   +3 I think it's slow because intended solution is O(n^4), while yours is O(k*n^3).
•  » » 9 years ago, # ^ |   +6 Your solution runs in about 1000*60*60*60 operations. But "correct" solution should do about 60*60*60*60 operations. So it will be really hard not to get TL even if you use int. But if you use long long you will obviously get TL.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +3 1675898Solution with m*n^4 (though pretty simple) operations passed system tests.
•  » » 9 years ago, # ^ |   0 Thanks for replies. Somehow I didn't realize that computing Ks >n is pointless.
 » 9 years ago, # |   +11 Won't there be any editorial for this round?
•  » » 9 years ago, # ^ |   -15 Maybe.
 » 9 years ago, # |   -20 It was held on Thursday,I had no time to take part in it. What a pity! T..T
 » 9 years ago, # |   -6 It was very good round :)))