A coder can apply his breathtaking coding skills not only in different search engines but also in the mobile game industry. It is an option in Russia. If you do not believe — check this out: ZeptoLab company that created the world famous Cut the Rope game offers you the opportunity to see this for yourself. And yes, we are in Moscow.

It's not a secret that those who strive to achieve top coding skills — work hard, including work on his self-education. Here in ZeptoLab we aim to create the area that strongly encourages self-development. Specifically, we have recently purchased a company library with everything necessary to get new knowledge, an improvised reading room with sofas and armchairs.

We also conduct developer's contest inside the company so that our ZeptoCoders could solve non-trivial problems and impress each other with zeroes and ones. The winners get glory, valuable gifts and name-encrusted weapon (it's a joke, it’s not weapon)

We have recently opened our own algorithmic school here in ZebtoLab and the teacher is no other than the creator and the head of the whole wide Codeforces, Mike Mirzayanov! He is well-known among developers: Mike has trained a team that became the world champion in programming, so it's not hard to imagine the opportunities opened for ZeptoLab developers and the whole company. It's the first time that Mike teaches in such format, there are hardly any more examples of such corporate education systems in Russia and throughout the world.

Algorithms play an important role for us as the requirements for developers are quite tough: ideally, the application should output 60 frames per second on the target gadget. All game logic calculations should be very quick and preferably, with simple and not amortized complexity. Besides, we can afford a fine pre-processing to transport some calculations to the stage at which resources for the game are prepared. Understanding this facts, alongside with many more is the key to the quick gameplay. That is why we support the algorithmist's movement.

It's the first time when Zeptolab holds an algorithmic development contest based on Codeforces. Ingenious problems, fierce developer rivalry and cool prizes are waiting for you:

- 1st prize: Ipad Air, plush Om Nom, the championship T-shirt
- 2nd-3rd prize: Ipad Mini, plush Om Nom, the championship T-shirt
- 4-th-30-th prize: plush Om Nom, the championship T-shirt
- 31st-50th prize: the championship T-shirt

And just for some suspense, we add another prize:

We will randomly give the IPad Mini Retina to the person who makes it to the top 50 list of the contest champion. The IPad winner will be chosen like this: we sum up the times of all successful attempts of three top winners (in seconds starting from the start of the contest) and take a row with number *s* % 47 + 4, where *s* is the resulting sum. Being true coders. If the resulting line divides the place, then the priority goes to the earlier person to submit his last solved problem.

Besides, the person who shows good results in the contest will have the opportunity to apply for a job in our company by a simplified scheme. If you'd be interested to try working in the ZeptoLab team, tick the corresponding square at the registration.

You can find out more about what working with us is like at http://zeptoteam.ru/.

The championship will be conducted in a single round. The contest will go by the Codeforces rules. The round will be rated and both divisions can participate.

The date and time of the contest is: June 13, 2014, 15:30PM — 18PM (UTC).

The problem scores are: 1000-1000-1500-2500-2500-3000.

The contest is over! Thanks for all the participants! We hope you like the problems and the contest! Our special congratulations to the winners:

- The 1st place — KAN (Nikolay Kalinin, Russia, Nizhniy Novgorod) — iPad Air
- The 2nd place — winger (Vladislav Isenbaev, USA, Facebook) — iPad Mini
- The 3rd place — tourist (Gennady Korotkevich, Russia, Saint Peterburg, ITMO) — iPad Mini

All the participants on the places 1-30 will receive presents: plush Om Nom and the championship T-shirt. All the participants on the places 31-50 will receive championship T-shirt!

Additional prize will be received to the the 21st place winner: package.zaic (Vadim Zaycev, Russia, Novosibirsk, NSU).

I think it will be good contest. We will see.

What is the degree of difficulty of problems? like codeforces one?

Didn't you see this when editing your comment? :

`You may edit your comment only for fixing grammar mistakes or small changes.`

`Do not change the main idea of your comment.`

`All previous revisions are available for others. Are you sure you want to edit comment?`

because I do a big mistake that :

I post my comment (in russian) mode :|

then I edit that comment and that comment change automatically :D

Do is incorrect.

Did is correct.

Thank you :|

You're welcome. :)

The contest lasts 2h30. It has how much problems, viktork!

Seems very funny :D I like this kind of round.

How will this round be rated (keeping in mind that both divisions can participate)?

like this round

Good Bye 2013

I love cut the rope and I will love this contest

Oh, Cut the Rope is an interesting game, and I have designed a problem based on the game mechanics in "DJ Box": CandyOnDisk.

I saw the website is in Russian, does it means the working language in ZeptoLab is Russian?

After this announcement I decided to try Cut the Rope app really really it's Amazing game

this is an English version

http://www.zeptolab.com/

Wow, a good problem! If you wish we could ask you to be a co-author of the following possible contests in the future. We are an international company, but yes, our working language is mostly Russian at the moment.

Yes, there are mostly russian-speakers here. But we do have offices outside Russia — so your English language won't be a problem :)

Watch it if you want

This video make me download this nice game it's really has a nice character I love it :)

Does that mean Top 50 have T-shirt with their name on it? Really awesome! Achieving that result is hard though..

Can anyone participate or it's just for Russians?

There is no difference

Registration started earlier than expected. :))

Lol, I wanted to google "Cut a rope", but instead "cut the rope" I mistakenly typed "cout the rope" :P.

I remembered when I told my friend do you watched breakpoint Series and I mean Prison Break Series :D

How many problems will there be in this contest?

"The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, Go, D and JavaScript."— and usually Perl is not forbidden! Thanks for early opening of registration and early notification about round.Will there be any indicator of who is the random owner of iPad Mini during the contest?

UPDDamn, I realized what was wrong with my comment 8 months later I posted it O_T By "random" I didn't really mean random but (quoting from the post):Does this contest influence the rating?

The round will be rated

When score distribution will be announced?

Why is score distribution so important for many people?

Because of thinking about strategy. and knowing number of problems and preparing file for each problem.

Registration users are 4664 :) lucky palindrome

Can two items have the same "H" in Problem A? If yes, can "Om Nom" eat both of them? Or just one of them? Thank you.

I suggest you ask stuff like this through the "Ask a question" form (see contest dashboard)...

Thank you! Contest was fantastic.

This comment and your avatar makes a perfect combination :D. But agree, contest was awesome.

The little drawings of Om Nom in each problem were really nice and cute :)

i don't know why but for almost an hour I thought in problem C you could only use the last sent level!

did anyone else understood the problem in this way ?

I wasted a ton of time thinking the same thing!

The same >.<

me too !

(

Me too, but then I looked at the sample test :P.

i have made this mistake (not solving/looking at the sample test) a lot of times and i never learn :D

How was C supposed to be solved?

Create a complete graph: weight between level i and j is min(n*m, w * their difference).

The answer is then n*m + Min cost span tree in this graph.

Minimum spanning tree

It is nice to see the beautiful pictures in the statement. :)

Seems the hard tasks are all about data struct and the code is long, looks like an OI contest.

Yeah, except OI involves long codes because it has full feedback and no time penalties.

Can anyone please tell me why this is not a correct solution for C ?

It is.

I got WA in test case 3. This is 3rd case of C.

Could you be printing null characters or something? Link to your code.

http://codeforces.com/contest/436/submission/6883198

You output 12 as the cost, while it was actually 11.

In my pc it generates the output which i gave to u, but for the same code codeforces generate another output. Although my solution may be incorrect, thanks anyway. I am looking forward to it.

After sort(), the order of edges which have the same w is indefinite. And unfortunately your algorithm for calculating cost is incorrect. These are the cause of different output. Additionally,

`if(par[r] = r) return r;`

must be`if(par[r] == r) return r;`

It appears correct to me.. Did it give you WA?

Yes it gave WA in test case 3, I include my solution.

The output is correct , may be the way that are you printing the output is the problem , maybe you are using printf("%d\n") y using long long .

Great problemset... However, so many participants worked out only A, B and C. And among them, they only compete who code faster... Sad story :(

Is there going to be an editorial?

When will be the editorial available?

Wow fast system test!

relevant comment :D

I am never able to hack anyone's solution until my own solution for that problem is wrong and I realize that after locking the solution :(

Problem A is not clear. I thought after Om Nom eats a candy, it continues hanging on that rope instead of jumping back to the ground :( I lost many precious minutes.

No, it does not. (At least: I did not assume that and got AC... I'm not sure about anything after seeing the results of problem E...) How would it do that, anyway? What a strange idea...

Me too :( In Cut the Rope the game, Om Nom cannot hang onto a normal rope, though...

Will the problems be available for solving after the contest? Took just a little too long to solve E ={

I can't find my mistake in Problem A, please Help

My code

Consider input:

Your program will start with type 1 (because the mass is large), and will be able to collect only 2 candies. The optimal answer is 3.

I cant submit my code . Please fix it.

Congratulation to package.zaic!!! You won an iPad.

Luckiest guy of Friday the 13th! Congrats :D

Saturday the 14th.

134-th place expected, 134-th place in the standings!

And fast systest is fast :D

Achievement unlocked: failed systest on a problem from Petr Mitrichev Contest :) (problem F)

orz

Through author of reference solution for that problem take a glance at the code in polygon and decided to rewrite from scratch and got OK ;)

Petr tasks are so hard, so even Petr can't solve them.

Do you know any solution faster than O(n*sqrt(n))?

I think I had some O(n*polylog(n)) in mind when I gave this problem, but I can't remember now :(

I solved this problem on your contest, but for some reason this time I decided to use segment tree instead of sqrt decomposition. Unluckily, I realized that the idea is wrong and sqrt decomposition can't be replaced with segment tree in this case only 12 minutes before the end of the contest after spending almost an hour in debugging. And I realized that I've already solved this problem only after reading your post here :)

I implemented incorrect segment tree solution too, but I had more time to rewrite it :)

problem F is equivalent with which one of your problems?

It hasn't been published, but it's called "Business As Usual".

Thank you.

So was your code actually wrong? I'm starting to think problems are not available for practice because they're double checking the test cases of that problem =P

Yes, it was wrong. The problem on my contest didn't allow a[i]==0, and the solution didn't handle that correctly (but only one part of it, so it worked when n<=sqrt(maxn)) :)

is there any chance of interview from with rank 465

Hey! Look at this: http://codeforces.com/profile/worse

He/She is trying to be the worst in every contest! So He/She solve a problem, and hack solutions with easy testcases!

Why do you know ?

you can look at the standings, and turn to the last page.... you will see two funny coder....

relevant comment

In problem E, is the correct solution to split the levels into two groups, where b>a*2, and b<=a*2, and choose how many stars to get from each group (since for both groups it is possible to find the answer in O(1))?

I had something completely different in mind: sort the levels by 1-star cost; if we pick the rightmost (

i-th) level with 1 star, all levels to its left must be either solved for 1 or 2 stars (otherwise, we have a better solution). Then, if we picked the numberKof 2-star levels to its right, then we know how many to its left need to have 2 (or that it's not possible). It's clear that we pick the cheapest ones (byb_{i}to its right, byb_{i}-a_{i}to its left) then. The cost of this first increases and then decreases as we increaseK, because what we add levels with largerb_{i}and remove levels with smallerb_{i}-a_{i}. Now, we iterate over allifrom left to right, the sets that we should pick don't change much with each iteration, so we just need set<>s to simulate it. I'm getting TLEs and other fails, though, so maybe it has a loophole... but it's hard to code, anyway.My idea was that if for all levels we have b>a*2, then we can make a list of a and b-a for all levels and sort it. If the optimal solution includes b-a, then it must also include a. If for all levels we have b<=a*2, then the optimal solution can have at most one level with 1 star, all others must have 2 stars.

So we split all levels into these two categories, precompute partial sums as required, and choose how many stars we want to get from each category (obviously, the optimal answer gets exactly w stars).

I would like to thank dreamoon_love_AA for sharing the 51st place with me. It is comforting to know you are not the only one who is the first to win no material prize.

DEL

Have result ?

please update the ratings soon:)

I hope that

I got the logic for C but couldn't figure out how to print operations in order. When i figured it out there was only 1 min left. Bad luck :(. Anyways when will the problems be available for practice.

Dunno what you did, but I just found the differences between levels; these are the costs of edges of a complete graph (+ 1 node with edge costs

NMfrom it), and I just need to find its minimum spanning tree. That's done by adding edges, so I have the edges' order given directly by algorithm.I found the MST using Kruskal, than I was not able to figure out the ordering about which I came to know when I submitted my solution the one without ordering and got WA on 1st testcase. Later I figured out that I should do DFS to get the order but only 1 min was left and couldn't code it it in time.

And I also started out at around 9:35 IST (around 35 minutes late).

Not a good idea — if you don't submit anything, it's as if you didn't register at all. You should've waited until the contest was over and virtual-participated.

I meant to say I started 35 minutes late. I have correctly submitted A and B but couldn't submit C after correcting the ordering.

Yes, I understood that. I'm saying that you shouldn't have submitted anything.

Will keep this suggestion in mind from next time. And now I am again Expert :(

I did the same thing and wasn't sure how to find the order. Then I switched to Prim's algorithm, which gives you the right order for free.

This is a really nice idea. Thanks for this one :)

If you got the MST, you can pick any root and simply print it out in DFS/BFS order. Prim's algorithm gives a simpler solution, though, because you can use N^2 instead of priority queues, and get the edges in the correct order.

You may consider using Prim instead, it's easier to write edges back

UPD: has been answered above. I didnt mean duplicate comment. sorry :(

fix it -_-

How can I resubmit my solution ?!

The system don't let you resubmit the code submitted

editorial and rating are wanted!!!

quickly ! quickly !

Since I have made it to top 50, what does "name-encrusted weapon" means? Itching to get that :P

In problem A, many people got WA on 37th test case and me too. Can someone tell me the trap of this test case? Thanks!

Try this test:

3 2

0 1 1

0 2 2

1 4 4

i hacked this solution with the same input.

well, not totally the same, but i guess our

ideasare. :)Mine failed on 36th :(

waiting DmitriyH' statistics :)

I just learned that (a maximization version of) E is known from a Polish middle-school OI :) And, if you're Polish, here's a link to a video editorial of it: https://www.youtube.com/watch?v=hhrLaokKBtk

Yes, I watched that during the contest XD.

It was a funny story, because few months ago I was solving exactly the same problem in TopCoder, but for n<=8 as a part of some 500pts problem and I told my friend about it and then he told me that johnasselta proposed this for a middle-school OI, but I haven't came up with a solution, but today I learnt that this problem has a video editorial xD.

Is there any link to this OI problem?

i just noticed that the

OIGlogo is very similar to theCFlogo :)Is there any way to see div2 only ranks?

Round Stats

My screencast: http://codeforces.com/blog/entry/12682

In problem A test 5, how the answer is 2? Why it is not 7?

`What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?`

7 is impossible as there is only one caramelYou can't eat the same type (1) twice in row, you can't start with type 1 (not enough high), and if you eat the (0 1 3) first, you can eat one type 1, and nothing else (you are still not high enough to eat 0 20 3).

Tnx. So I misunderstood about the meaning of 'in a row'.

Finally I'm RED!!!! After failed on TopCoder SRM 624 because of stupid MOD issue :'(

Anyway, thanks for the amazing round. I will remember this round forever :)

Congratulations! I wish someday I become red too like you :)

How amazing it is! viktork became 21th top-contributor because of only one blog. Most positive blog ever.

+710! really amazing!