Hello everybody!
On Mar 3, 10:00 Moscow time, Round 1 of Yandex.Algorithm 2018 competition will take place. I wrote the majority of the problems in this contest, with some additional help from GlebsHP.
I would like to thank GlebsHP for all his help with coordinating this round, MikeMirzayanov for polygon, and of course, everyone who took the time to test this round.
See you in the competition soon!
Editorial here: http://mirror.codeforces.com/blog/entry/58135
Is it rated for div.1 or div.2?
And where is it in the Contest list?
switch to russian version dude
This is not a Codeforces competition. https://contest.yandex.com/algorithm2018/
Where is it in the contest list? I want to join the contest.
If you haven't participated in qualifying or warming-up contests, you can't join the first round. Otherwise, go to the link in the comment above
10 am MSK on Saturday? Kinda strange timing if you aim for russian participants.
Why? Because of Friday night drinking? That's only in the West. (In Russia, it's every night drinking.)
In Soviet Russia Friday night drinks you.
10AM on weekend? Seems completely fine.
Saturday might be not a weekend for some students
Seriously? Who has courses on Saturday? Even if there are such cases I believe this is a rare case? Either way, there are many contests between Monday and Friday and I assume all students have courses these days :)
i had classes on Saturday while i was at school
In Russia it is quite common to have classes on Saturday for both high school and university students
Huh, didn't expect it. Maybe that's why Russians are so good ;). Do you have six working days or do you have free Monday or are courses on Saturdays "lighter" or "extracurricular" in some sense?
In high school there are long summer holidays (3 months)
In Moscow State University we had some random week day marked for “self-studying” (basically day off)
In the ruleset it states that if two participants have the same score they will be compared with their lowest rank in the three contests.
Does that mean that if I miss a contest I automatically get a lower position than someone who has the same score but participated in all three contests?
Duh, "lowest" is always confusing when talking about standings. It can be the case that lowest means better and that seems to be more probable case.
If I can't participate Round 1 at the exact time mentioned above, does it mean that I'm not able to participate in the contest?
How will top 256 participants be decided(for t-shirts)? GP 30 scores are 0 for >30 rank. So will it just be about lowest rank in three contests?
How to solve B ?
Generate all permutations for mapping [a,j] to [0,9] and see how many of them satisfy the constraint of having a..j as a subsequence. next_permutation in C++ Standard Library can come in handy
Brute Force...consider all 10! arrangements of 0123456789..
in any arrangement A[i] corresponds to ith alphabet...
for every arrangement if sub sequence exists or not can be checked in O(string_length)
overall complexity is ((10!)*string_length)
Is C of elimination round usually this hard? And is sqrt-decomposition required for this problem?
I solved it with sqrt dec, also swap(c,d);
What was the main idea? Partitioning nodes into heavy and light nodes based on whether their degree is > sqrt(m). Then doing manual updates for the light ones and storing the updates for heavy ones and later adding the stored value for heavy neighbors?
What does swap(c, d) mean?
PS: Can I see your source code for this problem?
Possibly that the setter should have set problem C as the present problem D and vice versa.
any hints for D, I know that the stamp must be concatenation between prefix and suffix, but how to check if a certain stamp is valid?
No only prefixes and Suffixes For example aabbaa abba is valid abba.. 1st position ababba 3rd position aabbaa 2nd position
vi=0 in problem C :)
How to solve E?
Build graph with vertexes(index, changed = 0/1), and edges (k_min, k_max), find path of length n.
tourist nails it again!! as usual :p
what complexity in D?
The editorial is up. The author has allowed O(n4) to pass.
I have O(N3), but I wrote O(N4) first and didn't find tests where it would be slow. Stamps were either too easy or too hard to cover the string with.
To everybody with ~10 bombs on E who still wonders "why isn't it passing?!": there was a missable condition in statement, that you can choose K lower than some numbers from the input, but then you just cannot flip them ;_;
I got WA9 because of n = 1 :(
40 seconds after the contest end got O(n^2) solution passed in 60ms.
Where can I see problems if I didn't register?
Where can I find problems if i did not participate?
http://mirror.codeforces.com/gym/101745