piloop's blog

Codeforces Round #119
By piloop, 12 years ago, In English

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

  • Vote: I like it
  • +211
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
12 years ago, # |
  Vote: I like it -85 Vote: I do not like it

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

(waiting for lots of minuses)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    we'll have standard points distribution in both divisions.

    → Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +25 Vote: I do not like it

      (waiting for lots of minuses)

      You got what you wanted.

      → Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

hope it's not three consecutive unrated rounds

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I Like PMP!!!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

Anyway, hope everyone enjoys this round.

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I read the notes of Div1.E Heaven Tour.

→ Reply
»
12 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The problems were great, thanks!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank. Very interesting contest.

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem C?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Awesome and interesting problems, thank you very much!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was fun : )

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It reopens every contest by someone

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 9   Vote: I like it +13 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      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<<c<<" "<<c2<<" "<<c3<<std::endl;
      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D in div2?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C div.2?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used binary search.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    смотри выше

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I think your Floyd algo is wrong

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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]);
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -26 Vote: I do not like it

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

    [спойлер]

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like 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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      1675898

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Won't there be any editorial for this round?

→ Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

It was very good round :)))

→ Reply