### Yandex's blog

By Yandex, history, 4 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 trial stage starts on September 21 at 12:00 and ends on October 18 at 23:59

• The qualifying round starts on October 19 at 12:00 and ends on October 25 at 23:59. It will be organized as a virtual contest. Participants will get six tasks, with 120 minutes total to solve them

• The final round will be held on November 7. 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: 150,000 rubles

• 3rd place: 100,000 rubles

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

UPD:

Algorithm 2020 final is over! Thank you all for participating!

More information is available at the Chmel_Tolstiy comment

See you at the next competitions!

• +254

 » 4 months ago, # |   +32 what about t-shirts?
•  » » 4 months ago, # ^ |   0 There won't be t-shirts this year. I know your sadness
 » 6 weeks ago, # |   0 If I start qualification round virtual contest now, will I write it for 2 hours or till 26 october for 7 days?
 » 6 weeks ago, # |   +48 Bump, 1 day of qualifying round is left.I found in rules that 5 points are enough to qualify but will I see the number of points assigned to each problem? The rules just say that there might be groups of tests, each worth 1-5 points.
•  » » 5 weeks ago, # ^ |   +34 Yes, the number of points is stated in the problem statement.
 » 6 weeks ago, # |   +36 What happens if in a certain track less than 3 people get score required to advance to the finals? Will the 3rd place prize be divided among the ones who advance? Or do organizers have an option of lowering the cutoff?
•  » » 5 weeks ago, # ^ |   0 The organizer reserves the right to lower the qualifying threshold if the number of participants who have scored 5 or more points in the qualifying round is less than 500.
 » 5 weeks ago, # |   0 Are we allowed to discuss the problems from the qualification round here now?
•  » » 5 weeks ago, # ^ |   0 And is there any kind of editorial?
•  » » 5 weeks ago, # ^ |   0 there are ~14 more hours
•  » » » 5 weeks ago, # ^ |   0 Oh shoot, I didn't realize it's Oct. 25, not Oct. 24.
 » 5 weeks ago, # |   0 How did people solve A. Reconstructing the alphabet and D. A reliable counter?
•  » » 5 weeks ago, # ^ |   0 D: let's maintain two multisets, first, contianing first k elements and second containing others. Let s be sum of first. Then one iteration is to: delete first element in first; insert s into first if s < second; insert s into second and move smallest element from second to first if s >= second; update s. $O((r + n) \log n)$
•  » » » 5 weeks ago, # ^ |   0 :( I didn't expect D to have such a trivial solution so I implemented annoying $O(N)$ solution.
•  » » » » 5 weeks ago, # ^ |   0 What is the $O(n)$ solution you are talking about?
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 It basically involved storing the first K numbers and other numbers with 2 deques each. In a merge sort like fashion we can perform each update in $O(1)$ while still maintaining the relative order. I've attached my ugly code as it might make more more sense (the code itself is $O(n\log n)$ because I was too lazy to write a merge code and instead of just sorting. Codepackage Tasks; import Code.IO.InputReader; import Code.Utils.ArrayUtils; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.PriorityQueue; public class ReliableCounter { public void solve(int testNumber, InputReader in, PrintWriter out) { int N = in.nextInt(); int K = in.nextInt(); int R = in.nextInt(); long[] store = new long[N + 1]; for (int i = 0; i < N; i++) { store[i] = in.nextInt(); } store[N] = (long) (1e15); ArrayDeque smallestK = new ArrayDeque<>(); ArrayDeque stillSmaller = new ArrayDeque<>(); ArrayDeque untouched = new ArrayDeque<>(); ArrayDeque touched = new ArrayDeque<>(); long totSmall = 0; for (int i = 0; i < K; i++) { smallestK.add(i); totSmall += store[i]; } for (int i = K; i <= N; i++) { untouched.add(i); } if (totSmall <= store[0]) { while (R-->0) { long temp = totSmall; totSmall -= store[0]; store[0] = temp; totSmall += store[0]; } } else { while (R-- > 0) { long old = totSmall; int minId = minId(store, smallestK, stillSmaller); totSmall -= min(store, smallestK, stillSmaller); store[minId(store, smallestK, stillSmaller)] = old; if (old <= min(store, untouched, touched)) { if (smallestK.size() != 0 && minId == smallestK.peek()) { stillSmaller.add(smallestK.pollFirst()); } else { stillSmaller.add(stillSmaller.pollFirst()); } totSmall += old; } else { if (smallestK.size() != 0 && minId == smallestK.peek()) { touched.add(smallestK.pollFirst()); } else { touched.add(stillSmaller.pollFirst()); } totSmall += min(store, untouched, touched); if (store[untouched.peekFirst()] <= store[touched.peekFirst()]) { smallestK.addLast(untouched.pollFirst()); } else { smallestK.addLast(touched.pollFirst()); } } } } ArrayUtils.sort(store); for (int i = 0; i < N; i++) { out.println(store[i]); } } long min(long[] store, ArrayDeque i, ArrayDeque j) { if (i.size() == 0) { return store[j.peekFirst()]; } if (j.size() == 0) { return store[i.peekFirst()]; } return Math.min(store[i.peekFirst()], store[j.peekFirst()]); } int minId(long[] store, ArrayDeque i, ArrayDeque j) { if (i.size() == 0) { return j.peekFirst(); } if (j.size() == 0) { return i.peekFirst(); } if (store[i.peekFirst()] <= store[j.peekFirst()]) { return i.peekFirst(); } return j.peekFirst(); } } 
•  » » » 5 weeks ago, # ^ |   0 Wow this was pretty trivial :/ thank you!
•  » » 5 weeks ago, # ^ |   +10 For A, I wrote $T_5$ down, ABACABADABACABAEABACABADABACABA, and tried to find some useful pattern. After some time I realized that all odd positions have 'A'. With this, I can test if all even or odd positions are the same and map it to 'A'.Then I tried to erase all 'A' from $T_5$ and I got BCBDBCBEBCBDBCB where the structure is exactly $T_4$ so we can just repeatedly do the same. After every step, I erase half of the string(either all odd positions or all even positions) so it is $O(n\log n)$. It looks like it can be done in $O(n)$, though.
•  » » » 5 weeks ago, # ^ |   0 Neat! Thanks.
•  » » » 5 weeks ago, # ^ |   +21 Since you erase half of the string in each step, it's $O(N)$.
•  » » 5 weeks ago, # ^ |   0 i used dynamic segment tree.
•  » » » 5 weeks ago, # ^ |   +8 Do you mean that the leaves are the numbers and you store the number of times they appeared so far? And an intermediate node contains the sum of the numbers in that range?
•  » » » » 5 weeks ago, # ^ |   0 Yeah
 » 5 weeks ago, # |   +26 How to solve F?
 » 5 weeks ago, # |   0 where can you see the problems after the round ?
 » 4 weeks ago, # |   0 Is there an editorial for this contest ?
 » 4 weeks ago, # |   0 Please announce time of final round.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +18 I received an email with the following: Onward to the finals, which start November 7 at 12:00 (UTC+3). The competition will last 3 hours. I assume you are talking about the Algorithm track.
•  » » » 4 weeks ago, # ^ |   0 Thanks.
 » 4 weeks ago, # |   +10 I think that https://clist.by/ has incorrect time and date. If I understand the email correctly, this is correct time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=Yandex+Algo+Finals&iso=20201107T12&p1=166&ah=3 Please confirm that you'll be taking part in your personal account. I just see X below algo finals there. Nothing is interactive, I can't click anything.
•  » » 4 weeks ago, # ^ |   +23 I think I fixed the time on clist.by.
 » 4 weeks ago, # | ← Rev. 2 →   +3 I still wasn't able to reach any organizer. I got enough points in quals and even got an e-mail "Congratulations! You are in the Yandex Cup 2020 final" and yet I see only this in my profile:Please help ;__;EDIT: thanks to Chmel_Tolstiy for help, I'm added to finals now.
•  » » 4 weeks ago, # ^ |   +3 Lmao one less guy to beat. Git gud at computers.Jk, I had a button under "confirmation" and when I clicked it a second button appeared under "final". It leads to a Yandex.Contest page. Maybe you blocked a script or something.
•  » » 4 weeks ago, # ^ |   +20 I'm checking this issue
 » 4 weeks ago, # |   +25 I'm qualified, I click on the contest link from logged in area, https://contest.yandex.ru/yacup/contest/21825/enter and it says "Internal server error"
•  » » 4 weeks ago, # ^ |   0 We have some issues I'll register you and send you a message.
•  » » 4 weeks ago, # ^ |   0 Please, check it again
 » 4 weeks ago, # |   +5 How to solve A Need more coffee?
•  » » 4 weeks ago, # ^ |   +2 binary search over derivate
•  » » 4 weeks ago, # ^ |   +8 To expand on Errichto's idea: if you give one person $x_1$ coffee and another one $x_2$ coffee, and their derivatives at those points are not equal, that means that you could give someone a little more and someone a little less and improve your answer. Therefore, an ideal case is to give everyone an amount such that their derivatives are the same.
•  » » 4 weeks ago, # ^ |   +5 You can also do it without binsearch and with sort by $B$ as the only log-operation (maybe it can be eliminated too, not sure).Let's take out the constant sum of $C$, ignore $B \le 0$ and sort all other functions $(B-Ax)x$. All functions with $x \neq 0$ must have equal derivatives $K$ and all functions with $x = 0$ must have derivatives $B \lt K$, since if that isn't satisfied, we can always find a pair of functions and move $\mathrm{d}x$ coffee from the one with the smaller derivative $d_1$ to the one with the larger derivative $d_2$, gaining value $(d_2-d_1)\mathrm{d}x$. All the constraints I mentioned ensure that this is a valid move. It's important that the derivative of each function nicely decreases from $B$ to $0$.Let's pick some function + all those with greater/equal $B$ in sorted order. Then for each function, $B-2Ax = K$ ($\le B$ of our function) and the amount of coffee is $\sum x = \sum (B-K)/2A = \sum B/2A - K \sum 1/2A \le S$, which gives a min-formula for the optimal $K$. Now the answer is the max of answer so far and $\sum (B-Ax)x = \sum (B+K)(B-K)/4A = \ldots$. All sums are only over selected functions and can be computed nicely.
 » 4 weeks ago, # |   +5 35th place despite being nearly asleep for much of the contest (10AM on Saturday smh). Not bad.Interesting problems. E was kinda misplaced, counting pairs with $a+c=2b$ is obvious convolution and the extra step with $a < c$ is also pretty well-known d&c; I don't see what partial solutions the second subtask offered.
•  » » 4 weeks ago, # ^ |   -10 I don't see what partial solutions the second subtask offered. You can use bitmasks to write fast $O(n^2)$ solution.
•  » » » 3 weeks ago, # ^ |   +10 $O(N^2)$ for $N=5\cdot10^5$? Would anyone even risk wasting time on that? It's on the edge even for the huge TL.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 People who don't know FFT would. This is how we found out about this alternative approach. I was surprised too that it passes within half of time limit.
•  » » » » 3 weeks ago, # ^ |   0 It takes a 1-2 minutes to write simple bitset solution for the first subtask. But I couldn't pass the second subtask using STL bitsets. I was curious so I wrote my own bitset, after some constant optimizations squeezed it to ~7 seconds (given that I'm pretty bad at optimizing code). I think if one has prewritten bitsets and no FFT they may try to attempt $O(n^2)$ solution without any huge risks.
•  » » » » » 3 weeks ago, # ^ |   0 Can you please share your std::bitset solution?I've also implemented it in couple of minutes, but got TL. I'm sure I'm too stupid, but don't know where
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +5 Mb you didn't use right pragmas? Not sure which instruction sets are actually helpful I just copypasted those magic words from somewhere. Spoiler#pragma GCC optimize("O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") #include using namespace std; using ll = long long; const int N = 2.5e5; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; ll ans = 0; bitset left; bitset right; int n = s.length(); for (int i = 0; i < min(n, N); i++) { if (s[i] == 'c') { right.set(i); } } int j = N; for (int i = 0; i < n; i++) { right >>= 1; if (j < n) { if (s[j++] == 'c') { right.set(N - 1); } } if (s[i] == 'b') { ans += (right & left).count(); } left <<= 1; if (s[i] == 'a') { left.set(0); } } cout << ans << endl; return 0; } 
•  » » » » » » » 3 weeks ago, # ^ |   0 Thank you so much, your are right, I forgot about pragmas. Got 8.984s on 32nd test without modification of my code :) It's stange I didn't get that I can use bitsets of length N / 2, not N: but even with this constant optimization TL without pragmas... Shame on me
•  » » » » » 3 weeks ago, # ^ |   0 I just plugged one of my SSDs into an external enclosure and pulled out some old FFT implementation. Also an option is putting all your solved problems in one place and doing grep -r . -e ' convolution\('. Gotta completely miss the idea that convolution can be used since fast implementations are everywhere.And as our purple friend below shows, it can really be risky if you don't have ingrained constant optimisations.
•  » » 4 weeks ago, # ^ |   +8 can you elaborate on what convolution is please? (i spent the entire 3hs to come up with some kind of tree ds for E and now i see "obvious"). I'd be super grateful
•  » » » 3 weeks ago, # ^ |   +5 Consider a simpler version of the problem, where you want to count the number of $abc$ or $cba$. Then, for $b$ at position $k$ you want to count the number of pairs of positions $(i,j)$ such that $i+j=2k$ and $s_i=a/c, s_j=c/a$.Consider polynomials $p$ and $q$, where $p_i=1$ iff $s_i=a$ and $q_i=1$ iff $s_i=c$. In $pq$ the coefficient at $2k$ is exactly what you are looking for. So, you can create $p,q$ and multiply them with FFT.In order to count only $abc$, you can use divide and conquer approach. Split the string in two halves, count the number of triples where $a$ is in the first and $c$ is in the second half with the described approach, and solve recursively for both halves.
•  » » » » 3 weeks ago, # ^ |   0 If I'm not mistaken, convolution with FFT can be done in $O(N\log{}N)$. Does that mean that the complexity of the divide and conquer + FFT solution will be $O(N\log^2{}N)$?
•  » » » » » 3 weeks ago, # ^ |   +5 yes
•  » » » » 3 weeks ago, # ^ |   0 Thank you so much!!! Got some stuff to learn to implement it. But now I totally understand the general idea!
 » 4 weeks ago, # |   +45 Thank you all for participating! We did the best to fix some issues and to prepare good problems.https://contest.yandex.ru/contest/22052/ -- one can register to look at problems or to upsolve. Hope to add both rounds into gym shortly.Congrats to winners ksun48, Um_nik and voidmaxSpecial thanks to tourist for great performance (there only three persons in Yandex Cup who has already been a winner twice). You are the champion in our hearts and minds ;)
•  » » 4 weeks ago, # ^ |   +3 Will there be an editorial ?
•  » » » 4 weeks ago, # ^ |   +1 Sorry, we have not prepared it yet. We'll publish it in some time on cup's page. Now community can help you I think.
•  » » 4 weeks ago, # ^ |   +13 Thanks for the great contest!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +20 91 seconds of penalty time :(I liked the tasks though, thanks
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +51 The problems were great but please don't change the rules during the contest. Some people could have waited with submitting the next problem till 2:00 for frozen standings. And maybe there should have been an announcement that tourist doesn't fight for prizes, because this might change strategy for people in the top. That being said, none of that affected me because I didn't do that well :Dbtw. here are highlights of my screencast (10 minutes with commentary): https://youtu.be/ifsVDBOg39E
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 3 →   +60 So here's my proof of a key part of full D: the only cases where the optimal string contains "ab**e" are: $e = 1$ is the end of the string "ab" contains at most 2 non-zero digits Step 1: $e = 1$, not the end of the string: Let's just concatenate and "ab1" is better than "ab". From now on, let's assume $e \ge 2$. Our alternatives to "ab**e" are "a**b**e", "a**be", "abe" and splitting "a" or "b".Step 2: When is splitting into "a**b**e" better? Obviously not when $a$ or $b$ is at most $1$, so let's denote the number of digits of $b \ge 2$ by $k$ ($10^{k-1} \le b \lt 10^k$) and prove by contradiction that $k \ge 2$ isn't allowed. The loosest possible constraint is $((a+1) \cdot 10^k)^e \gt (a\cdot 10^k + b)^e \gt a^{b^e} \ge a^{10^{(k-1)e}}$. If this doesn't hold, we want to split regardless of $b$. We're looking for $(a+1)^e \cdot 10^e \gt a^{10^{(k-1)e}} / 10^{(k-1)e} = f(10^{(k-1)e})$. The derivative of $f(x) = a^x / x$ is $f(x)(\ln a - 1/x) \gt 0$ for $a,x \ge 2$. Since $a \ge 2$ is assumed, the only case we need to consider is $k = 2$. If we increase $k$ any more, then the right side of the inequality increases and the left stays constant, so if it didn't hold for $k = 2$, that won't change for any greater $k$. We're looking for $(a+1)^e \cdot 100^e \gt a^{10^e}$ with $e \ge 2$. Since $a+1 \lt a^2$ and $100 \lt a^7$, it implies $a^{9e} \gt a^{10^e}$. It's easy prove that $9e \lt 10^e$, so this is impossible. Splitting just makes the exponent of "a" too massive. Step 3: Notice that even if "b" is at most $9$, there can't be a way to split "ab" where "b" would be larger. Since "a" starts with a non-zero digit, let's look at remaining cases for "ab": if there are at least $4$ non-zero digits in "ab", we can always find "b" that starts with the second-to-last of them, where both "a" and "b" are at least $11$ if there are $3$ non-zero digits and the first isn't "1", the same applies with $a \ge 2$ and $b \ge 11$ same if there are $3$ non-zero digits and "ab" starts with "10" if the 3rd non-zero digit isn't at the end, $k \ge 2$ is the only option "1d0...0g", where "d" and "g" are digits, is the only remaining case with $3$ non-zero digits with only one non-zero digit there's no way to split anyway, so "d0...0" is an option with $2$ non-zero digits, if each has a '0' right after, we can still split with $k \ge 2$ "d0...0g" is still an option "1d0...0" is the last option, since if the non-zero digits are at the start, the first has to be $2$ Step 4: It's obvious that there's nothing to do if "ab" is "d0...0", so let's ignore this and just assign each '0' to the previous non-'0'. Intuitively, pumping value into the exponent instead of the base is good, so let's see if we can eliminate "1d0...0g" as an option. We had $\left((10+d)\cdot10^{k+1}+g\right)^e$. Let's expand "e" into "h**r" and move "g" there, so that it becomes "gh**r". Now we have $\left((10+d)\cdot10^k\right)^{e^\prime}$. Let's add another variable $u = (10+d)\cdot10^k$ so we could say in a cleaner way that we're disproving $(10u+g)^e \gt u^{e^\prime}$. A useful estimate: $(10u+g)^e / u^e = (10+g/u)^e \lt 11^e$. Now let's estimate $e^\prime-e$. The string "gh" is at least $(g+1)h$, so $e^\prime \ge (g+1)^r h^r = (g+1)^r e \ge (g+1)e$; $e^\prime-e \gt ge$. Since $u \ge 11$, we get $(10u+g)^e / u^e \lt 11^e \le u^{ge} \le u^{e^\prime-e}$. QED. Step 5 (extra): Even for $e = 1$, splitting "ab" into "a**b" can be good. When is $a^b \lt a \cdot 10^k + b$? Let's just get a rough bound: with $a \ge 2$, $a \cdot 10^k + b \lt (a+1) \cdot 10^k \lt a^2 \cdot 10^k \lt a^2 \cdot a^{4k} = a^{4k+2}$. Then $b \lt 4k+2$ must hold. However, with $k \ge 2$, $b \ge 10^{k-1}$ and $10^{k-1} \ge 4k+2$, so $a = 1$ or $k = 1, b \le 5$. If "ab" has at least $4$ non-zero digits, we can always pick $a, b \ge 10$, so that's not a case we want. If "ab" has $3$ non-zero digits, we can pick the last (we just showed it can't have '0'-s after it) as "b". Then $a \ge 11$. With $a \ge 11$, we have a better bound $10a+b \lt 11a \le a^2$, so $a^b \lt 2a^2$ only if $b \lt 2$. If "ab" has $3$ non-zero digits, we can also pick the middle one as the start of "b". Then $a=1$ must hold, so "ab" must be "1d0...01". Again, "d0...0" is obviously one case. If "ab" has $2$ non-zero digits but '0' at the end, "1d0...0" is the only option. If "ab" is "d0...0b" with at least one '0', it must be "d0...01" or "102" ($a = 10$, where we bruteforce $b \le 2$). If "a" and "b" are digits $\ge 4$, a bruteforce check shows that "a**b" is always better. All other 2-digit numbers "ab" are still possible. We just found out that each substring between exponents must be a 1-digit or 2-digit number, "102", "d0...01", "1d0...0", "d0...0" or "1d0...01". In addition, "1d0...01" (step 4) and "102" (proof is pretty short, you can finish it yourself) are only possible at the end.