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

Div. 2

**Attention! Editorial for all problems is available!**

Awesome, time of next three rounds are close!

Wow, first contest author from Kazakhstan

your name make me think about my favorite brower

catch a diaosi!!!

I think you're Chinese

YES YOUR RIGHT !!

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

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

Good Luck and Have Fun

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

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

f5 f5 f5 f5

this is the worst contest I've ever seen

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)

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

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.

Thank you very much! hehe!!

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

Mine is 25 25 25 100 & 25 50 50

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

Pretest 9 for Problem B Div 2 :(

I think pretest 9 is smth like this:

5

3 3 3 3 3 3 3 2 3

Found one special case:

`8`

`3 4 4 5 10 10 10 10 10`

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

I think the answer is 41

Yes, my fault. 41 is the correct answer.

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

Nothing was helping me, but total rewriting helped.

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

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

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

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

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.

no, 41

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

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

Answer should be 41

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

I think we must try get max numbers and then change some first on other, more big. I don't sure. http://codeforces.ru/contest/349/submission/4583482

Yes, It was correct solving. I got OK

no for examle 61 7 8 8 8 8 8 8 8 9 it should be 99811111

Thanks for this testcase.

Need to use DP for problem B.

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

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

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

Congrats for being RED :)

Thank you.

& whats fst?

It's Failure System Test.

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

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?

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

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

nearly same compared to you

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

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.

You must chhose number of game — m, then check, than all in array <= m and that free players more that m(for arbiter). http://codeforces.ru/contest/349/submission/4581586

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

i couldnt get why N * K — sum(a[i]) >= K.

It is obviously correct. Let

x_{i}be the number of rounds skipped byi'th person, . We needx_{i}≥ 0,X-x_{i}≥a_{i}, sox_{i}≤X-a_{i}. Summing up, . Consider arbitraryXsuch that this statement is true. Then you can takex_{i}=X-a_{i}- α_{i}, so that α_{i}≥ 0, . Since right side expression is ≥ 0, such α_{i}exist, this finishes the proof.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.

Actually D is just a quite straightforward application of this theorem: http://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma

Moreover, searching for

number of tuples of nonintersecting paths, we can see this article as second link in Google.This theorem was used in recent Japanese competition.

When will ratings be updated?

Can someone please gives some idea about DIV2 C?

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

Awesome problem-set..!!

Waiting to know solution of D div.2

deleted!

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

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

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

Sorry, I found my mistake :D

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

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

You have to generate the result, instead of storing the result in a string array. Hope that helps

I'm in div 1 now

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

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

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

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";

Your code is wrong with case like:

`7`

`25 25 25 50 50 50 100`

Answer should be "NO".

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.

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!

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.

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

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.

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

...problem with problem B DIV 2.

Where are you, editorial?

This question is a bit difficult to read

oh man i forgot it yesterday

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

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

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.

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

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.

Screencast

thanks a lot Egor! i really enjoyed watching this!

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

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

Still no editorial :/

Editorial, where are you?

Editorial

Please??!!Please post the editorial for div. 1!!!

Please post the editorial for div 2

Thanks for the contest!

Won't there be an Editorial?!

Thanks for the editorial too.

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

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

Big thanks for your reply :)

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

afor all elements of X,sumfor all big sets.Update a large set X: Update

ct(X).Query a small set X: Sum up

avalues of elements in X. Add to this the sum ofct(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 thissum(X).Can someone tell me how to solve div1 B and div1 C? I have no idea.

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.

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

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

Well, I have found the entry for English version. It may help me a lot.

Can you give the link for the English Editorial??

You can check here :)

Thanks mate