Hello!
ICPC Southern and Volga Russian Regional Contest (Northern Eurasia) 2019 has ended on October 15. There were 76 teams onsite in Saratov, most of them were invited because of their result on the qualification stage.
On Oct/27/2019 12:35 (Moscow time) will start onlinemirror 20192020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred).
In this contest I play a role of Cheif Judge and the jury teams consists of exparticipants of ICPC from Saratov and jury members from other cities. Many thanks to all of them! I hope you will like the problems!
I invite ICPC teams and individual participants of Codeforces competitions to take part! Sure, the contest will be unrated.
is this rated for div3?
"Sure, the contest will be unrated."
Thank you for your efforts. Good luck to everyone!
how to solve E?
It's kind of 2SAT.
Let's iterate over all pairs of necklaces. For each pair $$$p$$$ and $$$q$$$, look at the similarities of $$$p, q$$$ and $$$p, rev(q)$$$. If this pair can only exist when both are in the same direction, draw a white edge between them; if this pair can only exist when one of them is reversed, draw a black edge between them; if this pair can't exist either way, report a failure. After this reduction it is fairly similar to e.g. 553C  Любовные треугольники.
We want to split the resulting graph into two parts $$$S$$$ and $$$T$$$, such that there are only black edges between $$$S$$$ and $$$T$$$, and only white edges within $$$S$$$ and $$$T$$$; also, we want to minimize the size of $$$T$$$ (i.e. the number of reversed necklaces). First check if there is a cycle with odd number of black edges, if there is, report a failure. Otherwise, we have a bunch of "bipartite" connected components. Put the smaller half of each component into $$$T$$$ and we have our answer.
E had very odd bounds as it can be solved in quadratic time.
For every pair of necklaces, we either get that
If 4 happens even once, answer impossible. Now knowing the orientation of one necklace in a connected component (with conditions as edges) determines the orientations of the rest. Just take the orientation that minimises flipped necklaces.
Isn't it still O(N^2*M) for constructing the graph? For every pair of strings you need to iterate over them to count the similarity. After that it's just the coloring described by you. Is there a way of making the graph in a better complexity?
You can compare the pairs of strings by simply taking their xor. If you store them as bitmasks, the comparison takes, in some sense, $$$O(1)$$$ time. I assume this is what he means.
Thanks! I figured it out eventually. I find the bounds kind of odd now too.
oh I'll check it. Thank you so much isthisfft mango_lassi
How to approach B?
you need at least k/2 buses and at most k buses since k<=8000 iterate on each k to find the optimal one
Only elaborating this approach, since I find the problem quite interesting.
Suppose we have the counts of all teams in a nondescending/sorted order. An important observation is that in an optimal solution, the teams that go alone in the bus forms a suffix. This can be proven with an exchange argument. Now, what is the best way to pair up teams in a prefix? We want to pair up teams so that the maximum sum of counts is minimised. Consider the largest team in the prefix. It is best to pair it up with the smallest team (again, can prove with an exchange argument). So we remove the first and last of the prefix and repeat the procedure.
Finally, we iterate on each prefix of even length (say $$$2i$$$) — obtain the maximum of the remaining suffix, and obtain the maximum sum of pairs of elements that are equally distant from the beginning and end of the prefix. Here, $$$s$$$ is the maximum of the two, and $$$r$$$ is $$$i + (n  2i)$$$. And for all such $$$i$$$, we take the minimum of $$$s\cdot r$$$.
Can you provide a link to the code? Thanks for the help.
Sure. https://pastebin.com/TUVADMmu
What is test case 2 in J ?
there were a lot of test cases
Thanks, test cases are visible now

Can anyone help me in explaining how to solve problem N (Wires) ? My solution is failing for testcase 7 :( Not able to figure it out
You delete a bridge.
I thought that I am already taking care of that. Looks like I am having a big or something. Thanks for that :)
Iterate over components, run dfs.
Then you can always delete the last vertex in dfs (Try to think why it is true). So connect any vertex from next component with parent of last vertex.
You don't need to find bridges or something like this.
Could you hack my solution?
I add all the edges to connect the point, which is relabeled,using dsu and keep the sum of edge for each point.
I check all the edges,if its Unicom block haven't been visit and one of its end is size of 1,I push it and its sizeone point to a stack.
If there is still some Unicom blocks haven't been visit, which means it's a circle.I got any of a edge with one of its point.
I connect the 2~n element in the stack to element 1.
I also WA on test 7.I have test many case and submit 10 times.
I wonder whether my solution bugged or the SPJ bugged.
below is my two tries https://codeforces.com/contest/1250/submission/63558169 https://codeforces.com/contest/1250/submission/63621689
Thanks a lot.
oh yeah! I am using algorithm to find all articulation bridges and made it complex. I see why choosing last node of the simple DFS works. I ll keep that in mind. Thanks for that :)
Edit: Removing the code to find articulation bridges and just using last edge of DFS gave me an AC :)
Hi dude, can you explain me why your greedy approach is correct?
Never mind, I just realized that!
According to the contests tab, it is "open hacking phase" now? Is there any actual hacking that can be done now? I.e. is there a reasonable chance that the test set (which was probably the same at the subregional) is not complete?
Should we wait for editorial or not?
How to solve problem C?
For C, What I did was, start by sorting queries by their r value. then i created a segment tree which tells the maximum possible answer with some l value for fixed r. segment tree was range update and point maximum query segment tree which also tells the index of maximum. now the main problem was how to store answer in segment tree so for fixed right index =x the index x would have k + sum of segments which lie in (x1,x) and index x1 would have 2*k + sum of segments which lie in(x2,x) and so on. we can do this possible by iterating over r and updating the range (1,r) with k everytime.
Heres my code https://www.ideone.com/g2j16q
https://pastebin.com/UNyjNnuu
Here hope this helps
Key observation is that to reach row_index rb from ra all the elements lying between will be of same type(if element at ra is even then all elements will be even and vice versa)..same thing applies for column too... I am limited by my formatting skills otherwise I could have explained better
I think you posted this in the wrong announcement.
Oops...nvm thanks for pointing it out
How to solve problem N:Wires?
If the number of connected components in the graph is $$$c$$$, then the answer is $$$c1$$$.
Just connect all the other components to the first component. To join the component:
1) If it is a tree, change any leafvertex's edge
2) otherwise, change any edge that belongs to a cycle
I was also trying to do this....but I couldn't hand the case
3
1 2
3 4
5 6
My code was connecting 1 with 3 or 4 which resulted in 2 becoming isolated.. How can I handle this situation
Vertices can be isolated.
We just need to make sure the edges are connected.
Oww!!!!of course...I guess I was overthinking after getting WA on test case 6...I was thinking about the vertices being isolated [Even sample case does that :]....
UPD : Got it!! I wasn't considering multiple edges between two nodes
If the component is not a tree then if I change either any leaf node edge or cycle node edge, then will there be any problem
63618975 Here I am trying to do that , but getting WA
How to solve D, I, M?
I: my solution was the weirdest solution I've ever came up with
First to make it simpler we'll take the complement of the set, so we'll order by lesser size and greater sum and the restriction goes from SET <= K to SUM — SET >= K.
Now, let's try and get TLE with a bruteforce solution like bf(i, remaining that need to be taken, current sum) + ordering the values before bruteforce.
Here comes the trick, if we compress a tree to not have any internal nodes with degree 2 then it has O(N) leafs and O(N) nodes, using this fact we can compress the segments that we don't have a choice but to choose the values by using a binary search to remove that segment.
This isn't enough since it might have values mixed in that are smaller than what should be the last value, so we do a binary search to find the largest value that doesn't use all M things and then do a special iteration to get some value that's exactly what the last should be.
Complexity is something like O(N * logN * logV) or something like that lol.
Alternative solution for I:
Let's suppose we fix $$$K$$$ as the number of people in the subset $$$S$$$ and the people are sorted in increasing order of awkwardness.
Obviously, the first set that we should output is $$$v_1, ..., v_K$$$. The main idea is how to transition from this set to potentially other sets while iterating through them in order of total awkwardness.
It turns out that we can do that by two operations. Consider a pointer that initially points to $$$K$$$ and represents to the position of the $$$K$$$th person in the set. We now consider two operations:  increase the position of the pointer by $$$1$$$  fix the position of the pointer and grab a pointer to the previous person in the set.
Basically, for set $$$1, 3, 5$$$ we can do these operations: $$$1, 2, 3 \rightarrow 1, 2, 4 \rightarrow 1, 2, 5 \rightarrow 1, 3, 5$$$.
Essentially, we start increasing the second pointer only when we fixed the value for the first pointer.
Two aspects here are essential: that the sequence of operations is unique for a given target set (we don't end up at a target set in two different ways), and that the intermediary sets are of increasing total awkwardness (the cost of transitioning is always positive).
Therefore, the state space with these two operations is actually a rooted tree, and edges are always of positive weight. In fact, all edge costs are of form $$$v_{i + 1}  v_i$$$. That means that we can traverse the tree in order by simulating Dijkstra algorithm on this search tree.
In order to reach the good complexity, we need to keep for each node in the tree a state of form: (maximum remaining sum, where current pointer points to, where is the fixed element to its right, how many elements are before it). Then we can transition from a state $$$(s, pos, npos, idx)$$$ to $$$(s  v_{pos+1} + v_{pos}, pos + 1, npos, idx)$$$ if $$$pos + 1 < npos$$$ (incrementing) or $$$(s  v_{idx + 1} + v_{idx}, idx, pos, idx  1)$$$ if $$$idx > 0$$$ (fixing + incrementing). Each state determines the values $$$ptr_0 = 0, ptr_1 = 1, ..., ptr_{idx  1} = idx  1, ptr_{idx} = pos$$$, and the positions greater than $$$idx$$$ are determined by its path in the search tree.
The rest is just reconstruction bonanza.
Total complexity is $$$O(k \log{k})$$$.
Solution
How to solve D?
Thank you but the solution can't be viewed.
Fixed.
solution of D:
First we can imagine all the persons as 2dimensional point $$$(L,R)$$$ with color $$$c$$$. If a person who located at $$$(x,y)$$$ is unhappy, then all person who located in the upperleft of $$$(y,x)$$$ should be in the same color(think about when two intervals don't intersect). So you can enumerate all the persons and see:if he is unhappy, what the color will be in the upperleft rectangle or we don't know the color yet.
we change the problem to this:give some points with color(or don't have any color yet),and some upperleft rectangles with color(or don't have any color yet). you should choose rectangles as many as possible and make sure:
1.give colors to all rectangles and points which don't have colors yet.
2.all points in a chosen rectangle should have the same color with the rectangle.
we can run a dp in $$$O(n^2k)$$$. for the first step,sort all rectangles according to its right boundary(from right to left).then define $$$dp[i][j][k]$$$ as "after considering the first $$$i$$$ rectangles, all useful points whose ycoordinate is larger than $$$j$$$ are already colored the $$$kth$$$ color,how many rectangles you can choose at most?".
some explanation about it:
1.after discretization, there are only $$$O(n)$$$ ycoordinates;
2.definition of useful points:you can imagine all the chosen rectangles, the figure of them is something like “stairs”. Obiviously only the points in the left of the leftmost stair are useful(because the rectangles are sorted).
there are more details:
1.precalculate the color/number of points in all rectangles(I use bitset)
2.color the rectangle. and in the process of dp you need the information precalculated in the first step.
the dp details are a little bit complicated but easy to think.
At first I'm afraid this solution is not efficient enough, but after coding carefully, my solution runs in only $$$140ms$$$
How to solve K? qwq
Suppose that we fix a way of distributing the ordinary projectors to seminars. Then there's a way to distribute the HD projectors iff for any integer $$$t,$$$ the time $$$t+0.5$$$ is not contained within more than $$$x$$$ intervals corresponding to seminars or lectures which do not already have a projector. (condition 1)
It follows that we don't actually care about the exact intervals spanned by lectures. For example, $$$[1,4), [2,3)$$$ is indistinguishable from $$$[1,2),[2,3),[3,4),[2,3)$$$ or $$$[1,3),[2,4).$$$ Thus, we want to create some sort of flow graph with the seminars (not the lectures) as edges.
The way of distributing the ordinary projectors must satisfy the following condition: Suppose that at time $$$t+0.5,$$$ exactly $$$X$$$ lectures and $$$Y$$$ seminars are happening. Then $$$X\le x, X+Y\le x+y,$$$ and at most $$$\min(y,x+yXY)$$$ ordinary projectors are not being used at time $$$t+0.5$$$. (condition 2)
Now let's construct a graph for the ordinary projectors. Create a vertex for each (compressed) time in increasing order from left to right. The source (left of all other vertices) has an edge to the first time and the last time has an edge to the sink (right of all other vertices). There will be edges for each seminar with capacity one and edges between every two adjacent times with capacities determined by (condition 2). All edges are directed from left to right. Then there will exist a distribution satisfying (condition 2) iff the max flow from the source to the sink is equal to $$$y.$$$
If (condition 2) is satisfied, then (condition 1) will be satisfied as well, so after distributing the ordinary projectors we can distribute the HD projectors greedily. (Nice problem!)
Code
I have another interesting solution for D.
First we can sort all persons by $$$r$$$ (departure time) in increasing order. For the $$$i$$$th persion, consider who he will meet during the conference. We can define it as a set. $$$S(i)$$$ means the set of persons that the $$$i$$$th persion will meet. For simplicity, we let $$$i \in S(i)$$$.
According to the colors, there are 4 types of sets.
When $$$S(i)$$$ is type 1, person $$$i$$$ is impossibe to be upset. When $$$S(i)$$$ is type 2, person $$$i$$$ must be upset.
So we can preprocess these two types of sets and ignore them in the following solution.
So the problem can be changed to this: we can select some sets (to make the corresponding persons upset), and assign a color to each set (For set of type 3, we can only assign the existing color). And this assignment is valid if and only if it doesn't exist that two sets are assigned different color but intersect with each other.
Since $$$r$$$ (departure time) for everyone is increasing, we can describe $$$S(i)$$$ in a simple way. We can define $$$p(i)$$$ as the smallest $$$x$$$ that satisifies $$$r_x \geq l_i$$$.
Then for all $$$p(i) \leq x \leq i, x \in S(i)$$$. And for those $$$x$$$ greater than $$$i$$$, $$$x \in S(i)$$$ if and only if $$$p(x) \leq i$$$. Hence, $$$S(i)= \{xp(i)\leq x \leq i \vee p(x) \leq i \}$$$
$$$S(i)$$$ consists of two parts, the first part of which is $$$\{xp(i)\leq x \leq i \}$$$, a consecutive interval; the second part is $$$ \{xx>i,p(x) \leq i \}$$$, which may be some isolated points.
Then we consider when will two sets $$$S(i)$$$ and $$$S(j)$$$ intersect. Suppose $$$i < j$$$, there are 3 types of intersection.
(It is impossible that the first part of $$$S(i)$$$ intersects with the second part of $$$S(j)$$$ since $$$i < j$$$.)
We can combine the conditions for the second and third types of intersection to $$$\exists x, x \geq p(j)\wedge p(x) \leq i$$$. We can define $$${\rm minp}(i)=\min_{x\geq i}p(x)$$$. Then this condition can be rewrited as $$${\rm minp}(p(j))\leq i$$$.
Next, we can define $$$f(i) = \min(p(i), {\rm minp}(p(i)))$$$. Then $$$S(j)$$$ intersects with $$$S(i)$$$($$$i < j)$$$ if and only if $$$f(j) \leq i$$$.
This is an elegant conclusion. After we get it, we can work out a dp solution. Define $$$dp(i)$$$ as the maximum number of unhappy persons when we only consider the first $$$i$$$ persons.
After calculating $$$dp(i1)$$$, how to get the value of $$$dp(i)$$$? First, we set $$$dp(i) = dp(i1)$$$, then consider the maximum number of persons upset if we make person $$$i$$$ upset. We can enumerate the color $$$j$$$ assigned to $$$S(i)$$$, and then enumerate $$$k(0\leq k < p(i))$$$, which means the sets among $$$S(x)( k<x\leq i)$$$ that are selected will be only assigned color $$$j$$$, and the sets among $$$S(x)(x\leq k)$$$ are free to select.
Which sets among $$$S(x)(k<x\leq i)$$$ can be selected in this case? Those sets can not intersects with the sets $$$S(y)(y\leq k)$$$. So the condition is $$$p(x) > k$$$ and the color of $$$S(x)$$$ is $$$j$$$ or 0. We can use Binary Indexed Tree to maintain the amounts.
This editorial is so long and I have written it for a long time because I'm not so good at English. But this approach is very easy to implement. I finished the code within 20 minutes.
The time complexity is $$$O(n^2 k\log (n))$$$, where $$$k$$$ is the number of total colors. In the problem, $$$k=200$$$. Since we shouldn't enumerate all colors when $$$S(i)$$$ is type 3 (have a specific color), the complexity is far from reaching the upper bound. My solution runs in $$$93ms$$$.
Here is my code.
solution
For the reason that the number of add operation is $$$n$$$, so with prefix sum, the time complexity is $$$O(n^2k)$$$.
M is nice.
For each bit $$$i$$$, let L = set of indices $$$x$$$ with bit $$$i = 0$$$, R = set of indices $$$y$$$ with bit $$$i = 1$$$ and $$$y + 1$$$ also has bit $$$i = 1$$$.
Similarly, for each bit $$$i$$$, let L = set of indices $$$x$$$ with bit $$$i = 1$$$, R = set of indices $$$y$$$ with bit $$$i = 1$$$ and $$$y + 1$$$ also has bit $$$i = 0$$$.
Now, we used 26 sets.
Observe that only pairs $$$(x, y)$$$, with y = 01111...1 (the string of 1s is nonempty) and x = 1 such that there is at least one bit 1 in the suffix, are uncovered.
Thus, it is sufficient to make $$$12$$$ more queries that cover all y of the form 0111...1 for a fixed 1suffix length and then put all x that can be matched on the left hand side.
In total, my solution uses $$$38$$$ queries.
Can you please provide your implimentation if you have it.
ps. Thank you zscoder. It's a nice solution.
Thank you very much.
Hi can you elaborate on the solution. I'm finding it difficult to understand the notations you have used in your explanation. Thanks
Simpler solution for I:
Sort all values. We loop through the number of elements from N to 1. Let's say now we are considering the ways to choose k elements. Start with the smallest k elements. We build our solutions progressively using 2 types of steps: Consider a pointer starting at the largest element. Each step consists of either increasing the current element to the next possible element, or move the pointer lefft and increase the current element to the next possible element. We can push the current sum, current position of pointer, position of previous element, position of current element into a priority queue to simulate this expansion. To restore the solution, just create an ID for each state and keep track of which move is used to reach the current state, and we can backtrack at the end.
Complexity: $$$O(M\log M)$$$
MikeMirzayanov codes are still not visible, will it be fixed or it will remain like this ?
In fact, codes of a problem in this contest will be visible after you solve it.
For me visible are codes of problems which I solved. If you see codes of all problems maybe it is because of coach mode.
It's the same to me. I can't see the solutions of problems I haven't upsolved. If you want to find a solution of a problem in this contest, you can search tutorial in this blog. Other users may have posted their own solutions. If the tutorial of the problem is not posted, you can ask about it. I will try to help you.
Thanks, can you tell the solution of C and N.In N I came up what is the main idea, but I don't know how to implement it easily.
Does this competition have any influence on ratings?
of course not
Thanks a lot.
Is there any solutions to these problems ？ Officially or unofficially.
Can anyone provide a link to there submission for problem B and J. Thanks
in J you should binary search the amount of soldiers in one row. in B you should sort teams by size and consider you put 1st and last together, then 2nd and last1 ans so on for each capacity you must check amount of rides and minimal capacity*number of rides among them will be the answer
can u provide link to your solution.. Thanks for replying..
J B
Thanks for providing the solutions, it help me a lot...
Please write the blog for editorial, it will help in upsolveing the problem. Thanks
Can you please make all sources visible?
How to solve G?
Enumerate on the position of last Reset operation, then we can use binary search to determine if this is possible. Also we need to know at least how many Reset operations we need to do before this one, which can be preprocessed using dynamic programming. The transition can be done using either binary search or two pointers. Time complexity should be $$$O(n\log{n})$$$.
Can you explain your approach in more details?
How to solve L ?
Just find the answer with a binary search.
We can assume that $$$a \geq c$$$ because they are symmetric, then for an answer $$$k$$$ wee need to check whether we can satisfy the condition.
Suppose we have all $$$a$$$ in set $$$A$$$, $$$b$$$ in set $$$B$$$ and $$$c$$$ in set $$$C$$$, then we need to adjust it.
If $$$a \leq k$$$, obviously $$$c \leq a \leq k$$$, we only need to check if we can put some person b to $$$A$$$ or $$$C$$$.
If $$$a \geq c > k$$$, we failed, otherwise we put $$$a  k$$$ person a in $$$B$$$, and we can take at most $$$b$$$ person b from $$$B$$$ to $$$C$$$, just to find out whether it is possible.
I am wondering if everything is ok with checker for task I.
During contest I've submitted solution. After contest with some assertions it turned out that test 9 is maxtest ($$$n, m = 10^6, k = 10^{18}, a_i = 10^{12}$$$). So I asserted to check if my answer is correct and I got wa instead of rte.
To check if I haven't made any mistake (in asserts etc) I took accepted code from comments and with diff checked on my laptop that I calculated answer correctly. Now I have no idea what's wrong with my code/output, can someone investigate this (maybe I made a mistake, but I just can't see where)?
You solution prints lines like
999998 999998000000000000
in the bottom of the output.Thank you. Sorry, I made a stupid bug in assertions.
Can anyone provide a solution for L? It will help me a lot... Thanks!
Here it is.
Thanks a lot!
How to solve problem K ?