## Hello Codeforces!

We are delighted to invite you to participate in Yandex Cup 2024! Yandex Cup is a championship in six different tracks:

- Algorithm❤️
- Backend
- Analytics
- Mobile development (iOS and Android tracks)
- Frontend
- Machine Learning (Self-Driving Cars and Music information retrieval tracks)

This year, as a pilot project, we are inviting schoolchildren (so far only from Russia) to participate in the Algorithm and Analytics tracks.

The championship consists of three stages.

## Schedule

The stages and dates are different for Machine Learning and Mobile Development. More details about the terms and conditions can be found on the track's pages.

**Qualification** is a contest with a virtual start. You can write a context during the week from **14 to 20 October**. The duration depends on the selected track. After the qualification stage we will publish the criteria for the semifinal.

**Semifinal** will be held on **3 November**. The start of the contests is at **12:00 (GMT+3)** and at **17:00(GMT+3)** at the Algorithm track. Duration depends on the selected track. The top 20 semi-finalists in each track and the top 10 students in the tracks Algorithm and Analytics will qualify for the finals

**The final** of the competition will be held in Tashkent Uzbekistan **on 2-6 December**. All expenses related to travel and accommodation of the finalists will be covered by us.

This year, we have also increased the prize fund, which amounts to 12.5 million rubles

See you at the Yandex Cup!

Auto comment: topic has been translated by Yandex (original revision, translated revision, compare)Yandex Contest of tourist was fun to watch without understanding anything.

the prizes are not worth trying

activities for non-rich competitive programmers

on which website will the contest be held? it will be my first time participating. some help would be appreciated :prayge:

On yandex

anyone can participate right? I am not from Russia can I participate?

yes

It seems that only the Algorithm track is available in English. To what extent will the non-Algorithm tracks use Russian? Would it be manageable (time-efficient) to use Translate to understand and solve problems in other tracks, say ML?

++, i wanna participate in the ML Track but the russian language is bugging me

These opportunities can also be a great motivation for competitive programming .

Form page is not opening, showing loading only !

It seems to me that there is no "other" option for university. Nevermind, found it.

I told you '_'

what did you choosed i can't find it either ! got it its '_Другое'

I didn't really understand how many people will qualify to finals

The time to start qualification round is not properly mentioned. What time it is??

This century

It says it up there. You can start the contest anytime during the week.

Qualification is a contest with a virtual start. You can write a contest during the week from 14 to 20 October. The duration depends on the selected track. After the qualification stage we will publish the criteria for the semifinal.

Where is the contest link? There is no email or any link in this post also.

In my browser history.

It

`s 10/14 and contest has not started. There`

s even no announcement of when does contest start!Started, what r u talking about?

May I ask how long the window of qualification round would take? It seems I cannot find some useful information related to this... I need to decide when to start once I could know the duration of the window :(

It's a 2 hour round.

Duration of Qualification by track: Algorithm — 2 hours Analytics — 5 hours Backend — 4 hours Mobile Development — 3 hours Frontend — 5 hours All contests with virtual start

I think I'll pass.

Hello!

Users located outside of Russia can also sign up using their Facebook, Google or X account.

Thanks for the clarification. Thankfully I have several fake facebook accounts that were registered a long time ago so I can use one for this. Please avoid making login system that requires phones\government id verification in the future.

Appreciate the organization of the contest though, thank you.

Hi! It seems that the Yandex Forms page I'm redirected to after creating a Yandex ID also requires a phone number. Is there a way to bypass that too?

You can just put fake number like +1(111)1111111, it's not validated there.

Oh 😳

Thanks a lot!

Only Russian allowed to get a price?

What was the last year qualification border(to semifinals)?

When will the results / cutoffs for Algorithm and Analytical Rounds come out!! :-)

Will we get t-shirts this time :--))

Is there any reason why a points cutoff and/or number of participants qualifying to a semi-final is not announced beforehand? Is there at least some statistics from the previous years about how many problems was required to advance from qualification to a semi-final in the Algorithm track?

Managed to find criteria in the 2023 post, participants said the border was approximately about 3-4 tasks.

when could us to discuss the tasks of the contest?

I want to know how to solve task F :(

Very true, i would be grateful if someone can explain F itself. I was not quite sure if I understood the task itself. The only significance of 16 i saw is that log_2 (2024) = is 11 and 11 < 16 due to which i thought of binary search but not quite sure how to proceed at all.

Let's discuss the solution to the 15-question problem.

Note that we ask all our questions before receiving answers! After processing the answers, we should determine if there is an error (in case there is one) and correct it.

The first part (if we only get correct answers, this is a classic problem):The i-th set contains all numbers whose i-th binary bit is 1.

We ask 11 questions and we get a guessed number.

The second part (the idea is that we will get 15 bits of information and need 11 of them to be correct... [Hamming Code], right?11 + 4 bits is a well-known basic code):Try it out!

Thank you so so so much. This makes a lot of sense :-)))))

The idea of hamming codes did strike me in contest but i did not realise the "if we get only correct answers" it is 11 part.

Now it makes so much more sense. TYSM!!!

Did anybody solve Backend D?

I didn't solve D completely, only got 14 of 200 points.

My idea was to store the data on cache servers (hash(key) % n) and ((hash(key)+1) % n). When a key arrives I first check the cache servers. If they have this key, I simply return the data. If the key is not there, I request db, store to the cache servers and return the data. In case one of the cache servers is down, I can always request from the second cache. Also in this way the data is evenly distributed across the caches.

It was pretty hard to debug, because the stderr output was limited in length. I don't know if this solution satisfies all the conditions: at least it can request the db twice in case the program is stopped at the moment between GET from db and PUT to cache (maybe we had to do something with catching signals?). Besides, the example suggests that the program straightly requests the db when it sees a key for the first time, but if we remember all the keys in memory, it will be cleaned when the program is restarted.

As far as I could see from the stderr, in the failing test all the keys were present in db, but that case could probably happen too.

I also got 14 points. Have no idea what can be wrong. Did you order somehow cache urls? One of my idea, that after restart order of urls in the config has changed.

Actually, upsolving is open through the same link in your account.

Got 200 with absolutely same idea.

I used C#. My mistake was that I forgot native

`string.GetHashCode()`

is not stable between runs. As soon as I wrote alternative hash code I got full score.100%! the same holds for Python hash(). I thought that is cool, because there will be no worst case example, but didn't realise of reruns.

could you share the code, pls? i also use c# and don't understand why my solution didn't work with io property.

intended solution for problem C and D of algorithmic track , how the M-N>N was utilized in D and for C is it DP or greedy way also possible ?

D is quite a nice problem

The basic idea is that you need to find the value of both M, N. Use the fact that M — N > N --> M > 2N

So first you output 1, if you get okay then you have found N.

Otherwise N >= 2 so M > 4 so output 5. (not binary powers i.e, 1 2 4 8 etc works but this is slightly optimised). Then you N >= 6 so M > 12 so try 13 and so on.

Once you find the "ok" you know the values of m, n, so just binary search to find the answer

For C, the question was a bit confusing to me; but after some amount of guessforces and checking if samples worked or not (and WA's :-), this finally worked

sr[i].second = max(sr[i].second, r); sl[i].first = min(sl[i].first, l); sr[i].first = min(sr[i].first, r); sl[i].second = max(sl[i].second, l);

repeat this from i = n — 1 to 0 and then print

max(sr[0].second — sr[0].first, sl[0].second — sl[0].first)

I hope this was helpful :-)

D was really cool now that i got how to utilise that M>2*N thanks, for C do you have a proof of why your algo works ? is it possible to use dp in this ?

For C you either use only L or only R, so you can try both and take the max. For the proof:

First you can realize that if you reach the extreme on the left first then you can use only L at the beginning and then only R after reaching it. Similarly if you reach the extreme on the right first, you only use R at the beginning, and then only L. With this I think you could already use some data structure to solve the problem.

If you take an optimal solution. In the first case (first use L then R), if you replace some of the L into an R the maximum distance either doesn't change or increase by 1 or 2, so by doing this you end up with a solution that has only R and is just as good or better.

nice proof really liked it , would like yandex cup in next years to have the all the tracks in both English and Russian it would be so much better tbh . Btw those who did the analytics track how they did they solve A,D,E ?

A.Let $$$F(a, b)$$$ be the probability of placing a thing in the first cave after $$$a$$$ unsuccessful attempts to find it in cave 1 and $$$b$$$ attempts in cave 2.$$$F(a, b) = \dfrac{0.65 (1 - 0.44)^a}{0.65 (1 - 0.44)^a + (1-0.65)(1-0.44)^b}.$$$

So the answer is $$$F(3,7)$$$ and $$$F(2, 0)$$$.

D.Let $$$\alpha$$$ be the expectation of one move (when all 5 dices are in hand); and $$$p$$$ be the probability to get 0 points at this move. I wrote some python code to calculate it.Then it's reasonable to try the next way: find $$$x$$$ such that $$$x > (1-p)x + \alpha$$$, the value which is more likely to get zero points by move than to increase it.So, $$$x = \alpha / p$$$. And we have to round it up to the nearest integer divisible by 5.

E.Find some borders of '1': minimal and maximal row and column:P.S. I posted video with some explanations and ideas here (in russian)

What is the criteria for the Semifinals qualification this year?

Am I the only one, who finds A to be harder than B and C? Maybe, I didn't get the easy idea of the solution, but I needed binary search and use not so easy math), while B and C were pretty trivial.

Also, D is not original, it's almost the same as this task from NCPC

I didn't see anyone asking, but what's the intended solution to E? At the upsolving, I solved it, using dynamic programming, where I kept at each bit hash table, where values were the weights after including some last bits and not including bits that are less or equal to the current, and at the keys I kept the number of ways to achieve that weight in the following way. The only thing, that optimised this approach, was to check, if it's potentially possible to achieve this weight (if multiplication of mask with all 1 bits that are less or equal than the current and the biggest integer from the array a is bigger or equal to the current weight, then we potentially can achieve this weight, otherwise it's impossible). You can actually see my code here. I'm wondering, if my solution is what was intended? I still don't have proof of why this should work fine, so, maybe, someone could provide it?

I don't know if this is intended, but a trick is this: You try to satisfy the equality $$$\sum w_i 2^i = n$$$ gradually, by first making sure it is true $$$\mod 2$$$, then $$$\mod 4$$$ and so on. When working $$$\mod 2^k$$$ all weights multiplied by a bigger power of two do not matter. This gives rise to the following DP state:

$$$\text{dp}[k][\text{carry}] = \text{number of ways to satisfy equality} \mod 2^k$$$ $$$\text{and such that the weights } <k \text{ carry over to the bigger bits with this carry.}$$$

In this DP state you have not decided yet what the weights will be for the bigger powers. Notice that the carry is at most twice the input weights, which is 100, and it does not make sense to add bigger weights than $$$\log_2(n)$$$, and for each DP state, we enumerate what the next weight will be. So this solution can work for much bigger constraints.

My solution is the same. Here's the code if someone needs it:

CodeFor problem E, I just submitted a brute force and it passed within 10ms...

I think yours is indeed intended. Actually, it would be more intuitive if you start from the $$$0_{th}$$$ bit, and then erase all states where $$$0_{th}$$$ to $$$i_{th}$$$ bits are not equal to $$$0_{th}$$$ to $$$i_{th}$$$ bits of $$$n$$$. There would only be at most $$$100$$$ states in each iteration, since you can at most add $$$100 * 2^i$$$ and $$$0_{th}$$$ to $$$i_{th}$$$ bits are fixed, thus only $$${i+1}_{th}$$$ to $$$i+6_{th}$$$ bits are free.

Your code actually does similar things, but just in a reverse manner. Just your code fixed $$$i+7_{th}$$$ to $$$26_{th}$$$ bits are $$$0$$$, and only $$${i}_{th}$$$ to $$$i+6_{th}$$$ bits are free.

Disclaimer: I might be wrong about the exact number of the bits above but I'm too lazy to validate them. Just roughly it could show that its $$$O(log(n) * max(a_i) * m)$$$.

I had a O(nm / 2^B + m^B) solution

You do a dp for all bits except for the smallest B bits and bruteforce the coefficient of smallest B bits

Problem E: after your setup, you want to receive a $$$k$$$-bit word and uniquely determine the word from your list it differs from in at most one position. So, in particular, every two words in your list must differ at 3+ positions, because otherwise you wouldn't determine the answer for a word that differs from both of them in at most 1 position.

First of all, since every your codeword generates $$$k+1$$$ possible answers you want to map to it, we have $$$2025(k+1) \le 2^k$$$, so $$$k\ge 15$$$. Second, this construction is called "error-correcting code", I used some linear code that is basically a carefully chosen 11D subspace of $$$\mathbb{Z}_2^{15}$$$, so that every non-zero vector there has at least three ones. I learned such things in my university earlier, but, to my shame, I had to google this during the round.

Apparently, you also needed to handle receiving

`-1`

, because it could happen any time and didn't mean that you did something wrong (???). Would be happy to hear the reason behind thisUPD:ah sorry, I am talking about the last problemWhat was the maths in problem A except computing lcms and using inclusion-exclusion principle for 3 numbers?

Yes, I got accepted using this principle too, but I find it to be harder than greed approach in C or very trivial trick in B. I find them to be easier from the implementing point either.

I agree that A is easier than B, C and even D. But in ICPC-style contests we cannot actually rely on the problems being sorted by difficulty (although it would be nice in this case because it's just a qualification round open also to newcomers).

If understand it correctly your solution is indeed fast, and I have the same idea but used recursive approach: $$$rec(k, w)$$$ — number of ways to get weight = $$$w$$$ using the first $$$k$$$ bits. The idea is to try to use brute-force from the highest bits and memorize the values that you visited before, and most importantly to exit the recursive call if it is not possible to get required weight. (I sorted array $$$a_i$$$ to make it more convenient). It is not possible to get the weight = $$$w$$$ if $$$w > a_m \cdot (2^{k+1} - 1)$$$. In the worst case, $$$a_m = 100$$$, so if $$$w > 100 \cdot (2^{k+1} - 1)$$$ we can exit the recursion.

This solution works fast, and can be proven in this way: For the $$$k \leq 18$$$ we can use $$$dp_{k, w}$$$ — number of ways to get the weight = $$$w$$$ using the first $$$k$$$ bits. This dp takes $$$\sum_{k=0}^{18} (2^{k+1} - 1) \cdot 100 \cdot 10 \approx 2^{20} \cdot 1000 \approx 10^9$$$ operations. And the last 8 bits can be calculated by brute-force in $$$m^8 = 10^8$$$ operations.

On practice this solution works much faster because the brute-force for the last 8 bits has many cutoffs and dp is calculated recursively, which makes solution faster as well. My solution works in 2ms for all tests.

Also, this problem is very similar to the 2123. Knapsack.

In the post it says the semi-finals is one 2nd November, however in the website it says 3rd November. Can you please confirm which is correct?

It has been rescheduled to

3rd November(because 2nd November is a working day in Russia).can someone also discuss the analytics track too ? for A is it bayesian only ?

How to know whether I qualify? Also how to solve E?

It will be announced in a few days, probably you will receive an email.

I guess if you solved maybe >=3 or 4 you will qualify

Yandex Can you add Node.js to Algorithm track next year?

What is wrong with my Algorithm A?

I used binary search with inclusion-exclusion principle, that give the number of good numbers less than $$$mid$$$ is

$$$mid/lcm(a,b) + mid/lcm(b,c) + mid/lcm(c,a) - 3*(mid/lcm(a,b,c))$$$.

But why am I getting WA on 25?

When all three numbers are different, this is the correct approach (at least, I was able to pass test 25 although didn't AC the whole problem).

You need special cases for a=b=c and when 2 out of 3 numbers are equal (and in the latter case you need to take into account the case when one of these 2 equal numbers divides the third one or vice versa).

But still, despite all this handling of different cases I got WA 64 and would be interested to learn what's wrong with my solution.

The above formula works even in case if some of the numbers are equal. The thing is that you need to postprocess the final value to get the answer (you need a number that divides by exactly 2 of them).

I keep failing at test 103.

https://codeforces.net/blog/entry/134927?#comment-1210657

Thanks, but in order to pass all tests, I had to change from:

Spoilerto:

SpoilerDescription looks correct. Can you share the code?

My codeYou can return 10^18 + 5 as an answer instead of -1 based on instructions.

One more thing is that there can be overflow during lcm(aa, bb).

Oh my bad, thanks got it

where can I see the standing of algorithm round?

According to the telegram channel of Yandex Cup, everyone, who receives at least 3 points, advances to the semi-final. Also there are open standings now, and not only for algorithm track (for backend also, idk for other tracks).

(I'm talking about the algorithm track, for backend track you needed to receive at least 160 points).

So score cutoffs are:

This year Yandex employees were also allowed to take part in the competition. I thought initially that there will be a separate leaderboard for them. But now I see Chmel_Tolstiy in the analytics leaderboard and elizarov in the backend leaderboard.

Does it mean that Yandex employees compete together with everyone else and potentially they can occupy some of the top-20 spots in the finals for each track? Please clarify this as it significantly influences strategy of choosing the track for the semi-finals for those who qualified to the semi-finals in multiple tracks.

Employees and juniors have separate scoring for the results of the contests

But how do we know who is the employee and who is not in the scoreboard? Or are you saying that there will be separate leaderboards for the semi-finals unlike in the qualification?

We have prepared 3 contests with the same set of tasks: - for external participants - for employees - for school students

Therefore, we will have separate leaderboards for each group, which will be easier to navigate.

Has the date of the Semifinal been changed from November 2nd?

According to the schedule on https://contest.yandex.com/yacup/schedule, it overlaps with AtCoder Grand Contest 069, so I would like to request a time adjustment if possible. Yandex maroonrk

Thanks!

Yes I can postpone the AGC if necessary, but this blog says the semifinals will be held on 2nd Nov, so I want to confirm that the correct date is the 3rd. Could anyone from the Yandex team answer this?

Yes, sorry for the confusion. The semifinal will take place on 3 November. The start times of the tracks are different. For example, the semifinal of the Algorithm track will take place on 3 November from 17:00 to 18:00 UTC +3 Detailed schedule here: https://contest.yandex.com/yacup/schedule

We did not foresee that the 2nd of November is a working day in Russia

What's the solution for F. Zeroth Rome ?

This is the editorial I wrote, maybe it's useful.

Where can I find solutions of problems in algorithm round?

In problem F, why does code1 result in a runtime error on test 1, while code2 and code3 pass all tests?

It seems something might be off with test 1.

Do you handle this:

In the email sent yesterday, it said, "The top 10 participants from the semifinals in each track will head to ancient Tashkent." But elsewhere it says "top 20." Which is correct?

Yandex

Hi! The Algorithm track will have 40 participants in the finals 20 external participants 10 employees 10 schoolers

I think I registered as an external participant, so does that mean that email (top 10) is a typo? (I'm waiting for other people's information too)

Forty people will advance to the final in the Algorithm track: - 20 external participants - 10 employees - 10 school students

I would greatly appreciate it if you could send me a direct message indicating which communication mentions only 10 participants on the final.

I sent you a DM.

Thanks!

Where is the Yandex Algorithm semi-final contest link? Is it the contest time now?

I messed up the time. The contest is like, 9 hours from now.

The correct start time of the contest is November 3rd at 5:00 PM Moscow time. Perhaps this link will help you get oriented.

Where is contest link? I qualified but don't see how to enter

The link to the contest will appear in your personal account at https://yandex.ru/cup/profile

Approximately one hour before the start of the contest.

Where is the semi-finals contest link? The mail i recieved says "Go to your account" but there is no link there to enter the competition Yandex ?

The link to the contest will appear in your personal account at https://yandex.ru/cup/profile

Approximately one hour before the start of the contest.

Okay, thank you!!

How are ties broken in the Algorithm Semifinals?

Time of the last AC submit in seconds

Is it possible to read problems and watch standings of the algorithms semi-finals while the contest is running?

Did anybody solve Backend C with DDoS?

can we see the problems of semifinals ? Yandex

Could anybody briefly explain how to solve C in algorithms track?

Check this blog. Problem I is the same as C in the contest. You can see implementation from the github link in the blog

Let A be the adjacency matrix. We are looking for the sum of M * A^k where M = [0 0 .... 1 0... ] where 0 is at the v'th place

We can precompute A, A^2, A^4, .... in n^3 log(n) and then compute M * A^k in qn^2 log(n)

How long does your code work? Constraints sound weird btw. I was writing the code, praying that it would pass the TL.

(It’s funny that I submitted two solutions: the first one had #define int ll, which passed all tests (3.719s), and the one without that define got a TL. XD)

3s on yandex, and 1.8s on codechef ide. It was close yeah

My solution with the same idea works in 1.4s on yandex. idk if I'm doing anything particularly smart, you can see the code here.

one thing i can think of is you are using arrays instead of vectors. Otherwise, our codes are similiar

Compute it for all $$$k < 3n$$$ in $$$O(n^3)$$$ time. For fixed $$$v$$$ the answer is a recurrence of size at most $$$n$$$, so use Berlekamp-Massey to recover it, and solve the recurrence in $$$O(n^2 \log k)$$$ time (most BM template will have that recurrence solver)

https://codeforces.net/gym/102644/problem/I

Pretty bad contest tbh. Problems A and B are okay I guess? In problem C I knew it needed matrix exponentiation but am not really good with it so after some research I found a blog for Errichto with the same problem so I used the solution. Didn't read problem D, but if my solution for E is intended, it's really bad.

My solution for EBasically create a vector for each prime factor, and we have a constant B =7000. For each prime factor, if the number of elements that have is less than B then we can do brute force for each pair and check distances. Otherwise, do a dfs with lazy seg tree to update distances each time and get the answer. Maybe also dp with rerooting works, still very long implementation. I spent the last 40 minutes implementing and it got wa because a 160 line code is definitely bugged

You can find the largest distance from each node by finding the diameter of the subset of nodes with a certain prime factor. To find diameter, just find the farthest node in the subset from an arbitrary node, and then find the farthest node from that node. Precompute LCA distances to compute distances in O(1).

Yeah that makes sense, still a lot of implementation though

It's only ~30 lines excluding the lca / prime sieve templates.

SpoilerOk I just skill issue

There's (imho) an easier way to find the diameter (and it is online!):

If vertices $$$a$$$ and $$$b$$$ are the current diameter, and there's a vertex $$$c$$$ inserted to the set, then the new diameter is either $$$(a, b)$$$, $$$(a, c)$$$ or $$$(b, c)$$$

Nodes might get deleted from the set though

Wdym? You just store the set for each prime

Nvm I think I got it wrong

Would be much better to have $$$T <= 100$$$. Spent so much time hardcoding all the base cases / tail optimization.

Why would you need to hardcode or optimize anything?

if you try doing for power <= p, formula and for power > p, "pure" bruteforce, it becomes hard

(i did for power >= 3, store them in a list and prefix sums, which passes easily)

Yeah, I had to do formula until power $$$p <= 5$$$ and bruteforce for the rest. Had a bunch of code that looks like this to squeeze into TL.

Unless there's a much simpler solution.

there are only <= 10^6 relevant numbers for powers >= 3. You can just binary search on a vector of those numbers after precomputing?

Attaching the core of my solution; sounds similar to what has been mentioned above minus binary search.

SpoilerIt's just that it's code is pretty messy because of the r <= 10^18 condition so lotsa mods would've been much cleaner for r <= 10^9

27th place, any chance? Yandex were there any people <= 26 rank who are employees/school?

schoolers have seperate standings :(

There's a chance of 7 people above you rejecting their invitation :D

yep i know, if anybody is rank <= 26 and does not plan to attend, feel free to reply here thanks

same but for rank <= 24 haha :)

Does someone who solved F really quickly mind sharing their solution (e.g., hos.lyric)?

I got sidetracked for a while (misreading the problem at first, then trying to optimize a solution idea that was getting TLE38 but was actually wrong). Even if I had come up with the correct idea from the beginning there's no way it would have taken me less than twenty minutes to solve. :)

I used a dynamic Aho Corasick with a small to large technique on tree. This works in $$$O(S \log^2 n)$$$ but passed in 2.5s.

Hi, do you have any resources on dynamic Aho Corasick? Thanks!

4th trick in Adamant's general ideas

Thanks so much!

Build Aho-Corasick on $$$s_i$$$'s. For query $$$(v, t)$$$ traverse the trie by $$$t$$$ and at each node $$$x$$$ we want to count the vertices (of the input tree) in the subtree of $$$v$$$, marked on $$$x$$$-root path of the trie (following the failure link). This is already a 2D query problem. We can scanline the DFS order of the trie to achieve 1 log.

If you DFS on the failure link tree, then you can maintain set of points in the root-node path for all nodes (add to set when entering it, and remove from set when leaving it).

We need to count the number of points under the subtree of input tree quickly, so maintain that DS with Fenwick trees indexed by DFS preorder.

Although I didn't finish it in time because of slowness on other problems, the idea I had which was not hard to implement was: Given that you have s[i]'s in order of DFS in numbers, the problem is basically a range count query. We can solve this offline, by slowly adding the s[i]'s in a Aho-Corasick which you can add words to (it has an extra log factor, and uses the standard log(n) versions of the DS trick). I already had this dynamic Aho-Corasick code. And then you just need to subtract two prefixes to get the result of a range query.

anyone mind to post semifinal solutions?

When will the problems and standings of the Algorithm semi-finals be available to outside spectators?

Actually, I found the standings — https://contest.yandex.ru/contest/70295/standings/

Question about problems still remains.