### Yandex's blog

By Yandex, history, 3 months ago, translation,

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

• +147

 » 4 weeks ago, # |   +43 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). Мы рекомендуем почитать все задачи, т.к. считаем их достаточно интересными и в некоторые добавили подзадачи для разнообразия.Удачи и побольше ОК.
 » 4 weeks ago, # |   +40 One who is planning to participate in Qualification round should start in next about 36 hours. Good luck and have fun.======Желающие поучаствовать в квалификационном раунде должны стартовать в ближайшие 36 часов (на самом деле около того). Удачи и приятно проведите время, решая задачки!
•  » » 4 weeks ago, # ^ |   +7 https://clist.by/ says that only 4 hours are left. That's a mistake, right?
•  » » » 4 weeks ago, # ^ |   +3 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.
•  » » » 3 weeks ago, # ^ |   +3 You are right, it's wrong. You should check correct time above. I've reported about the issue to aropan
 » 3 weeks ago, # |   +35 why are there so few T-shirts?)
•  » » 3 weeks ago, # ^ |   +5 Reason for thatWhere are my pants...
 » 3 weeks ago, # |   +45 Is it possible to upsolve the problems of qualification round ?
•  » » 3 weeks ago, # ^ |   +5 Chmel_Tolstiy said that it will be possible after ending of qualification round. But it is strange that now it isn't possible...
•  » » » 3 weeks ago, # ^ |   +24 Thank you all for participating! https://contest.yandex.ru/contest/29878/enter/ -- you can upsolve problems of Qualification.
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +8 how we can find upsolving(or another) contests without direct link?for instance I want to upsolve backend contest problems
•  » » » » » 3 weeks ago, # ^ |   0 please answer us Yandex, backed wants to upsolve problems too
•  » » » » 2 weeks ago, # ^ |   0 Is it hard to add Upsolve to qual contest of backend? Final is in 2 days
 » 3 weeks ago, # |   -8 Where can I find how to solve E
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   +13 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$
•  » » » 3 weeks ago, # ^ |   0 Thanks I understand
 » 3 weeks ago, # | ← Rev. 2 →   +4 Final round is on the same day as Kickstart round G, hoping that the timings don't clash.
 » 3 weeks ago, # |   +8 Hope we get an editorial for the problems this year :D
 » 3 weeks ago, # |   +8 Please, open upsolving for backend qualification
 » 3 weeks ago, # |   0 How to solve problem D Matrix?
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   +23 Observation: if we fold the matrix along the horizontal axis, all numbers in the same column became equal. For example for the matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 After folding 14 16 18 20 14 16 18 20 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)$
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +10 Thanks, I see what i did wrong.
•  » » » 3 weeks ago, # ^ |   +10 Sigh, I just realized I misread the limitation as $n, m <= 2^{30}$ and spent an hour for an $O(\log n)$ solution...
•  » » 3 weeks ago, # ^ |   +13 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.
 » 3 weeks ago, # |   0 How to solve problem F?
•  » » 3 weeks ago, # ^ |   +7 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. If one of the vertices $p,q$ coincides with $1,N$: If the other two also coincide, the path doesn't change. W.l.o.g. now $p=1$. If $q$ is on the path at distance $d$ from $1$, the length decreases by $d$ because the $q \rightarrow$ part of the path is changed to $1 \rightarrow$. If $q$ isn't on the path, the length can only change if the edge $1 \rightarrow$ isn't between $1$ and $q$ — the whole path is extended and its length increases by the distance between $1$ and chosen $q$. Otherwise, exactly one of the vertices $p,q$ (w.l.o.g. $p$) must be inside the path between $1,N$. If both are inside the path, its length doesn't change; if neither's inside, then all edges of the path don't change. Let's say that we moved from $p$ towards $1$, again w.l.o.g., for $d_1$ edges, left the path before reaching $1$ and moved further for $d_2$ edges. Then the length of the path increases by $d_2-d_1$. (Only if $d_2 \gt 0$ and $d_1 \gt 0$, the length doesn't change otherwise.) If we instead reached $1$ and moved further for $d_2$ edges, the same rule applies except $d_1$ is uniquely defined as the distance of $1$ and $p$. 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)$.
 » 3 weeks ago, # |   0 How to solve problem B?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 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 WWBBcan beBWBWif it's rotated, but both tiles can beBBWWwhich 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".
 » 2 weeks ago, # |   0 Isn't the next round schedule fixed yet?
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).
 » 2 weeks ago, # |   +3 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.
•  » » 13 days ago, # ^ |   +11 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
•  » » 13 days ago, # ^ |   +20 150-minutes contest will start at 9 a.m. UTC (12:00 Moscow time).
 » 11 days ago, # | ← Rev. 2 →   +21 Is there a public live scoreboard of the final round available somewhere?
•  » » 11 days ago, # ^ |   +2
 » 11 days ago, # | ← Rev. 2 →   +28 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?
•  » » 11 days ago, # ^ |   +18 I guess that's just a troll... There is a simple win strategy.
•  » » » 11 days ago, # ^ |   0 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.
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   0 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.
 » 11 days ago, # |   +36 Is it only me or was the problem statement hard to understand?
 » 11 days ago, # | ← Rev. 2 →   +16 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... 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.
•  » » 11 days ago, # ^ |   +5 Thank you for feedback. Sorry, for these issues. will double check it in next time frustrated to make the same mistake twice first time report of such an issue (will double check it) found an error fast and tried to fix it fast, forgot in hurry to send a message By the way hope it was quite good contest.
 » 11 days ago, # |   +8 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.
•  » » 11 days ago, # ^ |   +10 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.
•  » » » 11 days ago, # ^ |   0 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.
•  » » » » 11 days ago, # ^ |   +3 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.
 » 11 days ago, # |   +29 I think all the problems except B were really cool, kudos to authors!
•  » » 11 days ago, # ^ | ← Rev. 2 →   +33 [1,2]; [3,4]; ...; [2n-1,2n].I consider, so beautiful.
•  » » » 11 days ago, # ^ |   0 Alright, this problem is also nice :) I again forgot that generalized geography is a thing...
•  » » » 11 days ago, # ^ |   +11 Well now I feel like an idiot: I missed this, despite using it to solve https://codeforces.com/contest/1051/problem/B yesterday.
 » 11 days ago, # |   +8 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.
•  » » 11 days ago, # ^ |   0 In case of some issue with email contact we'll get in touch right here.
 » 11 days ago, # |   +18 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 implementationB — fine easy problemC — trivial with Berlekamp-MasseyD — niceE — bad convoluted statement; solution is easy if you know that sum over O(smaller child depth) is smallF — ok but why did you allow collinear and coincident points?
•  » » 11 days ago, # ^ |   0 Eh, D is pretty much classical "store prefix hashes and prefix reverse hashes", I wouldn't call that very nice.
•  » » » 11 days ago, # ^ |   +10 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.
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   +8 Yeah, we do. I don't see that as a particularly big step though. Maybe I got lucky by coming up with that quickly.
•  » » » » » 11 days ago, # ^ |   0 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.
•  » » » » » » 11 days ago, # ^ |   0 Min and max mismatched index define a single candidate prefix. That's because min and max must be matched with each other.
•  » » » » » » » 11 days ago, # ^ |   0 Ah, that's quite nice. I totally missed that.
•  » » » » » 11 days ago, # ^ |   +20 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
•  » » » 11 days ago, # ^ |   +16 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.
•  » » » » 11 days ago, # ^ |   +10 There's not much difference between hashing and randomized algorithms in general, so you're basically saying "I don't like all randomized algorithms"
•  » » » » » 11 days ago, # ^ |   +18 Pretty much. I don't get the same sense of satisfaction of having fully solved a problem.
•  » » 11 days ago, # ^ |   0 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 $g(s) = \text{length of longest unique subsequence of } s$and $f(k) = |\{s : g(s) \leq k\}|$If you have $f(0),f(1),...,f(|A|)$you can easily calculate the answer. Let us fix k. To calculate $f(k)$:For $j=1,2,3,...,k$ we define $g(j, len) = |\{s : |s|=len, s \text{ ends with exactly }j \text{ unique characters, }s \text{ doesn't have a subword of }k+1\text{ unique chars }\}|$One can write matrix M s.t. $M \cdot (g[1,len],...,g[k,len]) = (g[1,len+1],...,g[k,len+1])$Now $f(k) = \sum_{i, len} g(i, len)$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.
•  » » » 11 days ago, # ^ |   0 https://ideone.com/5EvGCw here you go
•  » » » 11 days ago, # ^ |   0 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)$.
•  » » » » 11 days ago, # ^ |   +10 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.
•  » » 10 days ago, # ^ |   0 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 for transitions in each node. It worked in ~1.8 seconds in C++, which seems too close to TL.
•  » » » 10 days ago, # ^ |   +2 You can store consecutive elements as decimal numbers since these elements are digits in base k. This way you will get rid of one L factor.implementation in case needed
•  » » » » 9 days ago, # ^ |   0 Ah, thank you! I didn't realize that these base-k sequences will fit in "long long" in base-10.
•  » » » » » 9 days ago, # ^ |   0 In "long long" in base-10? You don't use base-10 anywhere.
•  » » » » » » 9 days ago, # ^ |   +3 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? :)
 » 11 days ago, # |   0 How to solve task D in final round?
 » 11 days ago, # |   0 Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).
 » 11 days ago, # |   +3 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.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Check your spam and filters, I have mails with remainders as intended:
•  » » » 11 days ago, # ^ |   0 I double-checked. No letters. Also, I know that Egor did not receive these e-mails as well.
•  » » » » 11 days ago, # ^ |   +8 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 accountOf course it's my random guesses and only Yandex can answer properly
•  » » » 11 days ago, # ^ |   +20 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.
 » 9 days ago, # |   +24 Yandex when we can expect backend standings revealed?