Hi all,

We are pleased to announce that Yandex is once again including Yandex.Algorithm as part of the programming championship. The Algorithm track is a great opportunity to solve interesting problems, compete with participants from around the globe, and win cash prizes. This year's championship will be held completely online.

Schedule:

The trial stage starts on September 20 at 12:00 and ends on September 26 at 23:59

The qualifying round starts on September 27 at 12:00 and ends on October 3 at 23:59. It will be organized as a virtual contest.

The final round will be held on October 16. The time will be announced later. The final round will include participants who earned at least five points in the qualifying round.

The Algorithm tasks are available in English and Russian.

Prizes:

1st place: 300,000 rubles

2nd place: 250,000 rubles

3rd place: 200,000 rubles

4th place: 150,000 rubles

5th place: 100,000 rubles

There will be T-shirts for top-30 in each categories.

Registration is open until the end of the qualifying round. To learn more and register, go to the site: https://yandex.com/cup/algorithm/

I would like to thank the Algorithm team and personally the teamlead of category Chmel_Tolstiy

UPD: Qualification round is running now. It's two hours virtual contest and contestant should start the participation (you need a registration) till 23:59 3rd October (Moscow time, UTC+3).

UPD2: Qualification round is over. Thank you all for participating! Upsolving: https://contest.yandex.ru/contest/29878/enter/

UPD3: Qualification Round Editorial: https://codeforces.com/blog/entry/95880

UPD4: Algorithm 2021 is over! Congrats to winners ksun48, Radewoosh and Um_nik

Special thanks to tourist for great performance and first place out of competition.

Everyone can register to look at problems or to upsolve: https://contest.yandex.ru/contest/30228/enter/

Qualification round is running now. It's two hours virtual contest and contestant should start the participation till 23:59 3rd October (Moscow time, UTC+3).

Please read all problems we think that each quite interesting and some of them has subtasks.

Good luck and get some OK's.

======

Квалификационный раунд начался. В формате двухчасового виртуального соревнования участнику нужно стартовать свою сессию до 23:59 3 октября (время московское, UTC+3).

Мы рекомендуем почитать все задачи, т.к. считаем их достаточно интересными и в некоторые добавили подзадачи для разнообразия.

Удачи и побольше ОК.

One who is planning to participate in Qualification round should start in next about 36 hours. Good luck and have fun.

======

Желающие поучаствовать в квалификационном раунде должны стартовать в ближайшие 36 часов (на самом деле около того). Удачи и приятно проведите время, решая задачки!

https://clist.by/ says that only 4 hours are left. That's a mistake, right?

Yes, that is a mistake. According to rules for algorithm, registration closes 3th October, 11PM UTC+3, and one can start solving tasks before 3th October, 11:59 PM UTC+3, no matter when one started, they always will have 2 hours to complete the tasks.

You are right, it's wrong. You should check correct time above. I've reported about the issue to aropan

why are there so few T-shirts?)

Reason for thatWhere are my pants...

Is it possible to upsolve the problems of qualification round ?

Chmel_Tolstiy said that it will be possible after ending of qualification round. But it is strange that now it isn't possible...

Thank you all for participating!

https://contest.yandex.ru/contest/29878/enter/ -- you can upsolve problems of Qualification.

how we can find upsolving(or another) contests without direct link?

for instance I want to upsolve backend contest problems

please answer us Yandex, backed wants to upsolve problems too

Is it hard to add Upsolve to qual contest of backend? Final is in 2 days

Where can I find how to solve E

Define $$$cnt_i$$$ — size of suffix consisting of only bits $$$1$$$

One condition in good matrix is $$$cnt_i \ge cnt_ {i-1}$$$ and other bits in row $$$i$$$ consist of bits $$$0$$$, for $$$2 \le i \le n$$$

Write DP $$$dp_{i,j,k}$$$ — minimum number of swaps if we make suffix $$$i$$$ of rows and suffix $$$j$$$ of columns in row $$$i$$$ consist of $$$1$$$ using $$$k$$$ bits from some positions.

So transiions:

$$$dp[i][j][k]-(!a[i][j]) \Rightarrow dp[i][j + 1][k - 1]$$$

$$$dp[i][j][k]+(m - j + 1) - sf[i-1][j] \Rightarrow dp[i - 1][j][k + (m - j + 1)]$$$, where $$$sf_{i, j}$$$ is number of bits $$$1$$$ in row $$$i$$$ on suffix $$$j$$$

Answer is $$$\min(dp_{i, j, sum})$$$ for all positions $$$(i; j)$$$ and sum bits of matrix $$$sum$$$

Thanks I understand

Final round is on the same day as

Kickstart round G, hoping that the timings don't clash.Hope we get an editorial for the problems this year :D

Please, open upsolving for backend qualification

How to solve problem D Matrix?

Observation: if we fold the matrix along the horizontal axis, all numbers

in the samecolumn became equal. For example for the matrix:After folding

And if we fold along the horizontal axis again (just assuming, this is forbidden in the problem statement for this example), every numbers will be doubled.

And the same observation hold for the vertical axis. Also if there is a moment that we have already done 2 type of folds, all numbers will be the same.

The second observation is that we must fold along the bigger side. Suppose that side is $$$m$$$. Then we will have: $$$n \le m$$$, so $$$n \le \sqrt{n \times m} \le \sqrt {2^{30}} = 2^{15}$$$, which is small enough. That means after the first time folding, we actually can just maintain the set of the numbers in every columns. That is, we calculate them, put them into a set. While $$$m > n$$$, we double these numbers again and again, put them into the set. And finally we can fold along the other axis and all number will become one. Now is just looping until $$$n = m = 1$$$ and double this number again and again.

This algorithm works in $$$O(\min(n, m) \log n \log m)$$$

Thanks, I see what i did wrong.

Sigh, I just realized I misread the limitation as $$$n, m <= 2^{30}$$$ and spent an hour for an $$$O(\log n)$$$ solution...

Problem have $$$O(log(n)+log(m))$$$ solution.

We have some numbers after each fold. We need add count of this numbers to the answer and subtract count of numbers that have already been added since the previous fold. It can be proved that it is necessary to subtract only numbers $$$\le n\cdot m$$$ (numbers that intersect with the original sequence). It can be done in $$$O(1)$$$ with simple math formulas.

How to solve problem F?

Let's formalise reversing a path as changing each edge $$$p \rightarrow v$$$ to $$$q \rightarrow v$$$ and vice versa iff $$$v$$$ isn't on the path. Now it's simple casework with some efficient tree stuff.

We can bruteforce all cases for one of $$$p,q$$$ coinciding with $$$1,N$$$. Now let's pick the vertex $$$v$$$ (possibly $$$1$$$ or $$$N$$$) where we left the path after moving from $$$p$$$ to $$$q$$$; we know $$$d_1$$$ and just need the sum of distances to all vertices in its (non-path) subtrees, with some multiplier since we have equivalent cases depending on which vertex is on the path and to which one we're moving. $$$O(N)$$$.

How to solve problem B?

For mine, each tile can be rotated so for each tile I see the lexicographically minimum representation of it (there might be a better way). Like

WW

BB

can be

BW

BW

if it's rotated, but both tiles can be

BB

WW

which is the lexicographically minimum of them (going clockwise starting at upper left) so I use that to represent the first 2 tiles. I mapped the first 2 tiles to the third tile, and the third tile is mapped to the number of tiles that can be rotated to it.

Then, for each tile in the picture, I get how many tiles left I have that can be rotated to this tile, and if I run out of tiles that can be put there it's "No".

Isn't the next round schedule fixed yet?

Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).Will the final be in the same virtual format ? E.g. we will have x hour window to do the contest any time between some fixed start and end date. Since https://clist.by shows that the final round will be 27 hours.

the official contest side says it will be 2:30 starts at 2:00am (-7 utc). Anyway, can't believe they haven't announced yet the schedule even before 48 hours ago. https://contest.yandex.ru/yacup/contest/29447/enter?lang=en

150-minutes contest will start at 9 a.m. UTC (12:00 Moscow time).

Is there a public live scoreboard of the final round available somewhere?

https://contest.yandex.ru/yacup/contest/29447/standings

I admit I'm not too good at interactives but what is the point for the 90% winrate for problem B if tests are deterministic? Is it just a joke or does it actually matter for you to rng and hope the grader's heuristic is bad?

I guess that's just a troll... There is a simple win strategy.

What is the winning strategy? I solved the problem but I used a heuristic (go first iff N is odd, and always pick the number that has common factors with the most other numbers), but I see no reason that should be optimal.

If $$$n$$$ is odd, then go first, pick number $$$n$$$ in the beginning, and in the following round, if the jury picks one of $$${2i-1,2i}$$$ for some $$$i$$$, player just picks another one. Similar strategy can be applied for the case where $$$n$$$ is even.

Is it only me or was the problem statement hard to understand?

I don't want to excuse for my performance, but let me leave some complaints to make the contest better.

The rule page has been unavailable at least round the contest time. https://yandex.com/cup/rules/ redirects somewhere. Replacing

`.com`

with`.ru`

shows me something...Again: https://codeforces.com/blog/entry/81365?#comment-719214

The judge order was totally broken: https://gyazo.com/6d7af2cf350fc9640b28ed367d809f9d (I submitted the essentially the same codes to confirm it). This ruins a full-feedback contest.

When I first submitted a partial solution for D it got 0 points because of the sample. I needed to modify it, but the score was silently fixed then.

Thank you for feedback. Sorry, for these issues.

By the way hope it was quite good contest.

B makes me uneasy. You need to have a 90% winrate against what? Some jury solution that's not even guaranteed to be the best?

If the game has no known winning strategy that can be calculated fast enough, then this is just a tossup — you need to make several attempts because your strategy's winrate will depend on the jury's winrate.

If the game has a known winning strategy that can be calculated fast enough, then this formulation is just dumb and confusing. If it's supposed to be a joke, it's just annoying and not very amusing. Though, the problem statement doesn't guarantee that n is chosen uniformly at random, so you can make a test where all games have the same $$$n$$$ for every $$$n$$$, so I guess I was supposed to understand that it is a "troll"?

And then I find out that the first greedy strategy I write is actually correct.

What's "best"? If the grader plays the winning side, of course it can beat you, and if the grader plays the losing side, all moves are losing unless you mess up.

I mean optimal. From the problem statement alone it's not clear that the grader always makes correct choices (it is even called a heuristic and the statement about 90% makes it sound like it might not be).

A priori, you can't deduce from the statement alone that whether a state is winning or losing is decidable in polynomial time. So it could be possible that you are expected to exploit weaknesses in the jury's algorithm.

But then they wouldn't be able to set the problem if they couldn't decide who was winning in case contestant had a better solution.

Anyway, from contestant's point of view it doesn't matter too much, just try to solve the problem.

I think all the problems except B were really cool, kudos to authors!

[1,2]; [3,4]; ...; [2n-1,2n].

I consider, so beautiful.

Alright, this problem is also nice :) I again forgot that generalized geography is a thing...

Well now I feel like an idiot: I missed this, despite using it to solve https://codeforces.com/contest/1051/problem/B

yesterday.How will we be contacted according the prizes? My main email in yandex system is something@yandex.com, but I'm not using it at all, I guess that other non-Russian participants too.

In case of some issue with email contact we'll get in touch right here.

The problems felt too easy for the finals. I only like problem D because I couldn't solve it.

A — it's trivial what to do; scary implementation

B — fine easy problem

C — trivial with Berlekamp-Massey

D — nice

E — bad convoluted statement; solution is easy if you know that sum over O(smaller child depth) is small

F — ok but why did you allow collinear and coincident points?

Eh, D is pretty much classical "store prefix hashes and prefix reverse hashes", I wouldn't call that very nice.

Don't we need to store the set of mismatched positions in order to find a single candidate for what prefix to reverse? I didn't come up with that during the contest and I don't think it's that standard.

Yeah, we do. I don't see that as a particularly big step though. Maybe I got lucky by coming up with that quickly.

I still don't see how to find a single candidate prefix to reverse. I did see that you should store mismatched positions to give a lower bound on the length of the prefix, but that still leaves O(n) candidates.

Min and max mismatched index define a single candidate prefix. That's because min and max must be matched with each other.

Ah, that's quite nice. I totally missed that.

That's definitely the key observation. In our Polish group only Radewoosh came up with that observation. Call me stupid, but it took me a few minutes to even understand why this is true, yet alone come up with it during the contests :P

I have to say I dislike string problems that can only be solved by hashing: the solution isn't correct for all possible inputs, and you're just relying on the fact that judging is done with fixed examples that are unlikely to break your particular hash function.

There's not much difference between hashing and randomized algorithms in general, so you're basically saying "I don't like all randomized algorithms"

Pretty much. I don't get the same sense of satisfaction of having fully solved a problem.

Ad C. Can you elaborate on that? IIRC Berlekamp-Massey guesses the linear reccurrence from given n points. I am convinced that for a given $$$A$$$ there will be a linear rec. But how to feed it with initial values?

My solution was like this:

Let

and

If you have

you can easily calculate the answer. Let us fix k. To calculate $f(k)$:

For $$$j=1,2,3,...,k$$$ we define

One can write matrix M s.t.

Now

and this can be easily calculated with matrix exp, if you extend the matrix and the vector to maintain also the sum of everything.

Also, this got WA, but I am pretty sure that I have a bug in implementation. So if anyone could provide a correct result for 500000000 50, or share a solution, so I can find an input to debug, I would appriciate that.

https://ideone.com/5EvGCw here you go

I don't understand your question. Finding a matrix is only more advanced than solving the problem with dp for small values.

For me,

`dp[i][j][k]`

was the number of strings of length $$$i$$$ with max $$$j$$$ unique characters in a row, and a suffix of $$$k$$$ unique characters. Compute it for $$$i \leq A^2$$$ in $$$O(A^4)$$$ or $$$O(A^5)$$$.Ok. Got it, so you calculated the first elements of the sequence using the DP (for me that is the non-trivial part). And then used BM to find the simplest lin. rec. the first A^2 elems are satisfying. Having the lin. rec. allows you to find Lth element of the sequence for big Ls easily.

Can you please share your idea on problem A?

I was able to solve it with (I think) $$$O(L^2 \cdot n \cdot log(k))$$$ where $$$L \leq 20$$$. Using a trie with a

`map<int,int>`

for transitions in each node. It worked in ~1.8 seconds in C++, which seems too close to TL.You can store consecutive elements as decimal numbers since these elements are digits in base

k. This way you will get rid of oneLfactor.implementation in case needed

Ah, thank you! I didn't realize that these base-k sequences will fit in "long long" in base-10.

In "long long" in base-10? You don't use base-10 anywhere.

You're right, it doesn't really make sense to use base-10 in this context. But then again, there are 10 types of people in this world, right? :)

How to solve task D in final round?

Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).I missed the finals because there was no e-mail from Yandex Cup about me qualifying to the finals and/or reminder e-mail before the contest. Actually, the last e-mail I see from the organizers is dated August 7.

Of course, it's my fault that I don't visit clist.by on a daily basis :)

But still, it's quite normal to expect that that finalists have other things to remember other that the date of the finals, and make some effort on notifying us.

Dislike to Yandex Cup for that.

Check your spam and filters, I have mails with remainders as intended:

I double-checked. No letters. Also, I know that Egor did not receive these e-mails as well.

Have you checked correct inbox? Or maybe redirects are broken?

I noticed strange thing, that mails on screenshot above are sent to @mail.ru, though I of course take part with my @yandex.ru account

Of course it's my random guesses and only Yandex can answer properly

I only received 1 reminder yesterday, and interestingly it is different from the one on your screenshot: it has "уже завтра" in the title, and starts with a slightly different text. Seems like they have different mailing lists and send different emails to these lists.

Yandex when we can expect backend standings revealed?