what about t-shirts?

В чем смысл ограничения, что можно участвовать только в одном финале?

Уважаемый Яндекс! Расскажите, пожалуйста, почему вы считаете, что все люди в мире живут в ограниченном наборе городов, список которых хранится у вас на сервере, а вся остальная территория планеты сплошь необитаемая? Или как ещё объяснить, почему в поле "Город проживания" в форме регистрации нельзя ввести произвольное значение, а оставить его пустым тоже нельзя? Пожалуйста, сделайте так, чтобы люди, которые не живут в городах, список которых хранится у вас на сервере, тоже могли зарегистрировать. А то неудобно как-то.

If I start qualification round virtual contest now, will I write it for 2 hours or till 26 october for 7 days?

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.

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?

Are we allowed to discuss the problems from the qualification round here now?

Будет ли разбор задач квалификационного тура ?

How did people solve A. Reconstructing the alphabet and D. A reliable counter?

How to solve F?

where can you see the problems after the round ?

Is there an editorial for this contest ?

Please announce time of final round.

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.

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.

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"

How to solve A Need more coffee?

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.

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 voidmax

Special 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 ;)

Auto comment: topic has been updated by Yandex (previous revision, new revision, compare).

Автокомментарий: текст был обновлен пользователем Yandex (предыдущая версия, новая версия, сравнить).

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.