Hello, Codeforces!

*The problems were suggested by users roosephu and Sunayuki. The great help in preparing was provided by Aksenov239, GlebsHP and Codeforces team. ZeptoLab Team did its best while working on statements.*

*The round will use smoother dynamic problem scores with 250 points steps.*

In 2014 we hosted our first programming contest together with Codeforces, and we liked it!

Let me shortly remind you how it was. The contest consisted of 6 problems, 2.5 hours were given to solve (you can have a look at the problems of the previous year and try to solve them here).

Of course, even on a purely coding event we stayed true to ourselves, so all problems were designed based on our games, and, of course, we illustrated them with care:

Zepto Code Rush 2014 broke the existing Codeforces record of round popularity. Also we were glad to read a positive feedback about problems. By the way, the first three places were taken by developers from Russia. Some of them even came to pick up the prizes at the office, where they had a mini-tour and the highlight of the program: of course, the game in a giant Cut The Rope and our standard corporate "going green" welcome kit at the entrance (we call "going green" a welcome kit, full of fun gizmos of our corporate green color).

Somebody got even luckier: they stayed for more than just a tour and they still amaze us with their professional achievements. Here're some thoughts from one of them, Grisha WhiteCrow Nazarov:

I first came for the candies (just kidding), but if I share experiences now — what's especially important is that I can be myself here to the end. Zeptolabians are tolerant of my oddities and appreciate me as a person. In addition, Zeptolab leaders set goals, taking into account the abilities of each developer, including me. And when the head is also "into" algorithms, I can realease my potential. In the end I became a sort of client-side back-end developer, which, in fact, I wanted in the first place. Yes, I know some of the data structures that are unlikely to come in handy in Zeptolab soon (they would be more useful, for example, in developing a search engine); I almost never use this part of my knowledge in my daily routine. But these skills are useful to me on the internal algorithmic contests :) What I can say about Working moments: my last task was to improve packaging of atlases in preparing of game resources – a well-known NP-hard problem. I managed to make significant progress: to improve the famous algorithms, the best in 2013 in a variety of metrics. As a result, the memory consumption in all our game projects decreased by megabytes. With the appetite of our artists, I think it's not for long :) Maybe we'll publish my work in one of the next conferences. Overall, sports programming skills are highly valued here, and this, in my experience, is what isn't appreciated enough in other companies.

And this post is made to inform you, dear algorithm lovers, that: **Zepto Code Rush 2015 starts on Saturday, April, 4, 16:30 (UTC)**.

We are working on problems for the contest and ready, but we are ready to announce cool prizes!

You cannot get a vest like that in other ways besides taking part in the contest. The vests are great!

And as usual, the person who shows good results in the competition, will be able to get a job in our company by a simplified scheme. You can read about ZeptoLab on our official website.

ZeptoLab Code Rush 2015 will use standard Codeforces rules, it will be a rated round for the both divisions.

This contest will be rated ?? or get any editorial ??

it will be a rated round for the both divisions.

Div.1 vs Div.2

The vests are great! :))

Nice Jacket. I liked It :)

Rare! This is one of a few clothes you can win from a programming contest, and you can actually wear it in some not-programmatical place.

No T-shirts =(

I agree, it's not that funny when there aren't T-shirts :( .Anyway, I hope the problems will be as interesting as last year or even better :)

There are 15 vests and 50 plush toys to win and you are complaining that there are no T-shirts (100th opportunity to get programming T-shirts?) -_-... Codeforces community can be so cruel sometimes ; d

Oh, c'mon, wasn't it a sarcasm?

It doesn't look like one, especially geniucos' comment.

I would kill to get that cute toy and vest!

Kill me, you'd do a big favor to codeforces

Maybe your first comment that get up votes... :|

Man I am depressed

I love ZeptoLab. The code rush will be good!

i really wonder if viktork is fake account or a specialist host the zeptolab code rush!

Well green matches well with the vests..

tourist would you leave the IPHONE 6 this time ?

No chance,tourist would participate and would win again.

Still waiting for last year's Tshirt..

I think You are Going to Get Two T-Shirt Simultaneously :) Best Of luck For All

your company's games are full of fun,and they are popular in my country!

How can we register guys?

The registration system is same as you register in codeforces round.....

I think After this contest Color me pink (magenta) will be

OMG

What a nice grammar..(plz don't edit your comment... ;D )

No this is not my grammar,this is google translate grammar

Try to learn english in appropriate way! google translate isn't such good tool :|

If you want to highlight both the upvote(green) and downvote(red) arrows simultaneously you should first click on the upvote arrow and then "very quickly" after clicking on the upvote arrow , click on the downvote arrow .

Other way around (firstly downvote and then upvote) works as well ;)

It worked. ;)

As long as you don't reload the page.( I'm disappointed ).

Hopefully there would not be many unknown giant-non-rated(div1 coder competing in div2) coders here!!!

Huh this is combined division contest. This only happens in div2 only contests. So no need to worry.

I thought that more than 6000 participant will join to the contest

But now it's only 3500...

Maybe it will be(I hope)

Now it's 5000.

UPD :5500iPhone 6 is gone. tourist is participating. :)

you say that like tourist is the only one standing between you and iPhone 6 :)

-_- Very nice joke Mr. sepehr103. April fool is over though.

maybe ironman7453 is fake Petr's account

Hi cheater !

How are you? 9108491 && 9117330

Hi Majid :)

come on sorry_dreamoon !

iPhone 6 is waiting for you !

Edit: TY CF community, I know you wouldn't let me down :)

:|

why?

Still waiting starting the raund :))

Maybe "round"?

Good luck and have fun!

You too :)

tourist vs Petr ... I'm waiting :)

Are you waitimg?..

I moved the round 5 minutes forward just to be sure that everybody are ready and registered. May

~~the Force~~Om Nom be with you!How did you manage to strike out letters ? Just curious, :)

just use

`<s>test</s>`

.Its

~~great~~amazingWelcome kit of Zepto Lab is "going green", but for codeforces, it is "going RED"!!

Wow, the prizes are awesome, and I'm sure the problems will be just as good. It's a shame that with >5000 participants a few people (including me) don't stand a chance at getting one of those cool vests. How about giving away a few vests or buttons to random participants besides the top 50, or better yet, a vest for someone random in the top 500, in the top 1000 (places 0-1000), and so on? That way the more skill you have the better the chances for getting a prize, but everyone still has a chance. But then again, prize or no prize, I'm sure we'll have a great time solving the problems :).

It's starting in 5 seconds...

Nice Contest thanks all :)

It Ended in before 10 minute

Can anyone give a hint about E?

It is similar to WF2014 Problem K. I used the same method I used to solve that problem, but it may TLE on system test.

Use greedy + dfs + binary search to solve it.

What is your complexity?

The

O(N*log*Q) is quite obvious with the same method from WF2014 — K, but I think it'll TLE, so I didn't attempt..I think it will TLE too. I did some pruning so I can past the pretest. Let's hope it will not TLE on system test. :D

UPD: It passed system test! [smiling face]

Nice — mine linear per query TLEed :(

My also TLEd (rather understandably).

thanks :D

To solve this problem, first, you need to compute, for each level, how many levels starting from this one would fit in one group. Then, use dynamic programming to compute for each level, starting from the last one, two numbers:

Now, the answer is the smallest number of groups among levels where the groups include all levels, i.e. minimum of the first number among those

ifor which the second number is at leasti.Thanks guys

I tried that but I get TLE :(, I did many optimization but still no success :(

What's the time complexity of your solution? My solution has time complexity

O(nq).N*Q*log

Another solution with the same complexity:

If the answer for a query is equal to R, then if you start with the first element and do greedy, your answer will be at most R+1. So lets try to start with the first element and get some answer R', and after that check if R'-1 is also possible.

To check that, you can build an oriented tree with edges (P[i], i), where P[i] is largest position such that group [i, P[i]-1] fits. Now you have to find a path in this tree of some fixed length such that the difference between indices of the first and the last vertices of the path is at least N. Since the number of paths in O(N), you can easily check that using dfs.

why is it always at most R+1?

Because you can divide the group and the answer will increase by one.

Mine

O(N·Q) approach calculates for every starting position how many groups are needed and what is the sum of leftover elements at the end, which can be eventually grouped with the elements in the beginning.How do you do it in O(N.Q)??

inb4 90% of submissions on C fail and the problem gets 2500 points, sending people who solved it waaay up the scoreboard :D

(just so it's clear: I know that mine should fail — I have at least a typo)

Does problem C have a tricky corner case?

Is C a DP? I tried but couldn't think hoe to minimize size of array.

How do you solve C? I failed pretty hard on that one :/ Was thinking of some binary search type algo to get logarithmic complexity but didn't work out... Any hints?

Splitting it into 2 cases: and . The first case is trivial, you can try all possible numbers of candies of type A eaten and compute the max. number of candies of type B. For the second case, I tried all possibilities for the sum of weights of eaten candies that are worth trying (at least

C-Wa); when it's fixed, the optimal solution is taking the max. possible number of candies of one type, which means solving a modular equation. Seems that it's unnecessarily complex, I saw simpler solutions when trying to hack.thnx

I just did bruteforce, and it passes. Let's assume that

w1 ≥w2. Kill the casesw2 = 1 andw1 =w2 with "if"s. Thenw1 ≥ 3 and now iterate over all possibilex1 — number of type 1 candies.I have a feeling you dodged a bullet there! I tested your code against this 1000000000 4 3 4 3 and it just scrapes through the 1 second time limit :P

Result = 1000000000

=====

Used: 982 ms, 4 KB

I had used "custom invocation" option and had checked that it passes such tests, before I submited.

Woah I didn't know you can do that during the contest as well! Thanks! I usually code a solution and pray that it works :P

Here is the theory for a polynomial algorithm: http://www.ics.uci.edu/~dan/pubs/p147-hirschberg.pdf

It is possible, but very complex: http://www.csie.nuk.edu.tw/~cychen/Lattices/A%20Polynomial%20Algorithm%20for%20the%20Two-Variable%20Integer%20Programming%20Problem.pdf Code: http://pastebin.com/zSZ5vVWM

Good Bye Div. 1 till 2 months later :-h

Is D a DP? How can I solve it?

I've solved using Z-Function.

It's funny, because the great post about it by paladin8 — http://codeforces.com/blog/entry/3107 is currently on top 5 of recent actions :)

It's extremely simple with KMP too: 10582275

Can you explain your solution, please?

Let's ignore K for a moment and focus on choosing A, B. We have that the whole string S must be periodic with period len(A + B). Therefore len(A + B) is a multiple of the smallest possible period P for the whole string.

Suppose len(S) = mP + q, with 0 <= q < P. The last q characters have to be in A (as len(A+B) is a multiple of P). Therefore, the necessary condition to write S as A + B + A + B + ... + A is that len(A) = xP + q, len(B) = yP — q, and x+y divides m.

Knowing all of this, which A, B to choose to get k repetitions? Suppose you choose A to have length

L. After you remove the last A, you have to leave something which is (A+B) repeated K times. Therefore, you have that:From the first condition, we want L = len(S) mod k, and from the second condition, we want L as small as possible. So try L = len(S) mod K and check if it's valid, otherwise print 0.

KMP indeed! How did you use the

`pos`

array?Can you explain the idea behind your code, please?

what was the main idea?

Check all possible lengths

Lof blockA+B. For eachLuse Z-function to find numbertof equal blocksA+B(by checkingz[L],z[2L],z[4L],z[8L]...). ift≥k, then fillmin(z[L*k],L) indices with 1 (at positionL*k). ComplexityO(nlog(n))Actually you can do it in O(N). In fact you only need to check if z[L]>=L*(K-1)

Thanks!

Some hints for problem C ,please!!

This is my solution

Divide case into 2

Wr > 1000000 : check all posible case

Wr <= 1000000 : In this case, number of blue candy is smaller than Wr so check all

I'm not sure this is right

Now I'm sure this is right

Why the number of blue candy is smaller than Wr?

So if number of blue candy is bigger than Wr, it can't be a best case.

`(blue candy)*(Wr)`

can be replaced by`(red candy)*(Wb)`

, which has more enjoy unit.Thanks

Can i filter standings table by color?

Is the problem F only this? http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation I just didn't want to copy-paste the code, which is probably not even allowed...

I think code from SO is allowed: http://codeforces.com/blog/entry/8790

That's really interesting! I didn't know it, at least I will know for the next time!

ignore

Is D some kind of KMP? I was trying to figure out something from the mismatch array but failed.

D can be done using Z

How do you track the intermediate Bs? or may be thats not even required?

I've used Z-algorithm...

http://codeforces.com/blog/entry/3107 Epic!

A friend of mine used Z-algorithm. I'm not too familiar with that, so I used rolling hashes for string matching. As long as you have constant-time string matching, it can be solved in O(n lg n): for each value of m = 1...n/k, check if the first km characters is just k copies of the first m characters. If so, also check to see the longest prefix 1...i which matches km+1...km+i (using binary search). Then all strings from km...km+i will be regular (and with some minor details this gives you the output).

How to solve C ? Integer Programming seems too complex.

I will describe my algorithm but I don't know if it is correct since I haven't got the chance to submit its final version because CF was not available in the last seconds :@ :@ :@

We know that X * Wr + Y * Wb <= C.

If we have fixed Y, then X <= (C — Y*Wb) / Wr. As we want to have maximum X, let's say that X = (C — Y * Wb) / Wr.

Happines = X * Hr + Y * Hb. After replacing X, we get:

((C — Y * Wb) / Wr) * Hr + Y * Hb.

Now, using binary search we can find when F(Y) starts to be less than F(Y-1), where F(Y) = ((C — Y * Wb) / Wr) * Hr + Y * Hb.

I tried binary search and it failed.

I tried too but it was implemented wrong and when I found the bug, the contest was over because CF was unavailable.

Binary search will obviously fail because the function is not monotonic and even has several extremas. That's why ternary search is also not very good.

My bad :)

what's the best time complexity of problem c? I have solved similar problem on http://codeforces.com/contest/519/problem/C but here it's 10^9, and I always tle..... Could anybody give me some hint?

How about problem D?

Thanks : )

Refer to my solution 10585701

Time complexity is O(sqrt(N)), as described in http://codeforces.com/blog/entry/17281.

It was duficult.

I couldn't hack from Firefox (Chrome worked fine).

Hi, could you prove that your solution on C works correct for all cases?

If Wr is big, the number of red candies must be small. If Wb is big, the number of blue candies must be small. If both Wr and Wb are small, there are two cases: use less than Wb red candies or use less than Wr blue candies.

To hack from firefox you would have to delete the browser's cookies

Thank you, I can hack now.

Problem C have been used in a regional contest in China.

http://acm.hdu.edu.cn/showproblem.php?pid=4091

Problem E: http://main.edu.pl/en/archive/oi/21/doo

:(

So whats the dreaded test case 3 in problem C

Here are two tricky test cases I used for hacks:

999999999 10 499999995 2 99999999

999999999 10000 494999 2 99

Now that it's over:

982068341 55 57 106 109

How to solve Problem B? I found out the path having maximum number of lights, but had problem in incrementing values of edges and distributing the increment among edges in a path. Maybe I complicated it too much.

Finally Division 1! :D

Good job, hacker! (I have only 1 hacked solution because you were faster :D)

Hahahaha thanks :P

Became orange after 1.5 years not doing programming competitions xD

Btw, I solved C using some hacky brute-force constantly checking time limit until 0.9 second passes. How bad am I for doing is that?

Very smart.

Actually, it's easier to gain a lot of rating in a combined division round than a div1 only round for some reason.

My wild guess: In div1 only round some fraction of participants prefer to skip the round, should they observe problem A is too hard. So you can't "steal" your rating points from them. Combined round has easy entrance problems, so much more skippers got trapped :) More people lose rating — more chances you get some

I solved problem a like so many other people did,a very bad solution that works because n<=100 here's my solution anyone knows why it's wrong? 10579934

10593643

God damn me , what an awful mistake ;-(

Could anybody tell me why this solution of E is correct? It looks like magic. 10581607

Because it's wrong:

https://ideone.com/OKfcQJ (tourist)

https://ideone.com/ugCOlH (this one)

Test case:

Thank you!

Heh. I also submitted such solution (10589617), and wondered whether it works in the general case. Thank you for the test!

Please, take a look at this submission.

We can see that an array check with 100 elements(indexed from 0 to 99) is declared.

I tried to hack it with the following test:

`100 *****...******`

Here "..." means a lot of '*'s, not dots.

Let's take a look at the following for loop:

Here, the variable

ican be up to s.size()-1 which is 100 — 1 = 99. Then check[i+1] will be check[100] but it is indexed from 0 to 99. Then shouldn't this be a runtime-error because it cost me -50 instead of +100 :@PS: Something similar happened during Codeforces #297. I tried to hack this code. As we can see, the guy is pushing some things in a vector ot. And what if ot is of odd size:

I think that if ot.size() is odd, then i+1 will be equal to ot.size() at some point which should be a runtime-error anyway but it wasn't...

It doesn't give runtime-error. It causes undefined behaviour and sometimes works correctly.

Ok, thanks! I thought that it should be RTE because usually on my computer it causes Segmentation fault and when I submit such code on lightoj it causes RTE :)

Can someone please explain the solution for problem E? I didn't understand it from the Editorial.

i wish i could won the jacket :(( its so nice :)

I really like the way in which testcases for E were generated.

All large tests are

we'll give you 50 queires, but most of them will be same. Are you serious, guys? :) Looks like most ofO(N*log(N) *Q) solutions can pass after adding memoization. My messy implementation (10587744) wasn't even able to pass pretest 10 during contest, and after adding memoization it runs in 1.6 seconds (10600918).Omagad, what a shame. It is reasonable to create a maxtest with worst case repeated, but in ALL of them -_-...

What is more, there are some wrong submissions which passed (as pointed out above).

What's more, just 21 tests.

When I create tests, I usually also do something like "10 completely random tests" and variations of it several times. More tests won't kill anyone, especially on problems that won't have too many submissions. But this...

Is there any tutorial for this contest?

It looks like ZeptoLab has bad luck with repeating problems. As pointed above, C, E and F were already present in some places of the Internet and one year ago E was from Junior Polish Olympiad in Informatics (I watched editorial created by johnasselta during the contest :P) and F was used in Petr Mitrichev contest.

sorry, I misread

I'm not sure I understood. Didn't Petr clearly state that this problem was present on his contest?

Sorry, I missed "one year ago" in your post

Will this contest an editorial?I haven't see it.

Yes