By viktork, 8 years ago, translation,

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

What to apply to ZeptoLab?

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

Announcement of Zepto Code Rush 2014

• +726

 » 8 years ago, # |   +3 I think it will be good contest. We will see.
 » 8 years ago, # | ← Rev. 3 →   0 What is the degree of difficulty of problems? like codeforces one?
•  » » 8 years ago, # ^ | ← Rev. 4 →   -11 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?
•  » » » 8 years ago, # ^ |   0 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
•  » » » » 8 years ago, # ^ |   -35 Do is incorrect.Did is correct.
•  » » » » » 8 years ago, # ^ |   +6 Thank you :|
•  » » » » » » 8 years ago, # ^ |   0 You're welcome. :)
 » 8 years ago, # |   -7 The contest lasts 2h30. It has how much problems, viktork!
 » 8 years ago, # |   0 Seems very funny :D I like this kind of round.
 » 8 years ago, # |   0 How will this round be rated (keeping in mind that both divisions can participate)?
•  » » 8 years ago, # ^ |   +11 like this round Good Bye 2013
 » 8 years ago, # |   -32 none of your apps are for UBUNTU!why?
 » 8 years ago, # |   +16 I love cut the rope and I will love this contest
 » 8 years ago, # |   +28 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?
•  » » 8 years ago, # ^ |   0 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/
•  » » 8 years ago, # ^ |   +21 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.
•  » » 8 years ago, # ^ |   +21 Yes, there are mostly russian-speakers here. But we do have offices outside Russia — so your English language won't be a problem :)
 » 8 years ago, # |   0 Watch it if you want This video make me download this nice game it's really has a nice character I love it :)
 » 8 years ago, # |   +33 Does that mean Top 50 have T-shirt with their name on it? Really awesome! Achieving that result is hard though..
 » 8 years ago, # | ← Rev. 2 →   0 Can anyone participate or it's just for Russians?
•  » » 8 years ago, # ^ |   +30 There is no difference
 » 8 years ago, # |   0 Registration started earlier than expected. :))
 » 8 years ago, # |   +47 Lol, I wanted to google "Cut a rope", but instead "cut the rope" I mistakenly typed "cout the rope" :P.
•  » » 8 years ago, # ^ |   +22 I remembered when I told my friend do you watched breakpoint Series and I mean Prison Break Series :D
•  » » » 8 years ago, # ^ |   +60
 » 8 years ago, # |   +9 How many problems will there be in this contest?
 » 8 years ago, # |   0 "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.
 » 8 years ago, # | ← Rev. 2 →   0 Author's color is as same as plush Om Nom xD maybe they are same person...
•  » » 8 years ago, # ^ |   0 LOL, I'm same color as Batman too ^_^
•  » » » 8 years ago, # ^ |   -15 I answered back my self, then i guess i'm Gollum too :D
 » 8 years ago, # | ← Rev. 2 →   -16 Will there be any indicator of who is the random owner of iPad Mini during the contest?UPD Damn, 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): 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.
 » 8 years ago, # |   +7 Does this contest influence the rating?
•  » » 8 years ago, # ^ |   +4 The round will be rated
 » 8 years ago, # |   +9 When score distribution will be announced?
•  » » 8 years ago, # ^ |   +4 Why is score distribution so important for many people?
•  » » » 8 years ago, # ^ |   +3 Because of thinking about strategy. and knowing number of problems and preparing file for each problem.
 » 8 years ago, # | ← Rev. 2 →   +8 Registration users are 4664 :) lucky palindrome
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   +11 I suggest you ask stuff like this through the "Ask a question" form (see contest dashboard)...
 » 8 years ago, # |   +29 Thank you! Contest was fantastic.
•  » » 8 years ago, # ^ |   +18 This comment and your avatar makes a perfect combination :D. But agree, contest was awesome.
 » 8 years ago, # |   +63 The little drawings of Om Nom in each problem were really nice and cute :)
 » 8 years ago, # |   +45 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 ?
•  » » 8 years ago, # ^ |   0 I wasted a ton of time thinking the same thing!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12
•  » » » 8 years ago, # ^ |   -8 yav he he
•  » » 8 years ago, # ^ |   -8 The same >.<
•  » » 8 years ago, # ^ |   0 me too !
•  » » 8 years ago, # ^ |   0 (
•  » » 8 years ago, # ^ |   +16 Me too, but then I looked at the sample test :P.
•  » » » 8 years ago, # ^ |   -8 i have made this mistake (not solving/looking at the sample test) a lot of times and i never learn :D
 » 8 years ago, # |   +1 How was C supposed to be solved?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 8 years ago, # ^ |   0 Minimum spanning tree
 » 8 years ago, # |   +44 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.
•  » » 8 years ago, # ^ |   0 Yeah, except OI involves long codes because it has full feedback and no time penalties.
 » 8 years ago, # |   +2 Can anyone please tell me why this is not a correct solution for C ? 1 3 5 2 ABA BBB BBA BAB ABB  11 5 0 2 5 1 5 4 2 3 1 
•  » » 8 years ago, # ^ |   +1 It is.
•  » » » 8 years ago, # ^ |   0 I got WA in test case 3. This is 3rd case of C.
•  » » » » 8 years ago, # ^ |   0 Could you be printing null characters or something? Link to your code.
•  » » » » » 8 years ago, # ^ |   0
•  » » » » » » 8 years ago, # ^ |   +16 You output 12 as the cost, while it was actually 11.
•  » » » » » » » 8 years ago, # ^ |   0 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.
•  » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +7 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;
•  » » 8 years ago, # ^ |   +3 It appears correct to me.. Did it give you WA?
•  » » » 8 years ago, # ^ |   0 Yes it gave WA in test case 3, I include my solution.
•  » » 8 years ago, # ^ |   +3 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 .
 » 8 years ago, # |   +35 Great problemset... However, so many participants worked out only A, B and C. And among them, they only compete who code faster... Sad story :(
 » 8 years ago, # |   +2 Is there going to be an editorial?
 » 8 years ago, # |   0 When will be the editorial available?
 » 8 years ago, # |   +2 Wow fast system test!
•  » » 8 years ago, # ^ |   -11
 » 8 years ago, # |   0 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 :(
 » 8 years ago, # |   -15 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 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...
•  » » 8 years ago, # ^ |   +1 Me too :( In Cut the Rope the game, Om Nom cannot hang onto a normal rope, though...
 » 8 years ago, # |   +11 Will the problems be available for solving after the contest? Took just a little too long to solve E ={
 » 8 years ago, # |   0 beautiful illustration)
 » 8 years ago, # |   0 What a system testing everything changed !!!
 » 8 years ago, # |   0 I can't find my mistake in Problem A, please Help
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Consider input: 3 1 0 1 1 0 1 1 1 1 100 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.
 » 8 years ago, # |   +10 I cant submit my code . Please fix it.
 » 8 years ago, # |   +32 Congratulation to package.zaic!!! You won an iPad.
•  » » 8 years ago, # ^ |   +15 Luckiest guy of Friday the 13th! Congrats :D
•  » » » 8 years ago, # ^ |   +3 Saturday the 14th.
 » 8 years ago, # | ← Rev. 3 →   +4 134-th place expected, 134-th place in the standings!And fast systest is fast :D
 » 8 years ago, # |   +354 Achievement unlocked: failed systest on a problem from Petr Mitrichev Contest :) (problem F)
•  » » 8 years ago, # ^ |   0 orz
•  » » 8 years ago, # ^ |   +9 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 ;)
•  » » 8 years ago, # ^ |   +326 Petr tasks are so hard, so even Petr can't solve them.
•  » » 8 years ago, # ^ |   +8 Do you know any solution faster than O(n*sqrt(n))?
•  » » » 8 years ago, # ^ |   +12 I think I had some O(n*polylog(n)) in mind when I gave this problem, but I can't remember now :(
•  » » 8 years ago, # ^ |   +14 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 :)
•  » » » 8 years ago, # ^ |   0 I implemented incorrect segment tree solution too, but I had more time to rewrite it :)
•  » » 8 years ago, # ^ |   +8 problem F is equivalent with which one of your problems?
•  » » » 8 years ago, # ^ |   +5 It hasn't been published, but it's called "Business As Usual".
•  » » » » 8 years ago, # ^ |   0 Thank you.
•  » » 8 years ago, # ^ |   0 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
•  » » » 8 years ago, # ^ |   +8 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)) :)
 » 8 years ago, # |   0 is there any chance of interview from with rank 465
 » 8 years ago, # |   -11 Hey! Look at this: http://codeforces.com/profile/worseHe/She is trying to be the worst in every contest! So He/She solve a problem, and hack solutions with easy testcases!
•  » » 8 years ago, # ^ |   0 Why do you know ?
•  » » » 8 years ago, # ^ |   +1 you can look at the standings, and turn to the last page.... you will see two funny coder....
•  » » 8 years ago, # ^ |   -6
 » 8 years ago, # |   0 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))?
•  » » 8 years ago, # ^ |   0 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 number K of 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 (by bi to its right, by bi - ai to its left) then. The cost of this first increases and then decreases as we increase K, because what we add levels with larger bi and remove levels with smaller bi - ai. Now, we iterate over all i from 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.
•  » » » 8 years ago, # ^ |   0 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).
 » 8 years ago, # |   +97 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 DEL
 » 8 years ago, # |   0 Have result ?
 » 8 years ago, # |   0 please update the ratings soon:)
•  » » 8 years ago, # ^ |   0 I hope that
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   0 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 NM from 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.
•  » » » 8 years ago, # ^ |   0 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.
•  » » » » 8 years ago, # ^ |   0 And I also started out at around 9:35 IST (around 35 minutes late).
•  » » » » » 8 years ago, # ^ |   0 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.
•  » » » » » » 8 years ago, # ^ |   0 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.
•  » » » » » » » 8 years ago, # ^ |   0 Yes, I understood that. I'm saying that you shouldn't have submitted anything.
•  » » » » » » » » 8 years ago, # ^ |   0 Will keep this suggestion in mind from next time. And now I am again Expert :(
•  » » » » 8 years ago, # ^ |   +15 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.
•  » » » » » 8 years ago, # ^ |   +8 This is a really nice idea. Thanks for this one :)
•  » » » » 8 years ago, # ^ |   +5 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.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 You may consider using Prim instead, it's easier to write edges backUPD: has been answered above. I didnt mean duplicate comment. sorry :(
 » 8 years ago, # |   0 fix it -_-
 » 8 years ago, # |   +8 How can I resubmit my solution ?!
•  » » 8 years ago, # ^ |   +1 The system don't let you resubmit the code submitted
 » 8 years ago, # |   +11 editorial and rating are wanted!!!
•  » » 8 years ago, # ^ |   -13 quickly ! quickly !
 » 8 years ago, # |   +10 Since I have made it to top 50, what does "name-encrusted weapon" means? Itching to get that :P
 » 8 years ago, # |   0 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!
•  » » 8 years ago, # ^ |   0 Try this test:3 20 1 10 2 21 4 4
•  » » » 8 years ago, # ^ |   0 i hacked this solution with the same input. well, not totally the same, but i guess our ideas are. :)
•  » » » 8 years ago, # ^ |   0 My answer for this testcase is : 3 but i get WA in test 37 |:
 » 8 years ago, # |   0 Mine failed on 36th :(
 » 8 years ago, # |   +26 waiting DmitriyH' statistics :)
 » 8 years ago, # |   +16 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
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 Is there any link to this OI problem?
•  » » 8 years ago, # ^ |   +16 i just noticed that the OIG logo is very similar to the CF logo :)
 » 8 years ago, # |   +1 Is there any way to see div2 only ranks?
 » 8 years ago, # |   +37
 » 8 years ago, # |   +8 My screencast: http://codeforces.com/blog/entry/12682
 » 8 years ago, # |   0 In problem A test 5, how the answer is 2? Why it is not 7?
•  » » 8 years ago, # ^ |   0 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 caramel
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 You 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).
•  » » » 8 years ago, # ^ |   0 Tnx. So I misunderstood about the meaning of 'in a row'.
 » 8 years ago, # |   +52 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 :)
•  » » 8 years ago, # ^ |   +5 Congratulations! I wish someday I become red too like you :)
 » 8 years ago, # |   +9 How amazing it is! viktork became 21th top-contributor because of only one blog. Most positive blog ever.
•  » » 8 years ago, # ^ |   0 +710! really amazing!