UPD2: Standings: http://opentrains.mipt.ru/~ejudge/showres.cgi?data=resExt
http://opentrains.mipt.ru/~ejudge/showres.cgi?data=resExt2
UPD: registration deadline extended to April 25 23:59 (Moscow).
On April 26, 2020 at 10 AM (Moscow) join the international competitive programming e-championship RuCode Festival.
Rucode Festival is a great opportunity to prove yourself and get experience in programming competitions. The Championship will be held in two different levels of complexity: for A/B divisions and for C/D divisions. The tasks will be in English and in Russian.
To take part please register until April 22, 23:59 (Moscow)
The Championship Schedule:
Opening: 10:00 — 10:30
Trial round: 10:30 — 11:00
Contest: 11:00 — 16:00
Contest analysis: 17:00 — 19:00
The tasks are made by the leading Russian universities professors, champions of international competitions and coaches of Moscow Workshops — snarknews, 300iq, veschii_nevstrui, DPR-pavlin, I_love_myself.
RuCode Festival is held by MIPT, Yandex, MegaFon and supported by Phystech Schools Development Fund, Presidential Grants Fund и Analytical Center for the Government of the Russian Federation.
See you at the RuCode e-Championship!
Yuppi! It will be good for quarantine.
The web site is not fully translated and it gives me anxiety
we are working on it, thx
Select Language as Russian and then in google chrome you get notify automatically to convert into English, Click On Always Convert Russian and then you get whole site converted into English. Enjoy Buddy, Happy Coding :)
enjoy русский)
can everyone register?
yes!
yah, that's good
Could you provide some more details about the contest? Will it be individual contest? Will problems be of ACM-type (full feedback and AC/no AC)? How many problems will be there? Are there some prizes? What are these weird letters A/B/C/D denoting divisions?
This is what you need: https://rucode.net/?lang=en
I read through that page and I didn't see the answer to any of Swistakk's questions...
Division A/B will be an ICPC contest from me, same as GP of Moscow on 26th of April.
So, it means that it's a team competition, right? At least I hope so.
Ahh, ok, I planned participating in that GP anyway :)
it will be team contest (3 people), but in current situation there is possible individual participation or 2 persons in one team
it will be classical ACM-type contest
8-13 as usual :)
announcement will follow
Division A is designed to prepare students to participate and win medals in the ICPC World Finals. Division B is designed to help teams prepare for regional and international competitions. Division C/D is for beginners in competitive programming. The list of the topics in each division will be posted on the web-site a bit later.
Difficulty of the contest matches level of the division.
когда должно прийти письмо, по добавлению команды?
But real question is
Is It Rated ?
I don't have a middle name , what to fill while registration (Its mandatory) ??
you could leave it empty or enter -
I did both, but its not working still it requires middle name box
We will fix it, sorry.
Why don't you add more contests for this quarantine? like daily or in alternate days.
yeah that would be very helpful
Can someone not from Russia participate in this contest?
If tasks are not only in Russian, I guess so.
Of course. The tasks will be in English as well.
Great opportunity for great people
Will it be held on Codeforces?
Wondering the same
As of now it is not going to be on codeforces, but it will be a part of Opencup.
That should've been mentioned right at the start of the announcement, it would answer a lot of questions.
You're announcing a team competition without even saying that it's for teams? Come on... Just say next time that this is a public opencup contest.
On the bright side, I appreciate the detailed description of "the team" on your website. I never know if I should participate in a contest if I don't know the exact title of author's PhD thesis.
During the contest, the website is taking a hell of a time. And sometimes a contest is not running yet website won't open
How can I register my team and connect opencup account with RuCode?
Will editorials be published after contest?
will it be rated?
Should every team be limited to a single computer?
Edit: detailed answer.
no, each team can have 3 computers, but log in with one team-account
I believe each team is supposed to use only one computer in every moment.
Is there any language restrictions?
do you mean programming languages?))
yeah
You could choose one from the list: C/C++, Java, Kotlin, Python
Will i be able to indicate my team after 22 April if every member of my team registered?
yes
The contest website and some comments below indicate that this a team contest(Team of 3). But I can't find any option to form/register as a team? I've already registered on the site individually. What steps should I further follow?
I have a few questions:
Each should have an account
Wait until you get the email (April 22), there you will enter the name of the team and team members
Thank you!
To be honest, I am deeply confused about this whole announcement. We already learnt that this competition is just another OpenCup even though it is not indicated in any way in original announcement which doesn't even say that it is team competition (that alone is kinda asburd to me). Why is it given some different name in that case? Why do you tell people to register on that site even though, as far as I understand, we should compete in it as in any other OpenCup through our dedicated Yandex account? What is that website for in that case? OpenCup accounts are not easily created. Does that site let you compete in that particular OpenCup through it for people that are not usual OpenCup competitors? And one more very important question — why do you say here: https://codeforces.net/blog/entry/76187?#comment-607605 that we are allowed to use 3 computers even though on OpenCup people are allowed to use only one?
It is not only the Opencup tour — people can win prizes in Rucode, get diplomas, join stream (in Russian). A team can join only Opencup, but then the results will not be counted in Rucode.
Not everybody is able to participate in Opencup. There were thousands of new students involved in educational part of Rucode — for them this competition is a part of Rucode.
Regarding 3 computers — the rules are standard; a team is allowed to use 3 computers (which is more than ok regarding the pandemic situation), but at most one participant should be coding, compiling, testing or submitting a solution simultaneously. This is exactly the same as for OpenCup. We believe that everybody will follow these rules :)
We were planning to participate in OpenCup only, so we didn't register for RuCode. Currently entering through the OpenCup website only gets us "Not Found". So is it not possible to participate via OpenCup after all? Is there any way for us to submit our solutions?
OpenCup round starts at 11:15.
What is the Ejudge testing system where the contest will be held?
Like, till when we would get the Mail for Team Registration?
Div A and B are different or same.coders selecting A/B will be given same set of problems or it is like div 1/2 on codeforces.
Yes, Div A/B are the same. They don't match with codeforces div 1/2.
So. what is the difference between A and B? Different scoreboards or what?
This time the statements of my problems will be short!
How to give the trial contest. When I log in, I can't see any problems right now!
My team is participating in Div C/D. In the contest it was written that tomorrow's contest is a qualifying round for attending interactive courses on AI and cp. Can you specify how many teams will be shortlisted to attend those courses from all the divisions?
My team are experiencing lag and slow connection during trial contest, sometimes we can't connect to the webpage at all. Are we the only one who experience this? And will it get better when the round starts?
We have got the same thing...
Same here :/
Yes of course. The same here.
Trial was low, hope that now it is better
Unable to submit. It shows clients suspended.
Why is it showing "CLIENTS SUSPENDED" in submit and other options ?? We are unable to submit the code..
Programme is compiling for about 20 minutes, that is unbelievable...
Yeah Same :(
You guys took more than one hour to update team status on dashboard ..We(My team) decided to participate individually because there was no sign of team or team name anywhere ...And after 1 hour (+ 30 min trail round) team status got updated with this message "Client Suspended"
Compiling since half an hour. I expected the platform to be better than this :(
I think now we should appreciate the Codeforces platform. It works perfectly. Thanks to Mike.
They could have used CF platform instead. It would have been much better.
How to solve G?
For each vertex choose some 14-bit hash. For each edge $$$(v, u)$$$ if there is a bit $$$i$$$ that is $$$0$$$ in $$$hash(v)$$$ and $$$1$$$ in $$$hash(u)$$$, color it in the $$$i$$$-th color. It doesn't work when you have some $$$v$$$ and $$$u$$$ such that $$$hash(v) | hash(u) = hash(v)$$$. If you choose as hashes numbers with popcount equal to $$$7$$$, this will never happen. Luckily $$${14}\choose{7}$$$ is greater than $$$3000$$$.
Do you randomize which vertex gets which hash? And what if an edge has multiple bits that have this condition? Do you choose the smallest i?
No, no random required. And you can choose any $$$i$$$. It's correct because if vertex $$$v$$$ has outgoing edge of color $$$i$$$, then its $$$i$$$-th bit has to be $$$0$$$, and if it has incoming edge of color $$$i$$$, then $$$i$$$-th bit has to be $$$1$$$.
I was thinking about this problem for some time and once I rephrased the condition in the following way, it took me zero seconds to complete the solution. Condition means that set of colors ingoing to vertex must be disjoint from set of colors outgoing from vertex, so we can think one is the complement of the other and choose appropriate subsets. Easy to verify we can put all of them to be different 7-elements subsets.
Nice! I think you might be underestimating the difficulty after looking at the inset and outset. We thought of that as well for a while but nothing clicked. I guess it might be one of those problems that is hard for me to visualize in my head.
In hindsight, you're right. This solution might be broken down into these two pieces and it is indeed true that rephrasing that condition took me something like 20 minutes and then it was immediate to me, but in hindsight this sounds weird, first part is kind of obvious and natural and second one is kinda tricky, I can't really explain why did it go like this for me :P.
G is also similar (or same) to this USA TST problem.
I'd go with similar; dividing vertices into two halves is a much simpler idea than taking 14-bit hashes with popcount 7. (In fact, I tried the dividing idea for much of the contest, but it is not good enough here as it uses too many colors.)
I feel like B and G were the hardest problems of the contest. How to solve B?
I tried to greedly put '(' while there was still a solution.
If there is a solution it means that
emptypref[i] + sumpref[i] >= 0
andemptysuf[i] - sumpref[i] >= 0
for all i from 1 to 2n.sumpref[i]
= sum in range[1,i] if we denote '(' as 1 and ')' as -1 from the parenthese sthat we already greedly put.emptypref[i]
= how many positions in which we can still put parentheses in range [1,i]emptysuf[i]
= the same for suffixesI kept two segment trees where I could update a range and query min on intervals one for preffix and one for suffix. If the min of one the segment tree was < 0. Than I try to use a ')'. If that's still not good, then there is no solution.
Our team had the same solution, however, the realization is a bit simpler in my opinion. You need just one segment tree.
Can someone proof the correctness of this idea, because we didn't try during the contest, just submit xD
code
I think I have a simpler solution other than the one in the editorial. First of all make the first distinct $$$N / 2$$$ integers open brackets and the rest closed.
Now iterate over the current string and add $$$+1$$$ if you face an open bracket and $$$-1$$$ if you face a closed one once the value becomes less than $$$0$$$ at index $$$i$$$ it seems optimal that you need to replace one of the open values with second occurrence $$$> i$$$ with one closed with second occurrence $$$\leq i$$$ this way you can add $$$2$$$ to your current value. it seemed optimal to me that you need to replace the open value with largest first occurrence and closed value with smallest first occurrence. I only used some sets to make this solution pass.
I've came up with exactly the same solution during the contest, but discarded it, because when you flip 2 pairs of brackets, you decrease balance on some segment that you already passed by 2 and it may make it negative. Why won't it happen?
Also, when I asked for solution I expected something with proof. And none of the solutions I've seen so far are proven, not even the one in the editorial. :(
It will happen actually so after reconstructing the string you need to make sure that the sequence is a CBS.
Also this might not look like a proof but it made sense to me. First of all it's obvious that at index $$$i$$$ you won't replace an open value with second occurrence $$$< i$$$ since it will not add to the current value. when adding a value from closed set it's also kind of obvious that i need the smallest value with the first occurrence since the value i will remove from the open set will surely be before that so i need to focus on lexicographicality. Now the only problem is why remove an $$$x$$$ with second occurrence $$$y > i$$$ while i can remove an $$$x2$$$ with second occurrence $$$y2 > y$$$ that might help me in the future. I don't have a proof for this part but I thought that I will remove $$$x$$$ first and if i ever come to a negative value again I can then re-revert $$$x$$$ and add $$$x2$$$ if i had passed $$$x$$$'s second occurrence by that time.
Proof of the solution in the editorial (obviously, not invented during the contest) (I hope it's correct):
For simplicity, assume that
(
is equivalent to $$$+1$$$ and)
is equivalent to $$$-1$$$. Now, the following conditions are equivalent:Take an optimal solution $$$s$$$ and assume that the greedy solution identified $$$s_i$$$ incorrectly. Of course, $$$s_i =\, ')'$$$ and greedy must have chosen
(
. We'll construct a new correct bracket sequence $$$s'$$$ with the same prefix and $$$s'_i =\, '('$$$.Assume $$$s_i$$$ is paired with $$$s_j$$$. Obviously, $$$i < j$$$. Just after greedy decided that it wants to put at
(
at the $$$i$$$-th and $$$j$$$-th position, only the pairs of brackets $$$(s_a, s_b)$$$ where $$$i < a < b$$$ are undecided yet. Consider all such pairs where the optimal solution puts(
. There are two cases now:)
, and replace $$$s_i, s_j$$$ with(
. The sum of brackets didn't change, and no suffix sum increased (because $$$a > i$$$, $$$b > j$$$). We just found a better correct bracket sequence.)
, and replace $$$s_i, s_j$$$ with(
. Now each suffix is still non-negative:)
at the $$$i$$$-th and $$$j$$$-th position).In both cases we managed to put
(
at $$$s_i$$$ and $$$s_j$$$, so the greedy was actually right to put it there.How to solve A?
We can define the number of moves a position can give to Alice / Bob: He/she can either move it to another node it owns, either move it to one of the opponent's nodes. However, neither Alice nor Bob will ever move a token to a node of the other color if the other one can move it afterwards (Alice won't move from
a
tob
if Bob can move it after fromb
toc
). This is because it would mean basically spending a move to give the other one at least one move.So we can define
liberty[x] = number of moves from x without giving the opponent the chance to move it
.Now we just have to use the knapsack problem to find a positive difference between the number of moves of Alice and of Bob.
If both have the same number of moves(liberty) who wins? it depends on the next parts of path.
If both have same liberty then the first to move (Alice) loses, since she will run out of moves in her own color and be forced to move tokens into nodes of the other color, giving Bob more moves.
consider paths are like this:
WWBWW
BBWWW
now the Alice wins!
Liberty counts the number max number of W(or B) -1 in a path without BB(or WW). The path can be something like WWBWWBWBWBW...
The -1 removes the last move to the BB/WW.
I thought you had to find the value of all positions ( where the position means a coin placed in a node) using the simplicity rule http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Bartlett.pdf
and then it was just knapsack, how to select a set of numbers such that the sum is greater than 0.
Is it possible to practice the problems after the contest? actually I forgot about it. Though joined half an hour before ending and solved one. I want to practice the rest problems! Is it possible?
How to solve C?
C is a linear programming problem. If you write down dual program, you will need to find $$$y_1, y_2, ..., y_n \geq 0$$$, such that $$$\sum a_i y_i$$$ is minimized and $$$y_i + y_{i+1} \geq 1$$$. There are 2 cases: each $$$y_i = 0.5$$$(this can only happen for odd $$$n$$$), and each $$$y_i$$$ is either $$$0$$$ or $$$1$$$. I don't have strict proof, but the intuition is that it's similar to linear program for max weight matching, so it behaves similarly. The case with $$$y_i = 0, 1$$$ is solved with dynamic programming $$$dp[i][y_0][y_i]$$$.
Proof: There are $$$2n$$$ equations in the LP, $$$y_i + y_{i + 1} \geq 1, y_i \geq 0$$$ for all $$$i$$$.
Since the feasible region is bounded, there must be an optimal extreme point solution, where $$$n$$$ linearly independent equations are satisfied.
If none of these satisfied equations is of the form $$$y_j = 0$$$, then $$$y_i + y_{i+1} = 1$$$ must be true for all $$$i$$$. So the values must be of the form alternating $$$x, 1-x$$$. If $$$n$$$ is odd, the only possible solution is $$$\frac{1}{2}$$$. Else the objective function is (1-x) * (sum at even positions) + x * (sum at odd positions) which is minimized at either $$$0$$$ or $$$1$$$.
Else, if $$$y_i = 0$$$, then $$$y_{i-1}$$$ and $$$y_{i+1}$$$ must be $$$1$$$. So, first remove all edges with values known to be alternating $$$0, 1$$$. Now we are left with line segments with no constraints on the sum of ends.
Now, the LP for a line segment can be proved to have an integral optimum solution. Basically, in an extreme point solution, for atleast one edge, $$$y_i = 0$$$ must be satisfied (as we have $$$2n - 1$$$ inequations in the LP now). So, we use induction after removing this edge and its adjacent edges(with value $$$1$$$).
After dualizing the linear program, you get that you need to minimize sum of $$$s_i y_i$$$ such that $$$y_i \geq 0$$$ and $$$y_i + y_{i+1} \geq 1$$$. Turns out that the solution is to either put $$$y_i = 0.5$$$ for all $$$i$$$ or $$$y_i \in { 0, 1 }$$$. We have a rough idea why that is, but we didn’t formally prove during the contest. To optimize the second case, you just do a simple dynamic programming that remembers whether or not the first and the last elements have value $$$1$$$.
Edit: basically, what aid said above.
How to solve F?
We sorted the edges decreasingly by c. Each edge now connects two components. At this point, you should greedily alternate between these two components as much as possible. After you do that, you recurse into the larger of the two subtrees, delete the rest, and re-iterate the process for the edges in that larger component (where you have some nodes that are already connected, for which you keep a "lazy" value). You can do this whole process in O(n) (after sorting) if you compute the smaller of the two components by doing parallel bfs from both ends of the edge.
I think our solution works for arbitrary weights. Not sure why the weights were powers of two.
https://pastebin.com/SGcT5CJ3 (code might explain better)
Easier solutions may exist. I am interested in them.
how to solve J(div C+D)? i tried to do something with lca ans set with tin[v] comparator but it didnt work https://pastebin.com/u40S9zmM
to the rescue in the last minute in E and it worked xD
How to solve I? I tried to use network flow with O(nlog) edges, there are some edges with capacity = 1, but get TLE on test 5.
Model solution finds a lexicographically smallest maximum matching (smallest w.r.t query insertion time) in $$$O(n \log^2 n)$$$, using some divide and conquer based on Konig's theorem.
How to solve if network flow can be computed in linear time (assuming all capacity 1 or infinity)?
The naive method with network flow is to add edge and run flow again for each day? But I think we don't need to run flow for each day, just need to run for the last day. We will find augmenting path in order of edges added to flow network, which is order of days. So we will move back from last day to first day and decrease the answer when there is an respective augmenting path.
P.S: I'm not sure about the correctness of this solution. I just feel that it may be true. My code that gets TLE is here. Can anyone please confirm its correctness? Some testcases that make my code WA would be great. Thanks in advance.
D, anybody?
Editorial will be published soon. Key idea: solve queries offline and use segment tree beats.
Fun fact about D: Problem name was ko_osaga-type problem until yesterday.
( div c/d )H:How to arrange integer. How to solve it? I added directed edge from a to b if a divides b then answered number of strongly connected components but got WA.
It was pointed out by my teammate shiv1470 that for a case like:
The answer was 2 rather than 1, as we can number node 1 as 1 and node 2 as -1. So, the final was to find the number of SCC, and then 2*(number of components with size > 1) + (number of components with size = 1).
Thank you all for participating! All problems in Div A/B were created and prepared by me, with a huge help of testers ko_osaga, caoash, jqdai0815, Endagorion, rushcheyo, chenjb, ainta, xiaowuc1, Subconscious, Roundgod, Rewinding, xtqqwq, WZYYN, Rebelz, VivaciousAubergine, never_giveup, Elegia, Hazyknight, gamegame.
You can find the editorial (not the final version) here.
Could you please post the editorial for Div C/D as well?
Is there a link which can be publicly used to upsolve the contest? The link in the blog and website is for registered participants only.