### MikeMirzayanov's blog

By MikeMirzayanov, 4 weeks ago, translation,

Hello!

ICPC Southern and Volga Russian Regional Contest (Northern Eurasia) 2020 has ended on November 15. This year the competition took place online. 108 teams competed, many of them received an invitation based on the results in Qualification Contest.

Hope you enjoy the problems. In this contest I play a role of Cheif Judge and the jury teams consists of ex-participants of ICPC from Saratov and jury members from other cities: adedalic, I_Remember_Olya_ashmelev, BledDest, DmitryKlenov, DStepanenko, elena, KAN, kuviman, MikeMirzayanov, pashka, PavelKunyavskiy, Дмитрий Мещеряков, Герман Наркайтис. Many thanks to all of them!

I send special rays of gratitude to testers: Merkurev, Um_nik, romanasa, josdas, Nebuchadnezzar, Perforator, Oleg_Smirnov, IlyaLos, Supermagzzz, Stepavly, Igor_Kudryashov, HolkinPV, Edvard, le.mur!

I invite ICPC teams and individual participants of Codeforces competitions to take part!

Of course, the competition will be unrated. I ask the participants of the official competition to refrain from participating in the mirror and discussing problems until its end.

Since this year the audience of participants was wider (due to the online format), we also selected problems a little more accessible than in previous years. If you are from the top team that claims a medal in the ICPC Finals, then it may be more fun for you to take part in this contest personally.

Good luck!

• +269

 » 4 weeks ago, # |   0 Wow! I always wanted to pass the ICPC level contest in real time. Thank you so much MikeMirzayanov. Good luck to all.
 » 4 weeks ago, # |   -12 What should be the size of the team? I am assuming it to be 3
•  » » 4 weeks ago, # ^ |   -11 In such contests there is not interesting to participate alone
•  » » » 4 weeks ago, # ^ |   -11 Yes, I am forming a with some friends.... I wanted to know what should be the size. I guess there should be 3 people in a team....Am I right?
•  » » » » 3 weeks ago, # ^ |   -11 Yes, the ideal size of team is three people. But you can participate by incomplete team (2 people) or individually. More than 3 people is not allowed
•  » » » » » 3 weeks ago, # ^ |   -11 Thanks for confirming
 » 3 weeks ago, # |   -35 in part of virtual contests somthing happned wrong!please fix it.
•  » » 3 weeks ago, # ^ |   0 it is very hard to handle this type of big website and they are handling it very greatly. you should wait for sometime before this type of comment.
 » 3 weeks ago, # |   +33 Hey,I'm wondering if there is a strict limit on number of team-mates allowed? My friends and I are looking to do this contest for fun, and since it's unrated, we're wondering if a larger group than 3 people is okay.Thanks!
•  » » 3 weeks ago, # ^ |   0 not more than 3 teammates is allowed
 » 3 weeks ago, # |   +60 Maybe a bit irrelevant but Merry Christmas codeforces community!!!
 » 3 weeks ago, # |   +21 stuck in queue with H :(
 » 3 weeks ago, # |   +187 Mike: If you are from the top team that claims a medal in the ICPC Finals, then it may be more fun for you to take part in this contest personally.Chinese LGMs: Naaah, let's solve it altogether in 2 hours
•  » » 3 weeks ago, # ^ |   +26 On the other hand, the blog post name suggests to do it as a team (in Russian), and it is a bit optimistic to expect people to put their time into reading the post itself :)
 » 3 weeks ago, # |   +31 Maybe the contest could have been extended by 10 mins due to long queue :(
 » 3 weeks ago, # |   +2 how to solve J
•  » » 3 weeks ago, # ^ |   +18 Find the Minimum Spanning Tree 3 cases Maximum Edge is K, less than K and Greater than KIf Maximum Edge is Greater than K then all the lengths greater than K in the MST are to be consideredOtherwise in other 2 cases would be min(abs(edge weight — k)) for all edge weights
•  » » 3 weeks ago, # ^ |   0 I first joint the edge which is closest to k and thae applied mst.... But its giving wrong ans why
•  » » » 3 weeks ago, # ^ |   +1 because edges that are smaller than k basically won't be counted, so you should use them as much as possible.
•  » » » » 3 weeks ago, # ^ |   0 can u give any graph example on which it will fail plzzzzzzz
•  » » » » » 3 weeks ago, # ^ |   0 Check this test: 1 4 4 10 1 2 1 1 3 1 2 3 11 3 4 12 If you join edge 2 => 3 with cost $11$ the answer will be $3$. Correct answer is just $2$.
•  » » » » » » 3 weeks ago, # ^ |   0 https://codeforces.com/contest/1468/submission/102338964 can you tell why it is giving runtime error in test 46 not able to figure it out..
 » 3 weeks ago, # |   +13 When will the editorial available?
 » 3 weeks ago, # |   +6 What is the solution idea of problem J(road reform)?thanks in advance & Merry Christmas.
•  » » 3 weeks ago, # ^ |   +4 the trick from prim's MST + some greedy
•  » » » 3 weeks ago, # ^ |   -8 stuck with Kruskal whole time :(
•  » » » » 3 weeks ago, # ^ |   +11 I solved it using Kruskal.
•  » » » » 3 weeks ago, # ^ |   +11 We can also solve it using Kruskal.Just need to find Minimum Spanning Tree only and some greedy conditions
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +4 There is a property that the Maximum Edge Weight in the MST of a graph is the minimum among all possible spanning trees of that graph. (Not sure if it is true when you find the MST using Prim's Algorithm, but this is definitely true when you find it using Kruskal's Algorithm) More DetailsSo, there are 2 cases:Let Maximum Edge Weight in the formed MST (using Kruskal's) = P1) P >= k: Then clearly you need to reduce all the edges' weights whose weights are greater than k to k. So, ans = summation of [number of operations required for edge i] where i is any edge in the formed MST whose weight is greater than k. Clearly, considering any other spanning tree will only increase the overall number of operations.2) P < k: Then, all the other edges (which are not included in the MST) whose weights are greater than k can also be included in this MST by adding one of them and removing some edge from the current MST (to remove cycle). Hence, ans = minimum of [number of operations required for edge i] where i is any edge in the whole graph whose weight is greater than equal P.
•  » » » 3 weeks ago, # ^ |   0 I first joint the edge which is closest to k and thae applied mst.... But its giving wrong ans why??
 » 3 weeks ago, # |   0 Solution for M?
•  » » 3 weeks ago, # ^ |   +4 Divide the sets into "big" and "small" sets (more or less than $\sqrt{N}$ elements). Then come up with three different methods for checking whether two big sets are similar, whether two small sets are similar and whether a big and a small set are similar.
•  » » » 3 weeks ago, # ^ |   +8 How do you do "small vs small" part without introducing additional log factor to complexity? My idea was to generate all pairs of elements for each set and then find a pair that occurs more than once, but IIUC this can't be done in linear time unless we are using some hashsets. I have a slight suspicion that if the difference between my TL solution and my AC solution is "let's optimize by discarding all unique input numbers right away", this means I didn't do the model solution :)
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +26 but IIUC this can't be done in linear time unless we are using some hashsets. Recall the data structure that behaves like an array but you have the additional operation of making all entries 0 in amortized $O(1)$ time. You can achieve this by memorizing the number of times the array has been reset and for each entry the number of resets when this entry was accessed the last time.Basically you have an array of pairs $(u, v)$ and you want to check if there are duplicates in linear time. For every $u$ make a list of such $v$ that the pair $(u, v)$ exists. Use one global "array with resets". For each $u$, first reset the array, then scan through the pairs containing $u$ to check which $v$ occurs multiple times.Credit goes to .I. for inventing this part of the solution.
•  » » » » » 3 weeks ago, # ^ |   +1 Can't you solve it in O(n) using radix sort?
•  » » » » » » 3 weeks ago, # ^ |   0 Probably? I am not sure whether the constant is good enough though (in particular, whether it is faster than hashsets).
•  » » » » » » » 3 weeks ago, # ^ |   0 https://codeforces.com/contest/1468/submission/102338964 can you please tell why it is giving runtime error on test 46 i am not able to figure it out my mistake
•  » » » » » » » » 3 weeks ago, # ^ |   +2 Have you tried the following: Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution) Write a program to generate thousands of small (!) test cases Using those two, find a test case where your program gives the wrong answer Use print statements or a debugger to see where exactly your program does the wrong thing. 98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.
•  » » » » » » » » » 3 weeks ago, # ^ |   0 thanks for your reply i definately look into my debugging skill i changed one thing cout<<(*it) by changing this why its accepted RE code link https://codeforces.com/contest/1468/submission/102338964Can you tell is that something with syntex when i was getting RE??
•  » » » » » 3 weeks ago, # ^ |   0 Nice, thank you! Right, I stopped thinking in this direction after hitting "I don't have enough memory for N^2 bucket sort array".
•  » » » 3 weeks ago, # ^ |   +3 I came up with this, but didn't how to do the "big vs small" part.
• »
»
3 weeks ago, # ^ |
+14

I have an $O(n \sqrt{\frac{n}{64}})$ bitset solution. You find an implementation of this algorithm in Python here 102487844.

The key idea is to handle the most commonly occurring elements first (lets say occurring $B=100$ times or more) using a bitset. After you have taken care of the common elements, you can forget about them and only keep the uncommon elements.

##### Step 1. The algorithm to handle common elements (runs in $O(\frac{n ^ 2}{64 B})$)

Let $m$ be the number of common elements. For each set make a bitset of size $m$ that marks the commonly occurring elements in that set. Now go over every element $a$ (both common and uncommon), and for each $a$ go over all sets that $a$ is in. You then use the bitsets to find some common element $b \neq a$ that occurs in 2 or more of these sets.

##### Step 2. The algorithm to handle only uncommon elements (runs in $O(n B)$)

Go over all sets $A$, and then go over every element $a$ in $A$. Finally go over all sets $B$ that contain $a$ and check if $A$ and $B$ contains a common element (other than $a$) using a $n$ large array.

Finally, note that by letting $B \approx \sqrt{n/64}$ you get time complexity $O(n \sqrt{\frac{n}{64}})$.

 » 3 weeks ago, # |   +2 Is M something related to Bitsets or Bipartite graph?
•  » » 3 weeks ago, # ^ |   +24 You basically need to find a cycle of length $4$ in a bipartite graph, and finding a cycle of length $4$ in a general graph can be solved in $O(M\sqrt{M})$ by enumerating in a certain way based on degree of vertices.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 We reduced to it down to exactly this. Can you share some resource for learning how to find a cycle of length 4 in O(MrootM)
•  » » » » 3 weeks ago, # ^ |   +12
•  » » » » 3 weeks ago, # ^ | ← Rev. 4 →   +72 we consider a stronger problem: given an undirected simple graph $G_0$, count the number of cycles of length $4$.sort the vertices in degree-nonascending order, say $u_1, u_2, \ldots , u_n$ from left to right (that is, $u_1$ has the largest degree, and $u_n$ has the smallest).create a new graph $G_1$, which is a directed graph, the edges are identical with the original undirected graph ($G_0$), but they are all pointing towards the right direction. (from large-degree vertex to small-degree vertex)maintain a array $b[]$, its elements are initially $0$, and variable $\mathrm{answer}$ is initially $0$, too.enumerate all $x \in V$,$\qquad$ enumerate all $y$ which $x$ can reach it in the directed graph ($(x \to y) \in G_1$),$\qquad \qquad$ enumerate all $z$ which $y$ can reach it in the original graph ($(y \to z) \in G_0$),$\qquad \qquad \qquad$ if $z$ is to the right of $x$ (in the sequence $u_1, u_2, \ldots , u_n$),$\qquad \qquad \qquad \qquad$ increase $\mathrm{answer}$ by $b[z]$,$\qquad \qquad \qquad \qquad$ and increase $b[z]$ by $1$.$\qquad$ clear all modified $b[\ast]$s.=== The idea of the procedure above is, $x$ is the leftmost vertex in the cycle, and $z$ is the opposite vertex of $x$ in the cycle, if two $y$s ($y_1, y_2$) both reach the same $z$, the two halves of the $4$-cycle merges as one full cycle, as $x \to y_1 \to z$ and $x \to y_2 \to z$.about the time complexity, consider $\deg(y)$ is added to the total-time everytime when $y$ was enumerated in the $x \to y$ loop. two cases: $\deg(y) \le \sqrt{m}$: the number of valid $x$s is at most $m$. $\deg(y) > \sqrt{m}$: must have $\deg(x) \ge \deg(y) > \sqrt{m}$, because $\displaystyle \sum_{i=1}^{n} \deg(i) = 2 m$, that means the number of valid $x$s is at most $2 \sqrt{m}$. add up the two cases, total $\mathcal O (m \sqrt{m})$.to solve the original problem(just find one cycle is enough, but you need to print it), you only need to slightly modify the $b[z]$ part. see 102311532 for other details.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Hi !! Can you please explain how in case 1, the number of valid x's is at most m. I think i am confusing there. Thanks in advance.UPD : Got it , but i think number of valid x's in case 1 is $deg(y)$ and the $\sum_{deg(y)<\sqrt{m}} deg(y)^{2}$ is $O(m*\sqrt{m})$ . Please correct me if i am wrong.
•  » » 3 weeks ago, # ^ |   +27 if you consider values as the other part of the bipartite graph, the problem now is to find a four-edges cycle.and that's a classic problem which takes $\mathcal O (m\sqrt{m})$ time complexity.
•  » » 3 weeks ago, # ^ |   +6 You can speed things up using a bitset, to run in $O(n \sqrt{n/64})$ time, see here. But I doubt a brute $O(n^2 / 64)$ bitset solution would run in $< 1$ s.
 » 3 weeks ago, # |   +16 How to solve A ?
•  » » 3 weeks ago, # ^ |   0 Answered here
 » 3 weeks ago, # |   -18 in J I first joint the edge which is closest to k (means abs(k-edgeweight) is minimum) and then applied normal mst.... But its giving wrong ans why?? any idea plzzz
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +59 Have you tried the following: Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution) Write a program to generate thousands of small (!) test cases Using those two, find a test case where your program gives the wrong answer Use print statements or a debugger to see where exactly your program does the wrong thing. 98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms. The question you should be asking is "why should this be correct". You should be satisfied with a solution if you have found a proof that it is correct, not if you have no obvious counterexample. I see no reason this should be correct. Why do you think it is correct? Yeah, it seems that it should most of the time give good trees, but there is nothing about this construction that makes it obvious that it always gives the best solution.
•  » » » 3 weeks ago, # ^ |   -25 this guy has not posted his code here or told to debug his code / He is just explaining his idea and asking if it's correct or not :P , Dude You could have understood what he was saying and told him what's wrong in his idea/approach
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +39 This method can be used equally well to debug ideas. I don't think there is any meaningful way to tell "what is wrong with this idea" (because I can't understand why they thought this would be correct) other than giving a countertest. And I have outlined a method of obtaining a countertest above.
•  » » » » » 3 weeks ago, # ^ |   -19 cool , If I try some problem hard enough ( write naive solutions/ write test cases ) and still not able to get it and feel Something is wrong with my Idea , I do not hesitate to ask it here (I get valuable suggestions from some very good coders to "debug my idea" here on codeforces), That's what the mission of codeforces discussion is.
•  » » 3 weeks ago, # ^ |   0 The same happened with me as well. The problem with this approach is that it may happen that you had selected an edge which may be nearest to $k$ however this was originally greater than $k$. Due to this, there may remain some edges whose weight is originally less than or equal to $k$, which might have provided optimal answer if used.The correct solution is: Construct MST only from the edges whose weight is less than or equal to $k$. Let the closest of such edges used in MST be $e$. If everything is connected, you need to check, whether there exists an edge whose weight is greater than $k$, but is closer as compared to $e$. If so, it would be better to add this edge to generated MST as well (though original MST was already connected). If the obtained MST is not connected, consider edges whose weight is greater than $k$. Hope it helps!!
 » 3 weeks ago, # |   0 How to solve A?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 It is obvious that for any almost increasing sequence (AIS) of size 3 $b_1,b_2,b_3$, we have two cases: $b_3 \geq b_2$ $b_3 < b_2, b_3 \geq b_1$ Let us consider the first case. We can iterate $a_i$ from $i = 1$ to $n$, and at each point, find $a_j$ such that $j < i$, $a_j \leq a_i$ and the length of the AIS ending at that point is maximum. If that value of length is $L$, the new value is $L+1$.Now to consider the second case. To do this, we find the greatest $j$ such that $j < i$ and $a_j > a_i$. Now, just need to find $a_k$ such that $k < j$, $a_i \geq a_k$ and the length of AIS ending at that point is maximum. If that value of length is $L$, the new value is $L+2$.Both of these operations can be done by finding the last greater element with a stack, and using a persistent segment tree to find the best length. My submission
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +6 I did it without persistence and still O(NlogN). An almost increasing sequence is just an increasing sequence with some additional elements. Something like indices inc_1, inc_2, .., inc_6 and indeces add_1, add_2, .., add_3 with inc1 < add_1 < inc2 < add_2 < inc_3 < inc_4 < inc_5 < add_3 < inc6(ordered indeces) where indeces on inc corespond to a non-decreasing subsequence and the additional indeces add are bigger than both neighbours in the ordered indeces sequence. And then we just do dp on the increasing subsequence, dp[n] = max(case 1 no additional element, case 2 there is additional element j) = max(max(dp[i] + 1, with a[i] <= a[n]), max(dp[i] + 2, with a[i] <= a[n] and i <= j where j is biggest such that a[j] > a[n], j is additional element)). Then we observe that if there is a k such that a[i] <= a[k] <= a[n] with k between j and i then i doesn't need to be accounted for in the second case. Now let a[k] = biggest such that k >= j and a[j] <= a[i] and we have dp[n] = max(max(dp[i] + 1, with a[i] <= a[n]), max(dp[i] + 2, with a[k] < a[i] <= a[n]) which can be optimized using Segtree on values of dp[i] and a[i] as the position
 » 3 weeks ago, # |   0 How to solve H?
•  » » 3 weeks ago, # ^ |   +3 Every time you can remove k-1 elements so count of numbers you want to remove must be divisible by k-1 and now when count of numbers is >k-1 , you can bring them down to k-1 by applying operation between them now if any b[i] is having (k-1)/2 elements in left and (k-1)/2 in right you can do last removal ok k-1 elements so ultimately you just need to check that atleast one b[i] should have >=(k-1)/2 elements in left and in right also. English is not so good :(
 » 3 weeks ago, # | ← Rev. 2 →   +56 I is such a troll problem, it could be solved in 5 mins. Browsing through various solutions it seems that many people significantly overcomplicated it (e.g. TOP2 teams), so here's my solution (that took me long time to realize).Check if absolute value of cross product of (dx1, dy1) and (dx2, dy2) is n. If it is then print $[0, g) \times [0, n/g)$, where $g=gcd(dx1, dx2)$
•  » » 3 weeks ago, # ^ |   +59 When I got that accepted during testing authors thought that tests (or checker) are wrong.
 » 3 weeks ago, # |   +12 Will be get an editorial?
 » 3 weeks ago, # |   0 Why I am getting WA in J? I had to find an edge that is close to k and then used Kruskal. Is this approach Wrong?
•  » » 3 weeks ago, # ^ |   0 This may help. Previous Comment
•  » » » 3 weeks ago, # ^ |   0 I have checked the minimum of abs(a[i]-k). So I think I already covered what you're solution implies. So I not looking at greater only. I am looking at the whole 3 scenarios(>,=,<). Is it wrong?
•  » » » » 3 weeks ago, # ^ |   0 Yeah. As the edges whose weight is less than or equal to $k$ don't make the answer any worse (except the tricky part given in #2 in the previous comment). So, we have to use them first.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I think if u can give some example on which it will fail ... it can really help all of us .. thanks
 » 3 weeks ago, # |   +11 Someone getting an AC on G. Hobbits with Doubles and Binary Search? I am getting TLE, expected time complexity $O(n * log(max(A_i)))$. Are doubles really that slow or was this intended not to pass?
•  » » 3 weeks ago, # ^ |   +16 102317815 runs in 0.140, and probably can be optimized further. Initially I was getting TLE because of cin>> input straight into double instead of using much faster int :)
•  » » » 3 weeks ago, # ^ |   +3 Woaaah, I did the same and got AC, I failed to realise IO was the bottleneck. Thanks a lot :)
•  » » » 3 weeks ago, # ^ |   +5 I had the same issue with G for an hour, until I decided to just submit one with int in the last 5 minutes randomly and it worked. Basically, during the contest I generated random max tests, and ran my solution locally to check for such bottlenecks — it seemed to only take about 66ms on my Linux machine to fully execute. Thus, I thought the bottleneck was that the testcase was handcrafted to have a lot of intersections, and thus I need to convert double operations to float. This sadly gave WA, and I was left flailing about a lot.After the contest, errorgorn also tested a maxtest on his windows machine, and it took well over 2000ms. Can anyone explain the discrepancy in these? I have 0 idea about these things.
•  » » 3 weeks ago, # ^ |   +5 I copied your code and wanted to see if the verdict would have remained same if you had used scanf instead of cin. And that's when it happened:your code submitted in c++ 14 gives WA on test 10your code submitted in c++ 17 passes that test case.I don't understand why that happened ?
•  » » » 3 weeks ago, # ^ |   0 Actually it can be due to architecture, operations on doubles in C++17(64 bit) are more precise than doubles in C++14. I used doubles cause I was getting TLE and thought that could speed things up. I submitted the same code in C++14 with long doubles and it worked as expected.Code
 » 3 weeks ago, # |   +5 Problem D reminds me of Tablecity
 » 3 weeks ago, # | ← Rev. 3 →   0 Can someone give any hint to B? I reduced the problem to finding substring of maximum length with $sum - len \cdot k > 0$
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Nvm, I didn't notice the fact that first element of substring must be greater than $k$, greedily extending good substrings works knowing that.However I'm curious about solutions with D&C/Segment Tree. Is there anyone ready to explain it?
 » 3 weeks ago, # |   -8 https://codeforces.com/contest/1468/submission/102371387THIS IS MY CODE FOR K CAN ANYONE HELP ME TO FIGURE OUT WHY IT'S NOT ACCEPTED
•  » » 3 weeks ago, # ^ |   +35 Because there are some bugs in your code. :)
•  » » » 3 weeks ago, # ^ |   -8 can you give the case, so that I can improvise my code :]