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

"PMP"? Why not "PIMP"? Sounds cool

(waiting for lots of minuses)

Hi Rebecca :)

Please let us know about the point distribution and difficulty ordering of problems also.

we'll have standard points distribution in both divisions.

Is problems sorted by difficulty?

yes, they are.

How is the main character (PMP) supposed to be pronounced? The closest I got was "pimp".

I thought about same thing but got lots of negative votes. Does it mean people pronounce it another way?

Hah, your comment was hidden, but now I saw you said the same. Nah, I suppose they just didn't like the joke =/

You should pronounce it same as "ACM", "ICPC", "MST", "MSC" and all other abbreviations. Thanks for your point.

You got what you wanted.

hope it's not three consecutive unrated rounds

I wish you not to change opinion after round :)

The third is the charm, right =)

That peter50216 solved all the problems gains me some belief about a rated round :)

I hope it will be very interesting!!!;)

I Like PMP!!!

I Like PvP!!!

I hope every one will solve at least 1st problem!!! xD

first from the end or from the beginning?

Break stereotypes — solve the first from the end!

and be bad guy!

at least 1 problem

I've heard that Iranians are especially strong in Maths. Should we expect some maths problems?

Anyway, hope everyone enjoys this round.

I read the notes of Div1.E Heaven Tour.

The problems were great, thanks!

Как решалась А div 1

Ну заметим, что еси уж мы цифру перекладываем, то так, как нам нужно.

Посмотрим, сколько можно не перекладывать: это кол-во чисел от начала a, которые содержаться в правильно порядке(возможно с чем-то между) в b

Thank. Very interesting contest.

How to solve problem C?

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

binary search is not needed.

Awesome and interesting problems, thank you very much!

It was fun : )

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?

It seems that you are only counting the ones with equal diagonals. Those with unequal diagonals are also possible.

Yes you're right, I was so stupid thinking during the contest that "sides equals <=> diagonals equals"... Thanks!

(x,y) (x+1,y) (x-1,y) (x,y+2) is not a rhombus: 3 vertex on one line.

Sorry, I have edited there are some minutes.

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

It reopens every contest by someone

Let's open! I've created array of 100010 elements instead of 200010 (thx Edvard (**fixed**) for hack =) )

Let me in! Let me in!

That was not me, that was homo_sapiens.

Sorry! >_< Too many red coders in room.

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.

Try using a code ;)

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. >_<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.I made the same mistake.

I tried to hack this code 2 times during contest but it passed somehow! (Div2 A)

http://codeforces.com/contest/189/submission/1673396

It ran for 18sec in my PC to produce output of this case: 4000 2 2 2

Compiled with right keys? It works for 13 seconds on my PC without optimisation, and 1.7 with O2.

How to solve problem D in div2?

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.

Thanks!

How to solve problem C div.2?

I used binary search.

смотри выше

Number of fixed points = max {i| b[:i] is subsequence of a}

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

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.

I think your Floyd algo is wrong

replace

to

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.

Thank you. My implementation of Floyd was wrong also, and got the same error. I really shouldn't try to save memory:(

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.this part is ok in his code

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! ;)

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 ?

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

когда рейтинг пересчитают! :(

нееееееееееееееееееееееееееееееет..........

[спойлер]

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?

I think it's slow because intended solution is O(n^4), while yours is O(k*n^3).

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.

1675898

Solution with m*n^4 (though pretty simple) operations passed system tests.

Thanks for replies. Somehow I didn't realize that computing Ks >n is pointless.

Won't there be any editorial for this round?

It was very good round :)))