caustique's blog

Codeforces Round #202
By caustique, 11 years ago, translation, In English

Hello, Codeforces!

Codeforces Round #202 will take place today, September 27 at 19:30 MSK.

The idea behind the round was born when my friends and I were interning at Facebook this summer. This round probably has the highest number of authors for a Codeforces round to date. The authors of the problems are Azizkhan Almakhan azizkhan, Michael Kolupaev al13n, Filip Hlasek fhlasek, Ivan Mandura budabudimir and myself, Igor Demidov caustique.

Maxim Korystov dark_ai, Alexander Fedulin Jughead and Ibragim Ismailov ibra, Vladimir Chalyshev cmd and Sergey Sklyanichenko Sklyack helped us with preparation of the round.

The ideas behind the 2 problems were inspired by Anton Ermilov ant.ermilov and Dmitry Krasnov navi-spb.

Testers of the round are Alexey Safronov yarrr and Alexey Shmelev ashmelev.

I would also like to thank Gerald Agapov Gerald for his help in preparing the contest.

I hope you find problems interesting and diverse. I'm sure that everyone will find the problem to their liking.

Scores are as usual 500-1000-1500-2000-2500.

Good luck and have fun!

Congratulations to the winners!

Div. 1

  1. ilyakor
  2. rng_58
  3. EnumerativeCombinatorics
  4. ftiasch
  5. phtniit
  6. SillyHook06
  7. niyaznigmatul

Div. 2

  1. zhk
  2. love_kd
  3. alex_k
  4. arpit11293

Attention! Editorial for all problems is available!

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

Comments Comments (110)
| Write comment?
»
11 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Awesome, time of next three rounds are close!

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

Wow, first contest author from Kazakhstan

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

I'm damm sure, this gonna be some round !!! I mean 5 authors => awesome + cool + exciting !!! :)

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

i hope there won't be any mathematical problems , but still g & hf to all

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

Many authors = Many personalities = Different kind of problems = Good for everyone ;)

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

Scores will be announced closer to the beginning of the round. 2 min remain :|

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

this is the worst contest I've ever seen

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

1st problem has very weak pretests. I hacked 5 solutions with 25 25 25 100 ))

25 25 50 50 100 is also good for hacking ))

Thx for contest)

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

    Can you tell me how to hacked other's solution?

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

      After you pass the pretest, lock your problem in the dashboard using the icon like a lock, then you can view and hack others' solutions in the room page by double clicking on scores of that problem.

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

Many tricky cases in problem A(Div 2) ... :D

I hacked six solution with 25 25 25 100 &

25 25 25 100 50 ...:)

Thanks for the contest... :)

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

the problems of today's Div-2 contest are tougher than usual Div-2 contests! i wonder why?

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

Pretest 9 for Problem B Div 2 :(

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

    I think pretest 9 is smth like this:

    5

    3 3 3 3 3 3 3 2 3

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

    Found one special case:

    8

    3 4 4 5 10 10 10 10 10

    Though I didn't pass yet. Answer should be 23.

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

    To hell with this pretest 9 on Problem B Div 2.

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

    Nothing was helping me, but total rewriting helped.

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

    Might be one of these : 11 3 3 3 3 3 3 3 3 4

    OR

    9 2 10 10 10 10 10 10 10 9

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

    well, as it turned out, Pretest 9 was a big test case, different from what we expected :P

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

Why div.2 so hard just on problem B... Do I only have to solve it by DP?

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

    I solved the problem by dp but I saw some greedy solutions but I do not know if there correct

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

      Found one special case:

      8

      3 4 4 5 10 10 10 10 10

      Though I didn't pass yet. Answer should be 41. Greedy seems to be unavailable.

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

        no, 41

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

        it should be 41 41 > 23 I use greedy for my solution but no so sure about it :D

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

        no answer should be 41 since you can use 4 (costs 5 ) and 1 (costs 3)

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

    by a glance on the question I think we need to use at most 2 digits for all optimal solution. O(9*9)?

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

    Need to use DP for problem B.

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

      nope, greedy solution is ok just find maximum digit can be made and use the remainder to change some first digits into higher digit

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

        Cool.. Thanks for your input. I did use greedy at first but messed up with the implementation.

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

Hope no FST, and be red after this round. :D

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

Wow, so many Runtime Errors in final testing for Div1 B. Even Egor failed this problem.

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

Almost everyone who solved problem Div-1 A did binary search, this is my accepted solution: 4576049

It's just O(1) (after reading the input), to be honest I couldn't prove if this solution is correct or not. Can anyone check it please and tell me why it's correct? Or are the test cases weak?

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

    I can prove only that it is correct — my O(1) solution passed. Proving correctness is harder.

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

    http://codeforces.com/contest/348/submission/4576666

    nearly same compared to you

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

    answer >= max(a[i]) and the second inequality is your binary search's inequality. Solve this system and be happy :)

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

    Can you please explain how you applied Binary Search on this problem? I really want to know, because I could just think of brute-forcing it.

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

    It's easy to see. Let the answer be K. So the first person can be supervisor in (k — a[0]) games, the second in (k — a[1]) games and so on. So (N * k — sum(a[i])) games there is a supervisor. It must be bigger or equal than K cause there were K games. N * K — sum(a[i]) >= K. K * (N — 1) >= sum(a[i]). And we didn't mentioned that K >= max(a[i]) (that's obvious). So the answer is MAX(MAX([i]), sum(a[i]) / (N — 1));

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

    It is obviously correct. Let xi be the number of rounds skipped by i'th person, . We need xi ≥ 0, X - xi ≥ ai, so xi ≤ X - ai. Summing up, . Consider arbitrary X such that this statement is true. Then you can take xi = X - ai - αi, so that αi ≥ 0, . Since right side expression is  ≥ 0, such αi exist, this finishes the proof.

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

Really intresting problems. I liked all of them , especially D form Div1. I think these were very original problems. Congrats to the authors ! Thank you , you made my day ! :D

Btw, can someone explain how to do B-div1 & D-div1.

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

When will ratings be updated?

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

Can someone please gives some idea about DIV2 C?

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

    we can solve it by making an equation like this : ans ==> the answer/minimum game must be make

    (ans-a1) + (ans-a2) + ... + (ans-an) >= ans (the sum of all players become supervisor must be greater or equal than the minimum game)

    in short we can found ans >= ((a1+a2+...+an) / (n-1))

    but only by that it'll be failed in test case when there are some players that didn't need to be supervisor at all (in example case : 8 4 4 4 4 1 1 1 1 should output 4 instead 3) so the answer become max(ans,max_game_player_needed)

    hope it help :D pls correct me if im wrong

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

Awesome problem-set..!!

Waiting to know solution of D div.2

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

deleted!

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

    else if (y > 2) { y-=3; }

    must be else if (x > 2) { x-=3; }

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

Hi there! :)
I submitted my B problem's solution in the contest, and the checker gave wrong answer; but in my PC and in even in the custom test, it gives the right answer! Even I submitted it after the contest, but it gave wrong answer too. Here's my submission. Can anybody give any reasons for this? I would be happy if Codeforces moderators could explain this. Thanks! :D

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

Did anyone in Division 2 exceed memory with a DP on Problem B? I haven no idea what happened on mine. :O

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

    You are using a String array of size 10^6 , so it is so obvious the reason why

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

I'm in div 1 now

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

Can anyone help me with Div.2 Prob. A ? Link : http://ideone.com/b0HLLw

It shows WA on test case 12. Please help. Thanks.

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

    It looks like you totally misunderstood main problem statement or solution idea. ;-)

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

      Please correct me if I am wrong. With taking input, I am checking whether the desired change is available or not. If true, I am adding 25 to the counter, else , I am printing "NO";

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

        Your code is wrong with case like:

        7

        25 25 25 50 50 50 100

        Answer should be "NO".

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

          Thanks to all for replying. I got my mistake. The shopkeeper can only give change with the help of those bills which he has got from previous transactions i.e; by using 25, 50 or 100 bills.

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

Hi everyone!

My solution for Div1 B failed on final test 32, and it cannot be viewed completely under the submission. Does anyone know what final test 32 for Div1 B is?

Thanks!

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

    I do not know about test case #32. However, there goes a common mistake that lcm exceeds "long long" range, which may be divulged under a huge input, but you can pass through the pretest with the mistake.

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

I was hoping that there would be at least one Big Lebowski fan around here, so I introduced few references into the problem statement. Hope you enjoyed the round :)

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

Could someone explain why this submission has became tl? It's a simple greedy that a lot of people have got accepted with this method. http://codeforces.com/contest/349/submission/4581168 Thanks.

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

    for(int j = 8; i >= 0; j--) ...

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

problem with problem B DIV 2.

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

Where are you, editorial?

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

This question is a bit difficult to read

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

oh man i forgot it yesterday

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

div 1 problem is really challenge for me, i wonder where is the tutorial?

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

When will the Editorial come? Can't Wait to see it for Div. 1 B...

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

Problem B is unpleasantly similar to 2012/13 Czech/Slovak Olympiad in Informatics (these 2 share the problems and are held at the same time), Regional round, problem 2. The only difference is that we had a binary tree in that problem. The general one needs extending the idea and there is a lot of possible overflow to take care of (since that problem was theoretical), but I feel that it helped me get a better result.

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

    Hey Xellos, I like a lot your way of explaining problems ideas, so could you give a short description for Div2 problems. A sort of short tutorial :)

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

      I would, but I still haven't solved Cdiv1, and I kinda don't want to make an actual editorial if I'm not the author. If it doesn't appear in several days and I solve the rest of the problems, I might post one instead.

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

Screencast

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

    thanks a lot Egor! i really enjoyed watching this!

    can u continue to make screencasts for future contests? thanks in advance! :)

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

For Div-2 B my approach,

Find the minimum d ( minimum amount which takes to paint a digit with highest index) and divide the total paint by min d. This number gives total no of digits which can be painted. i.e. the answer will have this many digits.

Now only thing you can do is, if there is still left over paint ( total paint — paint used upto this point ), you can improve, in the sense you can replace already used digit and left over paint with a higher digit by using greedy method.

Repeat the improvement until you have some left over paint and there is a digit with higher index which you can replace.

My Solution

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

Still no editorial :/

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

Editorial, where are you?

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

Editorial Please ??!!

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

Please post the editorial for div. 1!!!

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

Please post the editorial for div 2

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

Thanks for the contest!
Won't there be an Editorial?!

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

Thanks for the editorial too.

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

Hi! Does anyone of you know an approach to solve Div1 C problem? I'm very curious about its solution.

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

    Thanks to SillyHook06, whose superb contest submission helped me solve this awesome problem !!

    The essential idea is to bifurcate all given sets as big and small: Let us denote by T the collection of all big sets [those sets which have size >= sqrt(n)] and by S the collection of all small sets [those sets which have size < sqrt(n)].

    What remains is to exploit the following two properties:
    1) Each element of S contains atmost sqrt(n) elements.
    2) The total number of elements in T is atmost sqrt(n).

    To do this, one can precompute for each big set, the sizes of its intersections with all other sets. Precomputation takes O(n*sqrt(n)) and processing each query takes O(sqrt(n)).

    I find it difficult to state all details in a short post. Here is my practice submission (with a few comments): 4607191

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

      Big thanks for your reply :)

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

      I will attempt to briefly explain the query processing:

      a[i] stores the current value at position i considering only the updates on small sets.
      (eg: The initial array is all zeroes. Big set #0 and small set #1 both contain the index 3. Set #0 is updated with 4 and set #1 with 7, then a[3]=7)
      ct[i] stores the total update value on big set i
      (eg: if set #2 is a big set and is updated thrice with values 2,6,3 then ct[2] is 11).
      sum[i] stores the current result of big set i considering only the updates on small sets
      (eg: The initial array is all zeroes. Set#0 is big and set #1 is small. The intersection of these sets is of size 2. Set #0 has been updated twice with 3,4 and set #1 once with 5. Then sum[0] will store 10, ignoring all the updates on all big sets including itself.)

      Update a small set X: Update a for all elements of X, sum for all big sets.
      Update a large set X: Update ct(X).

      Query a small set X: Sum up a values of elements in X. Add to this the sum of ct(Y)*|intersection(X,Y)| over all big sets Y.
      Query a large set X: Sum up ct(Y)*|intersection(X,Y)| over all big sets Y. Add to this sum(X).

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

Can someone tell me how to solve div1 B and div1 C? I have no idea.

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

    How about reading the comment just above for div1 C before you ask?

    div1 B: DFS the tree; the sum in a subtree of vertex i must be a multiple of some number M[i]; then, M[i]=LCM(M[all sons])*(number of sons of i), find the largest sum in subtree of a son satisfying that. Watch out for long long overflow.

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

      I am sorry I haven't seen the previous comment.Thanks for your reply :)

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

I hope someone can translate the editorial into English ! Thanks.

→ Reply