Hello Codeforces!
The Southern and Volga Russian Regional Contest was held in Saratov State University on 22nd of November. This contest was used to qualify the teams from Southern Russia and Volga region to the Northern Eurasia Finals.
On Nov/27/2022 13:35 (Moscow time), we will conduct the online mirror of this contest. It will last for 5 hours and is best suited for teams of three people, although it is not forbidden to participate in teams of smaller/larger size. The mirror will use ICPC rules, the same as the offline contest.
I would like to express my gratitude to all other jury members: awoo, Neon, vovuh, adedalic, DmitryKlenov, dmitryme, DStepanenko, elena and kuviman. Also, big thanks to the contest testers: IlyaLos, Oleg_Smirnov, ashmelev, pashka, and especially MikeMirzayanov not only for testing the problems, but also for his excellent Polygon system, without which it would be almost impossible to prepare the competition.
As a chief judge of the contest, I hope you enjoy the problems!
Of course, the contest will be unrated.
upd: The editorial can be found here.
Would the Southern and Volga Russia regional consider uploading test data for this year's (and also previous years') contests? The regional page is missing a lot of details.
Unfortunately, I don't have any access to editing that page. I will try to find out who I should contact to upload that information for the current Regional and the 2021-2022 one (I wasn't the chief judge during the earlier seasons, so I also need to consult with the previous chief judge).
As a temporary solution, I can upload the editorials and the tests as the contest files after we conduct the mirror.
Is the contest package uploaded?
Incidentally, what are https://icpc.sgu.ru/ and https://contest.sgu.ru/ used for?
Is $$$\mathcal{\color{red}{Hack}}$$$ available?
How challenging are the problems? Should I attempt to participate if I'm green?
You definitely should
For a lone green participant, the problemset can be very challenging. I advise you to play this contest with a team.
What about a lone blue one?
Much more suitable than for a lone green one, but there will be several problems which are not expected to be solved by anyone who is in the second division.
The problems are very different in terms of difficulty, you will surely find several ones to solve.
excited
As a tester, I think that this is a really good set of problems. It will be of interest to a wide range of participants.
I'll add more. That, as a former chef judge, I highly appreciate the problems and think that the guys did a great job. Kudos!
I think it should be ‘chief judge’ instead of ‘chef judge’ lol
It would be nice to finally fix language selector issue and remove excessive use of flags.
Sources with supporting arguments:
Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.
Please support the initiative and stop reinforcing poor UX practices.
Please use your plugin and don't bother us all.
Is this contes rated?
Literally the last line of the blog answer your question
Interesting provlems. Thx
What is test 72 of problem I?
How to solve problem A ?
Just https://e-maxx.ru/algo/path_cover (in Russian).
Docs form a DAG. Duplicate the vertices, for each edge of DAG add the edge (i, j+n) to a new bipartite graph. Find the maximal matching. Edges chosen for matching form a path cover. Each path is then solved independently, and it is easy.
Bad problem: it is not easy but at the same time it is just a copypaste from e-maxx.
How do you deal with duplicate vertices? I was able to figure out the DAG part and then googled my way into the mcbm solution, but I am currently unable to solve when some documents have the same permissions.
If two vertices are absolutely identical (the columns in the input are equal), just remember that one of them is the clone of the other and drop it from the rest of the solution except printing answer.
hmmm that's what I did initially, guess it must be something else that's wrong lol. thanks
EDIT: Ok i think my problem was decomposing the graph improperly (if $$$(i,j)$$$ is an edge and $$$(j,k)$$$ also an edge, I removed $$$(j,k)$$$ from the graph). :facepalm:
There's an interesting way to handle identical documents (credit to ashmelev): use the document index as the tiebreaker. The method you described works just fine, but this one is a bit more elegant in terms of code.
What is the idea for solution problem D?
Since you have to minimise the total time taken to watch the videos, try to utilise the memory in an efficient way by pairing up such $$$i$$$ and $$$j$$$ such that $$$a[i] + a[j] <= m$$$. ...
Firstly, sort the array in ascending order. Now maintain 2 pointers, $$$start = 0$$$ and $$$end = n-1$$$. If it satisfies the condition given in Hint, you can add both the values to the answer, increment $$$start$$$ and decrement $$$end$$$. If it doesn't, then $$$a[end]$$$ goes alone, so you add $$$a[end] + 1$$$ to you answer (1 minute to watch the video). This way, your overall time is minimised.
Complexity: $$$O(N)$$$ ...
When will the editorial be published?
How to see the failed test cases ? I am not able to see it
How to solve problem K ?
There is a way to visit every cell except for only one cell left. What strategy should we take to achieve this?
We can go right until we cannot go further, and then one cell below. Repeat until we reach $$$(n,n)$$$. Now, we can modify this route to change the cell that we do not visit. Among all such routes, what characteristic will the leftover cell have?
For the route that I explained above, the leftover cell is $$$(n,1)$$$. We can modify the point where we move below, and by this change, the leftover cell will move by $$$(-1,1)$$$. As a result, we get the fact that we can visit every cell, except for one cell in the longest antidiagonal. We can choose this one leftover cell, as the smallest one in the antidiagonal.
Only one type of shifting is available and dp.
how can i hack a solution when i can't see the author's code ?
update : problem solved!
How to solve Problem N?
First, you have to minimize the number that will appear in the first position of the answer, using as few operations as possible. If you have more operations left, do it again with the second position. Repeat the same process until you run out of operations. I implemented it storing in 10 vectors all the positions of the numbers from 0 to 9, then performing binary search in each position. Be careful with the leading zeros, and also, at the end of the process you might still have operations, if there is no way of making the firsts positions smaller. Example: "1111111111..." Then you can just delete random digits that are still not deleted.
Hope my explanation was not terrible.
Now I kinda get the concept, though the implementation seems quite complex. I wonder how so many teams solved it.
It's not that complex, but there must be simpler solutions.
If you have to delete $$$k$$$ values then you have to keep $$$n-k$$$ values. Let's try to understand an approach to decide the first digit (leftmost) of the answer. It cannot be a $$$0$$$ and it has to be a value in the range $$$[0,k]$$$ (inclusive). Because if we were to take the $$$k+1th$$$ value then we won't be able to take $$$n-k$$$ values in total. Greedily we choose the smallest value in the range $$$[0,k]$$$ as our first value. Mark this index as $$$l$$$, now to choose our next value we apply a similar technique but we have to choose the least value in the range $$$[l+1,k+1]]$$$. Call this value $$$mn$$$ and update $$$l$$$ to the first occurence of $$$mn$$$ in the range $$$[l+1,k+1]$$$. We can do this naively since our $$$l$$$ pointer moves atmost $$$n$$$ times in total. Now do this approach again by finding minimum of the range $$$[l+1,k+2]$$$ and so on.
To compute the minimum of the range, I just used a segtree. This makes the implementation quite easy imo — Submission
What was the order of problems in the onsite contest? Will you add ghosts?
The order of the problems from the official competition was the following one:
I don't know how to add ghost participants, but I'll try to find it out and, if possible, add them.
About Problem J :
Problem J is LP-Dual + Greedy . But the time limit is misleading .
LP duality is definitely one of the ways to solve this problem. But, in my opinion, there is an easier and cooler way to do it.
Take a look at how Hungarian algorithm works, and try to find something similar in this problem
The number of ways to subtract/add 1 for each row/column has exactly the same constraints as the potentials in the Hungarian algorithm
The time limit of problem C is even more misleading. There exists a solution in $$$O(n^2)$$$, but we decided not to increase the time limit because $$$O(n^3)$$$ is already difficult enough
We managed to cheese C in $$$O(n^4)$$$, not sure if that was intended or not.
can you tell a bit more about the solution? i thought keeping the count distribution of the k cards is not enough because the selection algorithm may make the states heavily biased. it may not b the case that the remaining cards are uniformly distributed before the k cards.
We just used linearity of expectation. Note that the contribution only depends on the distribution of the cards. For that you only need a multinomial distribution. For every possible size of your look-back, you can compute the distribution in $$$O(n^3)$$$, leading to an $$$O(n^4)$$$ solution.
That's kinda unfortunate. I had a rough time cutting off $$$n^4$$$ in this problem since neither Polygon nor our local judging system supports 64-bit C++, and it gives a huge decrease in constant factor, making the solution work like 3x-4x faster than on 32-bit C++. I've tried using optimized solutions from testers to find the right constraints, but it looks like your implementation of modular arithmetics is superior to theirs.
How do you solve H?
Use a topological sort to find the minimal $$$p_i$$$ for each vertex (basically you want to ensure that $$$p_i \leq p_j$$$ if $$$i$$$ is an ancestor of $$$j$$$). Then for each vertex, you must place all ancestors before it, so just retrieve the ancestors then binary search on the leftmost position you can place it at.
Thank you
How to solve H?
I'm kinda surprised so few participants solved L and G. They were much more popular on the official contest (all teams which solved 9 problems had G+H+L+6 easiest problems), and neither L nor G is especially hard.
On the other hand, A and F were the opposite of that: not solved on the onsite, popular during the mirror. Problem A is understandable, much more participants know the required techniques and can reduce the problem to those techniques; but F was considered one of the hardest problems in the set by me.
When will the editorial be published?
I think F is not difficult to solve it ,but maybe hard to prove it. I solved it by guessing.
It is easy to find that we need to use DP to solve this problem in O(n^2). And then we guess dp[i]=min(dp[j]+f(j,i)) [1<=j<=i-1], try a try, ac is ok.
If n<=300 the problem will be more difficult,I think.
Proved by geometry, It actually relates to area below segments.
Just upsolved it. Nothing hard, easier than A and L for sure. There was too much stress during the contest, but now it's much better.
The problem is, in short: you can buy some points and in the end you gain the area under the top part of their convex hull.
Sort the points by x. Write a DP:
DP[i] = answer if the last point is i. Constraints allow quadratic solution, so we can write two cycles: for the previous and the next point. When you move from the previous point to the next point, you can buy the next point and gain the area of the trapezoid between these points and OX axis. Since all segments are considered, this DP automatically remembers only the optimal choice.183055686
How solving problem E please ? I know this the problem solve math but how ?
J is absolutely beautiful. F and G are nice. Cool contest!
How to Solve L ?
Does anyone know what causes the verdict of hack showing "Unexpected verdict"?
I tried to hack some solutions (which seem to have wrong time complexity) for problem L, but I only got "Unexpected verdict".
The "Unexpected Verdict" happens when the checker returns
_fail, and is supposed to happen when a jury solution happens to fail on a valid testcase or a solution finds a better solution than the jury solution. I don't understand why this happens on problem L though, isn't the answer supposed to be deterministic (i.e. there is only one answer for one input)?Hmmmm, could it be that jury solution neither fits in TL? xd
Polygon will check all the solutions marked as "Correct", and if one of them fails, will return
_fail. Authors sometimes add participants solutions, so maybe one of them is slow, or maybe one of jury solutions is slow, which also can happen. Or the model solution is slow :)Yes, this time our solution (me + pashka) was actually slow. Thanks, YaoBIG. Now tests are better!
Thanks for the fix!
Would be also good to mark uphacked submissions in the standings (maybe change the color of '+'), and to run all contest submissions on new tests to see if they should be marked as uphacked.
Now someone looking for the code can check top-2 team's solution for L, but it's wrong. Our contest submission is also wrong but as it's not uphacked it may seem it's correct.
Ah I see. I did not know that all solutions marked as "Correct" will be checked and it is good for me to learn this! Thanks for the explanation!
How to solve problem H?
How to solve G?
Use one query to guess $$$s_2$$$, then try to guess characters in pairs ($$$s_3$$$ and $$$s_4$$$, $$$s_5$$$ and $$$s_6$$$, etc) efficiently. How can this be done?
If we want to guess a pair of characters efficiently, we should start from the second character in the pair and try to guess both of them by querying that position. When is it possible?
Suppose the string starts from $$$00$$$, and we want to guess a block of two adjacent characters by querying the prefix function or the antiprefix function. Analyze which combinations of characters are guessed with the prefix function better, and which — with the antiprefix function.
If you use any query and get $$$2$$$ or greater as the answer, you've successfully guessed two characters in one query. Let's take a look at the cases when you get $$$0$$$ or $$$1$$$. If you used prefix function, the answer $$$0$$$ may mean $$$01$$$ or $$$11$$$; the answer $$$1$$$ means that the next two characters are definitely $$$10$$$.
If you used antiprefix function, the answer $$$0$$$ may correspond either to $$$10$$$ or $$$00$$$; the answer $$$1$$$ corresponds to $$$01$$$. Note that we assume that the string begins with $$$00$$$, but it's a similar story with $$$01$$$.
So, by using the prefix function, we cannot distinguish $$$01$$$ from $$$11$$$, and by using antiprefix function, we cannot distinguish $$$10$$$ from $$$00$$$. If we use the wrong type of query, we need a second query to guess these two characters. What should we do to make sure we don't use the wrong type of query too often?
Pick the query type randomly, then we'll guess $$$2$$$ characters in $$$1.5$$$ queries on average.
Thanks. I now know how to do. Additionally, can I ask when the editorial will be posted?
Hopefully we'll finalize it in about 24 hours. I am sorry for the delay.
Nevermind... You don't have to use all contracts...
Solution
This is the solution of Torus path (K) . Please help me i am not able to clear all test cases , i have tried with dp.
K is simpler than DP.
You calculate dp in DFS order, it doesn't always find maximum path. Sometimes you can get better value if you go to already visited cell. Example:
3
2 2 2
2 2 2
1 2 2
This problem can be solved with dp using the fact that it's impossible to use both vertical and horizontal teleports. If you don't use vertical teleports, you can calculate DP in vertical order and vice versa.
But we cannot visit the same cell twice. It will be great if you can give code please
We cannot visit the same cell twice but your function can visit some cells in one path and block some other paths. For the same reason we can't use DFS for finding shortest paths.
Solution with vertical and horizontal DP: 183454259
I understood that it's possible to use both types of teleports so this idea is incorrect. But in this problem you don't need it so this solution works.
I recognize that for D it is simply to permute $$$a$$$ such that the least pairs $$$(a_i, a_{i+1})$$$ add to over $$$m$$$. To do this I use a simple greedy algorithm: for $$$a_x$$$ starting from smallest $$$a_x$$$, pair it with largest $$$a_y$$$ such that $$$a_x + a_y \leq m$$$. Then arrange pairs as such: $$$a_{y_1}, a_{x_1}, a_{y_2}, a_{x_2}, ...$$$. The remaining elements will always cause pairs that add to $$$\geq m$$$. I came up with this algorithm through intuition (it works). Is can somebody prove correctness?
Where can I find the editorial?
How to solve problem F ?
Not sure why does this solution work? 187063817 (why does this solution doesn't work without line 18: dp[i][j][t] = ans = -INF; should be just ans = -INF; from my knowledge it enters an infinite loop in this case).
For Problem K 1765K - Torus Path