### BledDest's blog

By BledDest, 2 months ago,

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, I_Remember_Olya_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.

• +210

 » 2 months ago, # |   +41 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.
•  » » 2 months ago, # ^ |   +56 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.
•  » » » 2 months ago, # ^ |   +10 Is the contest package uploaded?Incidentally, what are https://icpc.sgu.ru/ and https://contest.sgu.ru/ used for?
 » 2 months ago, # |   -29 It should be rated!!
 » 2 months ago, # |   -10 Is $\mathcal{\color{red}{Hack}}$ available?
 » 2 months ago, # |   +1 How challenging are the problems? Should I attempt to participate if I'm green?
•  » » 2 months ago, # ^ |   0 You definitely should
•  » » 2 months ago, # ^ |   +58 For a lone green participant, the problemset can be very challenging. I advise you to play this contest with a team.
•  » » » 2 months ago, # ^ |   0 What about a lone blue one?
•  » » » » 2 months ago, # ^ |   +48 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.
 » 2 months ago, # |   0 excited
 » 2 months ago, # |   -34 As a participant i will not have participate
 » 2 months ago, # |   +181 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!
•  » » 2 months ago, # ^ |   +50 I think it should be ‘chief judge’ instead of ‘chef judge’ lol
•  » » » 2 months ago, # ^ |   +78
 » 2 months ago, # |   -120 It would be nice to finally fix language selector issue and remove excessive use of flags.Sources with supporting arguments: fix language selector blog post flags are not languages, www.flagsarenotlanguages.com 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.
•  » » 2 months ago, # ^ |   +27 Please use your plugin and don't bother us all.
 » 2 months ago, # |   -8 Is it rated?
•  » » 2 months ago, # ^ |   -21 Is it rated?
 » 2 months ago, # |   0 I'm very excited to participate in this competition. I wish all the players a good result!
 » 2 months ago, # |   0 How difficult is it?
 » 2 months ago, # |   -52 Is this contes rated?
•  » » 2 months ago, # ^ |   0 Literally the last line of the blog answer your question
 » 2 months ago, # |   0 Interesting provlems. Thx
 » 2 months ago, # |   0 What is test 72 of problem I?
 » 2 months ago, # |   0 How to solve problem A ?
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   +5 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.
•  » » » » 2 months ago, # ^ |   +10 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.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   +5 hmmm that's what I did initially, guess it must be something else that's wrong lol. thanksEDIT: 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:
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +31 There's an interesting way to handle identical documents (credit to I_Remember_Olya_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.
 » 2 months ago, # |   +3 What is the idea for solution problem D?
•  » » 2 months ago, # ^ |   0 HintSince 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$. ... SolutionFirstly, 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)$ ...
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Could you please prove this idea? It can be brief. I can figure out the methods but seem to always wonder if they are right.I'd be super grateful!!
 » 2 months ago, # |   +10 When will the editorial be published?
 » 2 months ago, # | ← Rev. 2 →   +1 How to see the failed test cases ? I am not able to see it
 » 2 months ago, # |   +1 How to solve problem K ?
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Hint 1There is a way to visit every cell except for only one cell left. What strategy should we take to achieve this? Hint 2We 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? Hint 3 (+ Answer)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. Solution Codep=[*map(int,open(0).read().split())] n=p[0] g=p[1:] print(sum(g)-min(g[n-1:-1:n-1])) # Don't bother the code being too short and unreadable, it's simply just sum of everything - min of antidiagonal 
•  » » 2 months ago, # ^ |   0 Only one type of shifting is available and dp.
 » 2 months ago, # | ← Rev. 2 →   0 how to solve n please? update:solved
 » 2 months ago, # | ← Rev. 2 →   +7 how can i hack a solution when i can't see the author's code ?update : problem solved!
 » 2 months ago, # |   -11 How to solve Problem N?
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   -8 Now I kinda get the concept, though the implementation seems quite complex. I wonder how so many teams solved it.
•  » » » » 2 months ago, # ^ |   0 It's not that complex, but there must be simpler solutions.
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 the problem asks to pick a lexicographically smallest subsequence of length |x|-k, so just find the next digit from left to right (prefer '0', fallback on large digits '1','2','3'...);I memorize the index of every next digit from every index(simple 2D array), then start from left trying to find a next small digit(prefer '0'). O(10*|x|). submission
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Perhaps this could be most elegant solution!! But its failing one case that i cant access Someone help please! #include using namespace std; #define int long long #define endl "\n" void solve(){ string s; int k; cin >> s >> k; int n = s.size(); vector stk; for(int i = 0; i < n; ++i){ while(stk.size() && stk.back() > s[i] && k){ if(s[i] == '0' && stk.size() == 1) break; stk.pop_back(); --k; } stk.push_back(s[i]); } while(k){ stk.pop_back(); --k; } for(char c : stk) cout << c; cout << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; cin>>tc; while(tc--) { solve(); } return 0; } 
 » 2 months ago, # |   0 What was the order of problems in the onsite contest? Will you add ghosts?
•  » » 2 months ago, # ^ |   +12 The order of the problems from the official competition was the following one: Spoiler Broken Keyboard Infinite Chess Project Manager Chemistry Lab Hero to Zero Watch the Videos Access Levels Torus Path Card Guessing Minimum LCM Guess the String Number Reduction Exchange Hospital Queue I don't know how to add ghost participants, but I'll try to find it out and, if possible, add them.
 » 2 months ago, # | ← Rev. 2 →   +10 About Problem J : SpoilerProblem J is LP-Dual + Greedy . But the time limit is misleading .
•  » » 2 months ago, # ^ |   +10 SpoilerLP 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. SpoilerTake a look at how Hungarian algorithm works, and try to find something similar in this problem SpoilerThe number of ways to subtract/add 1 for each row/column has exactly the same constraints as the potentials in the Hungarian algorithm
•  » » 2 months ago, # ^ |   +22 Another spoiler, now about problem CThe 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
•  » » » 2 months ago, # ^ |   +8 Spoiler for CWe managed to cheese C in $O(n^4)$, not sure if that was intended or not.
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » 2 months ago, # ^ |   +12 SpoilerThat'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.
 » 2 months ago, # |   +11 How do you solve H?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 2 months ago, # ^ |   0 Thank you
 » 2 months ago, # |   +13 How to solve H?
 » 2 months ago, # |   0 How to solve problem N ?
 » 2 months ago, # |   +57 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.
•  » » 2 months ago, # ^ |   +11 When will the editorial be published?
•  » » 2 months ago, # ^ |   +3 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.
•  » » » 2 months ago, # ^ |   +12 Proved by geometry, It actually relates to area below segments.
•  » » » 2 months ago, # ^ |   +2 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. Solution of FSort 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
 » 2 months ago, # | ← Rev. 3 →   +3 How solving problem E please ? I know this the problem solve math but how ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 if a is less than b, it's useless to do the exchange operation as at this condition you will lose silver coins, so in this case the optimal solution is to complete a quest and exchange one gold coin with a silver coins, so the answer will be n / a rounded up, same answer works for condition where a equals b.if a is greater than b, you can always earn silver coins by doing the exchange operation, since you start the game with no coins, you need to complete one quest then do the exchange operation any number of times, so the answer will be 1.
 » 2 months ago, # |   +60 J is absolutely beautiful. F and G are nice. Cool contest!
 » 2 months ago, # |   0 How to Solve L ?
 » 2 months ago, # | ← Rev. 2 →   +5 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".
•  » » 2 months ago, # ^ |   +12 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)?
•  » » » 2 months ago, # ^ |   0 Hmmmm, could it be that jury solution neither fits in TL? xd
•  » » » » 2 months ago, # ^ |   +20 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 :)
•  » » » » » 2 months ago, # ^ |   +23 Yes, this time our solution (me + pashka) was actually slow. Thanks, YaoBIG. Now tests are better!
•  » » » » » » 2 months ago, # ^ |   +3 Thanks for the fix!
•  » » » » » » 2 months ago, # ^ |   +3 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.
•  » » » » » 2 months ago, # ^ |   +3 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!
 » 2 months ago, # |   0 How to solve problem H?
 » 2 months ago, # |   0 How to solve G?
•  » » 2 months ago, # ^ |   +8 SpoilerUse 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? SpoilerIf 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? SpoilerSuppose 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. SpoilerIf 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? SpoilerPick the query type randomly, then we'll guess $2$ characters in $1.5$ queries on average.
•  » » » 2 months ago, # ^ |   0 Thanks. I now know how to do. Additionally, can I ask when the editorial will be posted?
•  » » » » 2 months ago, # ^ |   0 Hopefully we'll finalize it in about 24 hours. I am sorry for the delay.
 » 2 months ago, # | ← Rev. 3 →   0 Nevermind... You don't have to use all contracts...
 » 2 months ago, # |   0 SolutionThis is the solution of Torus path (K) . Please help me i am not able to clear all test cases , i have tried with dp.
•  » » 2 months ago, # ^ |   0 K is simpler than DP.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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:32 2 22 2 21 2 2This 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.
•  » » » 2 months ago, # ^ |   0 But we cannot visit the same cell twice. It will be great if you can give code please
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » 2 months ago, # ^ |   0 Thank You
 » 2 months ago, # |   0 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?
 » 2 months ago, # |   0 Where can I find the editorial?
 » 2 months ago, # |   0 Where is Editorial for this contest???
 » 2 months ago, # |   0 How to solve problem F ?
 » 5 weeks ago, # |   0 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).
•  » » 5 weeks ago, # ^ |   0 For Problem K 1765K - Torus Path