activities for non-rich competitive programmers

On yandex

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

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

I told you '_'

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

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.

Started, what r u talking about?

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

Hello!

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

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

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

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):

• The adjustment of the first part and the Error Correction Code took me about an hour :) One can do it much faster.

Try it out!

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.

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 :-)

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.

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.

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 this

UPD: ah sorry, I am talking about the last problem

What was the maths in problem A except computing lcms and using inclusion-exclusion principle for 3 numbers?

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.

It has been rescheduled to 3rd November (because 2nd November is a working day in Russia).

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

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.

Description looks correct. Can you share the code?

So score cutoffs are:

• Frontend — 26
• Analytics — 31
• Backend — 160
• Algorithm — 3
• iOS — 13
• Android — 12

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.

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?

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

Do you handle this:

If the given number k is greater, than the pharaoh wants – he does not wish to answer that many questions, the jury program will respond with the number −1. In this case, you must correctly terminate the program (to receive a correct verdict).

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

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

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.

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.

Time of the last AC submit in seconds

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)

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

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).

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

schoolers have seperate standings :(

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

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.

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.

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.

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

Question about problems still remains.

also data analytics semi final round too