Cheers everyone.

Today, on June 13 at 10:00 MSK the third and final qualification round of Yandex.Algorithm 2016 tournament will take place. I am the author of all tasks in this round. I wish to thank Ivan Gassa Kazmenko, Oleg snarknews Khristenko, and espically Aleksey Chmel_Tolstiy Tolstikov and Maxim Zlobober Akhmedov for their immense contribution to problems preparation. I also thank Yandex employees who were involved in testing this round.

Best of luck!

**UPD**: the round is complete! Congratulations to Um_nik, who was the only one to solve all problems!

You can find the elimination standings here. Congratulations to 25 best participants!

Editorial here

Auto comment: topic has been translated by Endagorion (original revision, translated revision, compare)How to solve Problem B — BMO and Garland?

Iterate for left turned on lamp. add

`2^(min(k - 1, len of suffix))`

to answerUPD: and also add 1 for case when there's no lamps at all

I've got WA 11 using this approach, and all the contest spent testing :(

2^(k-1)%m != ((2^k)%m)/2. It my WA 11. Very stupid bug :(

Formula: (

n-k+ 2) * 2^{k - 1}. But actually I have no idea how to prove it, just found it by bruteforcing.fix '1' in the left suffix : full segments : (n-k+1) * 2^(k-1) not full segments: sum from 0 to (k — 2) 2 ^i and just zeroes — it's 1 more, not full segments and just zeroes gave 2^(k-1).

Wow, that's pretty clear. Thank you so much.

UPD: Thank you all the guys below for explanation.

Well, I first thought it would be like (

n-k) * 2^{k}, that is, (n-k) positions to fix a window of sizekand 2^{k}possibilities for each window. However, this has over-counting.But, we can fix ones at the end of each window padded with zeroes on left and right of the window, and then place anything in between. Dunno how to put that in a formula though.

fix any segment and set leftmost and rightmost lamp. If set has length l, then count of possible variants is 2

^{l - 2}. For fixed l count of segments isn-l+ 1. And then answer is sum for l = 2 to k of 2^{l - 2}* (n-l+ 1). And need to addn+ 1 (for l = 0 and 1). Simplifiing formula gives us your formula.Say you fix the first K long segment at the beginning. Now you have 2^k possible ways. Every time you move your segment one along, you should not count all the combinations where the lamp that just left your segment was turned off, as they are also valid in the new segment, but already counted. That is 2^(k-1), so for the new segment that is one to the left we add (2^k)-(2^(k-1)) = 2^(k-1) to our answer. We do this n-k times, as this is how many times we can move the segment. So answer is, as you said, 2^k + (n-k)*2^(k-1) = (n-k+2)*2^(k-1)

EDIT: I guess I was the last of a million people to all post within 1 minute ;)

First add all possible for the first k lamps.

`res = 2^k`

Now say the right most turned on lamp is

`i > k`

. Iterate over all`n >= i > k`

.You will notice for each such

`i`

, answer is`2^(k-1)`

, since you have fixed`i`

-th lamp.Hence formula is:

`2^k + (n-k)2^(k-1)`

Iterate

lover range [0..k]. Consider all possilble segments of lengthlwith leftmost and rightmost bits set to 1. For every position, there are 2^{max{0, l - 2}}possible segments, making (n-l+ 1)·2^{max{0, l - 2}}possibilities for each possiblel(except whenlis 0 when there is only one possibility: a string consisting of all zeros).Most intuitive for me was the following:

Imagine all numbers from 1 to n. For n equals 5 it is going to be:

00000

00001

00010

00011

....

11111

If k =3, then there are exactly 2^k numbers with three digits, we count them in. There are 2^k numbers with exactly four digits, but we are intersted only in those which end '0', like:

01010

01100

01110

So there are 2^k / 2 = 2^(k-1)

Then we look at numbers with exactly five digits, there are 2^(k+1) of them. But we are interested only in those which end by 00, there are 2^(k+1) / 2^2 = 2^(k-1) of them.

And so on. So the final calculation will be 2^k + 2^(k-1) + 2 ^ (k-1) + 2 ^ (k-1) + ... + 2 ^ (k-1) repeated (n-k) times.

any idea how to fix WA3 in C?

I think the scenario in that case is that after losing to some vampire i, we will lose to a vampire j < i few times and build up the strength to beat i later.

Thanks

Спойлер+1, what can be wrong?

my codeEDIT: Yeah, I assumed that the defeated prefix never decreases.

On a different note, how do you post collapsing blocks in comments? I tried the two options available (block, inline) both does not collapse the code.

Try spoiler. I used below (but without dots).

<.spoiler summary="description">

.~~~~~

code is block, block is in spoiler

~~~~~

<./spoiler>

I thought the number of fights in one "run" never decreases when I had WA 3.

Very tricky. It is possible that you return to the original position with fewer points and still the answer is not -1.

3 4 0 5 0 8 0 0 9 0 7 answer: 8

Spent 13 wrong submissions on this (which effectively disqualified me), but finally got it right.

The point is that sometimes it pays of decrease the starting value of M, while my original algorithm terminated when such a situation occurs.

And on the 13th day the forces of code went to their forum and said unto each other: "Why can't we solve a baby problem? What's wrong with us?" And they answered: "Behold, thine logic has given way to thine vanity."

My solutions failed on such case: 3 2 0 7 0 8 0 0 10 0 100

Answer should be 8.

UPD: Its wrong sample, correct one in comments belowHow to fix this case? I had a greedy-ish algorithm to go to max point where we can and then increase value to such that it greater than what is needed there. For finding max point where we can reach I used suffix minimum BIT. I am not sure how to fix my idea to accommodate for this case as it would keep on running in prefixes. Can it not be fixed using my current idea?

Codeare you sure it's 8? I got AC now but my solution still thinks it's -1

Correct answer is -1. When we lose the third battle the strength become 0, and we can not win first battle.

Oh, sorry, my bad.

Correct one should be: 3 2 0 7 0 8 0 0 10 0 8

When will the final standings (three rounds combined) be released?

UPD: It's out!

Yandex rounds have really good quality. C, D and E were nice problems, thanks Endagorion.

Though, D was much easier than C and E.

How to solve Problem D?

Check what is in . Then, with binary search find on the right the first cell of different type. Then, the same on the left.

In binary search you should check

X+ 1,X+ 2,X+ 4,X+ 8, ... till you find the first different type. Then standard algorithm.X = 0 is just fine too

Let's find minimal k such that cells 0 and 2

^{k}have different colors (iteratek). I state that cells 0 and 2^{k}are in consecutive segments (ease to prove, try yourself). Using binary search find the leftmost cell in 2^{k}-s segment. Now repeat that starting from that cell instead of starting from 0. We have found starts of two consecutive segments. It is queries (and complexity).from Provision:

final round — July 28-29, 2016from Schedule:

28-29 Jun 2016Could someone clarify? Also, will there be someone from Yandex willing to help with visas?

It's JuLy, thanks for the note. We'll get in touch this week

A common reason for blind submissions: Submit near the end of the contest and no time to debug if the code is wrong.

How to solve C?

Does anybody know where I should write my address on yandex? I am in first 500 competitors, but I can't find field for address and they can't send me a t-shirt :D. Thanks

We'll get in touch everyone in TOP-512 this week.

This is not a TOP-512. This is the list of 512 people who can afford themselves to take part at least in two rounds.

Better than year ago :)

Even red still need to participate in competitions to win.

Some important information for non-Russian-speaking people:

"The Organiser shall not reimburse the Finalists’ costs of transfer from the place of residence of the Finalist to the final round" "Finalists can participate in the final round at the final round venue or online."

Are you planning to attend the onsite finals?

What about #513 who has the same penalty with #512 :) ? Can he receive T-shirt ?

he is cheater[2k])

Sure. We'll send the T-shirt.

Love the blind submissions. Encourage people to code more carefully and not to depend on the testing system to check their codes. And the reward for the brave people is very worthy — Much fewer penalties time!

Let's settle this once and for all. Amazing World of Gumball >> Adventure Time :))).

Have everyone received the notification mail about the T-shirt? My friends received it yesterday, but I haven't yet. So I am really worried that they lost my email...

I haven't received it yet either.

Please fill feedback form. You can find the link in the bottom left corner of the contest page.

Please give me advice on T-shirt.

I will be in Russia in August, so thinking to put Russian address in the form instead of Cayman Islands. Do you think it is realistic to receive T-Shirt to address in St. Petersburg by August 26th? Otherwise I'll stick with Cayman Islands address.

August 26'th is perfectly realistic date for St.Petersburg. Fill in Yandex office address and my name, if you want a personal office tour with your shirt =)

I've surprisingly found mine in a spam folder.

Mine too, but I provided @mail.ru address, so I can understand why :)

The same thing to me)

Where did you provide your email? I can't remember if I did that.

If you are not sure, please fill the feedback form on the contest page.

Well, I'm #513 who has the same penalty with #512. As you said before, I am able to receive a T-shirt.

However, I haven't receive any mails from Yandex, even when I filled the feedback form on the contest page. So could you consider my problem?

Thank you so much!

Of course you get the tshirt too! Sent you an email about now.

T-shirts are coming. A courier delivered it to me today. What is strange, I had to fill in my passport number in his papers, he said it's required when the package is insured.

Can you please elaborate on that on support@contest.yandex.ru

Can someone explain design of t-shirt ? xD

It's look like a curled armadillo.

Can you share a photo :p?

Is it OK if a contestant from my city (Izhevsk) has received a t-shirt 4 days ago, but I still haven't?