В Opencup вы и так сможете участвовать, Rucode туда добавится, в чемпионате можно будет получить диплом победителя, призы. Плюс там много параллельных активностей будет: трансляция с комментариями, деловая программа, интервью.

Разве ты не хочешь, чтобы твой e-mail отправили спонсорам?

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

yes!

This is what you need: https://rucode.net/?lang=en

Division A/B will be an ICPC contest from me, same as GP of Moscow on 26th of April.

Will it be individual contest?

it will be team contest (3 people), but in current situation there is possible individual participation or 2 persons in one team

Will problems be of ACM-type (full feedback and AC/no AC)?

it will be classical ACM-type contest

How many problems will be there?

8-13 as usual :)

Are there some prizes?

announcement will follow

What are these weird letters A/B/C/D denoting divisions?

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.

you could leave it empty or enter -

yeah that would be very helpful

If tasks are not only in Russian, I guess so.

Of course. The tasks will be in English as well.

Wondering the same

As of now it is not going to be on codeforces, but it will be a part of Opencup.

У меня возникла абсолютно такая же проблема :)

Мы поправили это, теперь все работает. Извините.

Поправили, извиняемся

no, each team can have 3 computers, but log in with one team-account

do you mean programming languages?))

yes

Must every team member have an account on the website, or only one for the whole team?

Each should have an account

What do we have to do after we have completed the form from the website?

Wait until you get the email (April 22), there you will enter the name of the team and team members

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

Yes, Div A/B are the same. They don't match with codeforces div 1/2.

Заявки на команды принимаем автоматически, список зарегистрированных команд вывесим завтра.

We have got the same thing...

Same here :/

Yes of course. The same here.

Trial was low, hope that now it is better

Yeah Same :(

They could have used CF platform instead. It would have been much better.

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

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.

G is also similar (or same) to this USA TST problem.

I tried to greedly put '(' while there was still a solution.

If there is a solution it means that emptypref[i] + sumpref[i] >= 0 and emptysuf[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 suffixes

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

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.

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:

1. The bracket sequence is "correct".
2. The sum of brackets is $$$0$$$ and each suffix is non-positive.

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:

• There is an opening pair of brackets in the optimal solution: $$$(s_a, s_b)$$$, $$$i < a < b$$$, where $$$b > j$$$. Take any such pair and replace $$$s_a, s_b$$$ with ), 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.
• There is no such pair. Take the opening pair of brackets $$$(s_a, s_b)$$$, $$$i < a < b$$$, with maximum $$$b$$$. (Such a pair must exist or else $$$s$$$ would contain fewer opening brackets than we put in the greedy solution so far.) Notice that $$$i < a < b < j$$$. Again, replace $$$s_a, s_b$$$ with ), and replace $$$s_i, s_j$$$ with (. Now each suffix is still non-negative:
  • suffix sums $$$[p, 2n]$$$ for $$$p \leq b$$$ or $$$p > j$$$ decreased or remained the same,
  • suffix sums $$$[p, 2n]$$$ for $$$p \in (b, j]$$$ increased by $$$1$$$, but are still non-positive (as these are exactly the suffix sums kept in the structure when the greedy decided to put ) 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.

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 to b if Bob can move it after from b to c). 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.

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]$$$.

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.

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.

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

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.

It was pointed out by my teammate shiv1470 that for a case like:

2
1 2
2 1

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

Could you please post the editorial for Div C/D as well?