### cip999's blog

By cip999, 2 months ago,

Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems.

There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I has already appeared in a contest (most likely also in Polish contest, if you know it please tell us in the comments). See also this comment.

Pre-contest predictions

Detailed overview on the problemset and a bit of behind-the-scenes

Which author did what?

Some thoughts from cip999

## Hints and solutions

A

B

C

D

E

F

G

H

I

If you find any typo, feel free to tell us with a comment. Moreover, if you want to share your opinion on the problemset, we are eager to read it.

• +533

 » 2 months ago, # |   +69 Great problems, but too hard for me :,(
•  » » 2 months ago, # ^ |   +1 Sad round for me, too. ToT
•  » » 2 months ago, # ^ |   0 me too
•  » » 7 weeks ago, # ^ |   0 same here, the ideas behind each problem are brilliant, but.... (I can only solve A :'( )
 » 2 months ago, # |   -40 Everywhere graph . Why :|
 » 2 months ago, # |   0 Solutions and Implementations aren't visible. Kindly fix it. Thanks.
•  » » 2 months ago, # ^ |   0 Just read what the editorial says, "As of now, only hints are available"
 » 2 months ago, # |   +49 One of the finest rounds on codeforces. kudos to the problem-setters!
•  » » 2 months ago, # ^ |   0 for me UNO reverse :(
 » 2 months ago, # |   +21 Great Problems.
 » 2 months ago, # |   +12 Tooooooooooooooooooo.. Hard. Yet, very interesting.
 » 2 months ago, # | ← Rev. 3 →   +2 .
 » 2 months ago, # |   0 In problem B, won't only the winners(getting best standings) of the 5 marathons be the only potential candidates for the gold medal? Please, someone, help
•  » » 2 months ago, # ^ | ← Rev. 2 →   +23 Consider this case:162 2 2 2 21 6 6 6 66 1 5 5 55 5 1 4 44 4 4 1 33 3 3 3 11 is the only one that can get a gold medal, but he didn't win any marathon
•  » » » 2 months ago, # ^ |   0 Thanks Man
•  » » » 2 months ago, # ^ |   0 Yeah, I tried to solve similar way, whose rank-sum will be less than will be a potential winner but I got WA.
•  » » » » 2 months ago, # ^ |   +3 Just consider the following case: Number of participants: 5 Marathons and ranks: M1: 1 2 3 4 5 M2: 1 2 3 4 5 M3: 1 2 3 4 5 M4: 4 2 3 5 1 M5: 3 2 4 5 1 2 has the lowest 'ranksum', still 1 is the winner.
•  » » » » » 2 months ago, # ^ |   0 Yeah, but in this case, we simply take a lower index if the sum is equal???
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 By 'ranksum', you mean the sum of the ranks of the player across the 5 marathons, right?What I am trying to say is that the concept of 'ranksum' is of absolutely no use in some cases, as the superior athlete might not actually have the lowest ranksum.In the above example itself, the ranksum of the superior athlete 1 (0 + 0 + 0 + 4 + 4 = 8) will be greater than the ranksum of the athlete 2 (1 + 1 + 1 + 1 + 1 = 5), even though 1 is the superior athlete...
•  » » » » » » » 2 months ago, # ^ |   -14 Yeah, now I got your point but I am unable to find any such example. Below is my code it's a little bit hard to understand. Thanks. void solve() { int n; cin >> n; vector> v(n, vector(5)); vector> sum(n); ll temp = 0; for (int i = 0; i < n; i++) { temp = 0; for (int j = 0; j < 5; j++) { cin >> v[i][j]; temp += v[i][j]; } sum[i] = {temp, i + 1}; // putting rankSum in vector } sort(sum.begin(), sum.end()); temp = sum[0].second; // taking index of lower rankSum vll m(5); ll flag = 0, k = 0; for (int j = 0; j < 5; j++) { flag = 0; for (int i = 0; i < n; i++) { if (v[temp - 1][j] < v[i][j]) { flag++; } } m[k] = n - flag - 1; k++; } if (n % 2 == 1) { n--; } for (auto x : m) { if (x > n / 2) { cout << -1 << "\n"; return; } } cout << temp << "\n"; } 
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Your code is throwing a lot of compilation errors.You could try attaching a link to your WA solution instead, though I don't feel that it's necessary. Your code should fail this Test Case (the correct answer here would be 1): 1 5 1 1 1 5 5 2 2 2 2 2 3 3 3 1 1 4 4 4 3 3 5 5 5 4 4 
•  » » » » » » » » » 2 months ago, # ^ |   0 Okay, i will check, But my code is fine you just have to take main function and put a loop inside main for test case. anyway Thanks for help.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Edit-> definitelynotmee already answered it above, Thank you
•  » » » 2 months ago, # ^ |   0 Why do you think your #2 will always pick the right candidate (if there's any) ?
•  » » 7 weeks ago, # ^ |   0 yep I had that incorrect insight too; I should practice more hehe
 » 2 months ago, # |   +4 In Problem D, I wrote down some examples and observed 3 ways to get a YES answer (First of all I converted all the negatives elements to positive because since we have been given differences, the sign doesn't matter) :- 1) If there exists a 0 in the array. 2) If there are repetitions in the array. 3) If there exists more than one subset sum in the array. :)
•  » » 2 months ago, # ^ |   +22 I had the same solution XD The fun part is that I didn't fully understand why would this work but it passed pretests.But if you look at the formula in the editorial and move all the negative elements onto the right hand side of the equation (either because they were negative in the first place, or because $s_i = -1$), suddenly we have the formula we came up with: sum of at least two subsets of absolute values must add up to the same value. It is $O(2^n)$.
 » 2 months ago, # | ← Rev. 2 →   +64 I have an $O(2^n\cdot n)$ solution for D. I don't know why does it work: SolutionGenerate all possible subsequences of a and keep their sums in a set. If the length of the set equals to $2^n$, then the answer is "NO", else the answer is "YES". Don't forget to handle the case when there's a zero in the array! Implementationvoid solve() { int n; cin >> n; vec a(n); cin >> a; set s; s.insert(0); for(int i = 0; i < (1 << n); i++) { int sum = 0; for(int j = 0; j < n; j++) if(i & (1 << j)) sum += a[j]; s.insert(sum); } cout << (len(s) != (1 << n) ? "YES" : "NO") << "\n"; } 
•  » » 2 months ago, # ^ |   +2 Great approach but how it works
•  » » » 2 months ago, # ^ |   0 it is basically same as editorial solution . Let there exist 2 subset A and B which have equal sum then we can take element of A with positive sign and element of B with negative sign so the total sum of subset (A +(-B) ) =0.
•  » » » » 2 months ago, # ^ |   +1 Can you give an example how to construct the array b given two subsets are equal? Thanks.
•  » » » » » 2 months ago, # ^ |   0 Suppose A[] = {5,3,8} then you can generate an array B[] = {5,8,16}, we can generate this because we have two subsets (1,2) and (3) with equal sums.
•  » » » » » » 2 months ago, # ^ |   +1 Thanks. Can you explain the construction for A[] = {-3, 6, 10, 1, 12, 100} subsets (1,2,3) and (4,5) have same sum (-3 + 6 + 10) = (1 + 12) = 13
•  » » » » » » » 2 months ago, # ^ |   +1 I have understood. {0, -3, 3, 13, 1, 100}
•  » » 2 months ago, # ^ | ← Rev. 3 →   +18 The target of this problem is to build an array b that contains n numbers instead of n+1 so that if there are 2 subsets have the same sum S, you can build an array b having n+1 numbers with S appears twice, and you just delete one of it to make an array b have n numbers.
•  » » » 2 months ago, # ^ |   0 Thanku
•  » » » 2 months ago, # ^ |   +12 Thanks!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 you can build an array b have n+1 numbers with S appear twiceCan you explain this line?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +7 We call 2 subsets have sum $S$ with ${a[i1], a[i2], ..., a[ik]}$ and ${a[j1], a[j2], ..., a[jr]}$ We know that these $r+k$ elements have distinct index in $a$ which mean $r+k \leq n$.Let build array $b$ in this way : $b[1]=0$ $(2<=y<=k)$ $->$ $b[u+1]=b[1]+a[i1]+...+a[iu]$ $(k+1<=u<=k+r)$ $->$ $b[k+u+1]=b[1]+a[j1]+...+a[ju]$ For any element in other $n-(r+k)$ elements in $a$, we can easy set to last $n-(r+k)$ elements in $b$. Now we have array $b$ with $n+1$ elements and we also have $b[k+1]=b[k+r+1]=S$. Now just remove $b[k+1]$ to make array $b$ with $n$ elements.
•  » » » 2 months ago, # ^ |   0 Thanks!
•  » » » 2 months ago, # ^ |   0 Hey I used the logic that if there is atleast 1 combination of Ai whose sum is equal to the some Aj then we don't have to make a segment for it and it can be done in n Bi otherwise n+1 Bi will be needed but it is giving me NO instead of YES for this test case. 9 25 -171 250 174 152 242 100 -205 -258 Can anyone explain why it is not working? Here is the code for reference
•  » » » 2 months ago, # ^ |   0 Thanks it helped me a lot
•  » » » 6 weeks ago, # ^ |   0 Thanks, you helped me a lot!
•  » » 2 months ago, # ^ |   0 you can forget to handle the case when there's a zero in the array. Because one of the subsets is empty set and the sum of it is equal zero. so if there's any zero in the array , the length of the set(sum) will be less then number of subsets.
 » 2 months ago, # |   0 I also did problem B in O(nlogn) but i used sorting
•  » » 2 months ago, # ^ |   0 if you used the STL sort then I think it is a UB.suppose A,B,C are any structs that you sort,the STL sort only works when if A>B,B>C,then A must be bigger than C,Otherwise the sorted result might be a complete mess.Sorry for the bad grammar.
•  » » » 2 months ago, # ^ |   0 I used sort with comperator function and also after sorting I iterate over all thing to check weather it holds satisfies condition or not
•  » » » 5 weeks ago, # ^ |   0 can u elaborate more??
 » 2 months ago, # | ← Rev. 3 →   0 Did the setters anticipate non-bitmask solutions to G? It seems that even with some careful book-keeping to avoid performing any $O(n)$ calculations at the critical deepest level of recursion, the time limit is still pretty strict for these solutions.My contest solution (123766099) keeps the non-recursive part of every loop at $O((k+1-i) \cdot (1 + |S_i \setminus T_{i-1}|))$ by following the set and un-set bits to their destinations in advance and attains something close to $O((\frac{n+k}{k})^k)$ performance. (It's technically a bit worse for large $k$, but that's not very relevant to this problem.)
•  » » 2 months ago, # ^ |   0 It is possible, albeit requires some optimization (or, for example, the second observation described at the end of the editorial), to get accepted without using bitmasks.While preparing the problem, I wondered if it was better to give the problem with $n=50$ (which obliged to use bitmasks) or $n=40$ which allows many more solutions to get accepted. At the end I decided to go for the "low-constraints" version since the gap between F and G was already rather big.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +38 I don't think the second observation by itself would have been enough for my own implementation, since the ratio $5^{10} : 6^4 \cdot 5^5 \approx 2.4$ it seems to actually save isn't very big, and my own idea (which I estimated saves a factor of about $40/5 = 8$) didn't yield so much headroom. I should look over the other slow solutions and try to see what ideas they used.It's also very possible that my implementation is just rather slow. But if non-bitset solutions were intended to pass, it seems perhaps a bit strange to keep the time limit at one second.
 » 2 months ago, # |   0 I did problem B using a comparator function 123741857
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Hey, I also used a similar approach(123769494), but I'm not sure how is this working because,If A is superior to B and B is superior to C, then it is not always true that A is superior to C(like in the given test case). This would probably give the wrong sorted order, right?Can you please explain why is it working?
•  » » » 2 months ago, # ^ |   0 Suppose A,B,C,D is the order you get after sorting. Then, D cannot be the answer as C is superior to it, similarly C cannot be the answer due to B, B cannot be due to A. So if any answer at all exist it has to be A.
•  » » » » 2 months ago, # ^ |   +3 Thanks a lot!! Got it
 » 2 months ago, # | ← Rev. 2 →   +22 Typo: The latex in hint 3 for H is currently broken
•  » » 2 months ago, # ^ |   +11 Thanks, it has been fixed!
 » 2 months ago, # |   +3 Is it only me or the "Hint 3" in problem H is bugged?
•  » » 2 months ago, # ^ |   +9 It's fixed now. :)
 » 2 months ago, # |   +245 Don't ever upsolve. If a problem appears at one contest, what is the chance it will appear at another? - Gennady Korotkevich
 » 2 months ago, # |   +14 I have another way to do in problem D. First, if there is some zero in the given set, the answer is YES. Otherwise, consider the absolute values |a1|, |a2|, ..., |an| and check whether there are two distinct subsets of the new set s.t their sum are equal. This can be done in O(n.2^n).
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 deleted
•  » » 2 months ago, # ^ |   0 why is true ?? I cant figure it out ??
 » 2 months ago, # |   0 How is it supposed to solve D in $O(3^n)$? Is it a typo, while the actual complexity is $O(3^n\cdot n)$?
•  » » 2 months ago, # ^ |   +11 You are right! It has been corrected in the tutorial, but it might take some time to render in the blog.
•  » » 2 months ago, # ^ |   +22 I solved it in O(3^N). Precompute the sums in O(2^N) or O(2^N*N) then iterate through the pairs of non-intersecting subsets.
•  » » » 2 months ago, # ^ |   0 I used that approach too (123745577)
 » 2 months ago, # |   +65 Hello authors, Thanks for the great contest, all the problems I read were interesting and entertaining to solve and think about. However, one decision I am confused about is the omission of a max pretest for D. There was no pretest that had 20 test cases of n = 10, and this lead to people FSTing. My solution ran in less than 200 ms on pretests, and so even though I was suspicious of my complexity, I figured that my solution for D was okay, yet it still FSTed. Next time, please include max tests in the pretests so contestants can be rather certain their solution will pass under the time limit.
•  » » 2 months ago, # ^ |   +8 What does FSTed mean?
•  » » » 2 months ago, # ^ |   0 Failing system tests
 » 2 months ago, # | ← Rev. 6 →   +9 Sadly, I got FSTed for D. Interesting problems btw. Kudos!Edit: Can anyone explain why I got TLE for D while the time complexity seems to be n * O(2 ^ n)? 123771731
•  » » 2 months ago, # ^ |   0 rep(i, 0, elements.size()) { rep(j, i+1, elements.size()) { if(abs(elements[i] - elements[j]) == curr) { return rec(arr, idx+1, elements); } } }Just because of this loop your complexity is already at least O(n^2*2^n). There are also 20 test cases. That already puts you at O(10^8). Add any major inneficiency and it's time limit (like what happened).For that solution you could just store everything on a set end check in the end if the size of it is equal to 2^n, you really didn't need to make your life hard. Also cout.tie(0) litterally does nothing
•  » » » 2 months ago, # ^ |   0 Thank you for the explanation. I'll keep these things in mind.
 » 2 months ago, # |   +6 1552C - Maximize the Intersections I still completly do not get why we can ignore the initial chords configuration. The editorials seems to not explain it further. Is that something so obvious?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 It's not obvious, but the idea is that you can consider a pair of new chords separately from any pre-existing chords. Let's say there are multiple chords already drawn, and you now have 4 free points ($A,B,C,D$ in that order), and you must draw two chords. You can convince yourself that the configuration $AB$ + $CD$ intersect the same number (or fewer) previously drawn chords as the configuration $AC$ + $BD$, but since $AC$ and $BD$ intersect themselves, this configuration is better.I hope that it's somewhat clear. It's the usual swapping argument employed in proofs of greedy solutions.
•  » » 2 months ago, # ^ |   0 As there is only one configuration that is giving the maximum we can ignore initial chords. If that is not the case then we can't ignore the initial chords.
 » 2 months ago, # |   +11 "Problems A and B are meant to be easy!" Really?
 » 2 months ago, # |   +3 I had a different approach for problem F:First of all, compress all coordinates so each of them is not greater than $2n$. The solution below uses 1-indexation for compressed coordinates. The original coordinates are kept in array c.Then do some kind of right-to-left dp, let's call it over. over[i] means the number of times the ant goes from point i - 1 to point i. Then the answer is clearly $\left(\sum_{i = 1}^{2n}over[i] \cdot (c[i] - c[i - 1])\right) + 1$.The point is how to calculate the over dp. There are two cases: i-th coordinate is y for some portal p. Then over[i] = over[i + 1] - cnt where cnt is the number of telepantings through the portal p. It can be easily found as over[p.x] - over[p.x + 1]. i-th coordinate is x for some portal p.One can notice that in the half of the cases the ant is moving forward, so over[i] = 2 * over[i + 1] +- 1 (+-1 depends on the initial activity of the portal). You can read the code here (123756889) or herestruct portal { int x, y; bool active; friend istream &operator>>(istream &is, portal &p) { int a; is >> p.x >> p.y >> a; p.active = a; return is; } }; void solve() { autoint n; vector p(n); cin >> p; vector c{0}; for (auto[x, y, _] : p) { c.push_back(x); c.push_back(y); } sort(c.begin(), c.end()); vector what(2 * n + 1); int index = 0; for (auto &[x, y, _] : p) { x = lower_bound(c.begin(), c.end(), x) - c.begin(); y = lower_bound(c.begin(), c.end(), y) - c.begin(); what[x] = what[y] = index++; } mod_int ans = 1; vector over(2 * n + 2); over[2 * n + 1] = 1; for (int i = 2 * n; i > 0; --i) { int j = what[i]; if (p[j].y == i) { over[i] = over[i + 1] + over[p[j].x + 1] - over[p[j].x]; } else { over[i] = over[i + 1] * 2 - !p[j].active; } ans += over[i] * (c[i] - c[i - 1]); } cout << ans << '\n'; } 
 » 2 months ago, # | ← Rev. 2 →   +1 I think I have done problem B in more simple way. All I did is 2-d vector sorting using my own compare function. Compare function code: compare function// size of vector athleteA is 5, result of matches bool myCompareFunction(vector athleteA, vector athleteB){ int A_won = 0; for(int i=0 ; i 0; } Only first athlete in sorted vector will be contestant to be superior. Just have to check that.
•  » » 2 months ago, # ^ |   0 Can you elaborate your logic that how sorting helps in solving this problem!!
•  » » » 2 months ago, # ^ |   0 Because my compare function will automatically bring superior athlete forward.
 » 2 months ago, # |   +3 D can be solved in O(2^n). It's sufficient to check if two subsets have the same sum.
•  » » 2 months ago, # ^ |   0 Can you explain how does this works?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 This works because in a single subarray of B[] we can get at least two elements of A[].
•  » » 2 months ago, # ^ |   0 Shouldn't they need to ne non intersecting as well? For ex-: If we have a1+a2-a3-a4+a5-a6=0 => a1+a2+a5=a3+a4. I think that's why you are telling that the two subsets should have the same sum. But, then won't they also need to be non-intersecting?
•  » » » 2 months ago, # ^ |   0 What do you mean by non-intersecting?
•  » » » » 2 months ago, # ^ |   0 Two sets having no element in common. Like {a1,a2} and {a3,a4} are non-intersecting but {a1,a2} and{a2,a5} are intersecting.
•  » » » » » 2 months ago, # ^ |   +1 Okay, then we don't need to check if they are non-intersecting. Take the example, {a1,a2} and {a2,a5} which are two intersecting subsets which have same sum. a2 is common. so we can find {a1}, {a5} which are two non-intersecting subsets which have same sum. It is same for each intersecting subsets. I hope you understood :D
•  » » » » » » 2 months ago, # ^ |   0 Thanks ! Learnt a new thing!
 » 2 months ago, # |   0 2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/
 » 2 months ago, # |   +30 Alternative solution to 1552F - TelepantingLet $z_i$ be the index of the teleporter reached immediately after using the teleporter $i$ (it can be calculated by binary search). Let $dp_{i,0}$ be the number of times $x_i$ is reached. Let $dp_{i,1}$ be the number of times the teleporter $i$ is used. Then, the answer is easy to calculate (you spend $x_{z_i}-y_i$ time for each teleporter, and if the teleporter is inactive you spend $x_{i-1}-x_i$ time). You can calculate $dp_i$ in decreasing order of $i$ by obtaining it from the recurrences $\displaystyle dp_{i+1,0} = \sum_{z_j=i+1}{dp_{j,1}} + \lfloor \frac{dp_{i,0} + (s_i \oplus 1)}{2} \rfloor$ $\displaystyle dp_{i,1} = \lfloor \frac{dp_{i,0}}{2} \rfloor$As there could be multiple possible values of $dp_{i,0}$, you have to choose the one with the same parity as $s_i \oplus 1$ (because all the teleporters are active at the end). This can be done by using mod $1996488706 = 2 \cdot 998244353$.Submission: 123775629
•  » » 2 months ago, # ^ | ← Rev. 2 →   +26 Nice solution! If I had to guess, I would have said it is impossible to solve this problem without the observation that all portals with $x_i < x$ are active when the ant is located at $x$, but it looks like your solution doesn't require this (only that all portals are active in the end). Thanks for sharing.I'll try to include it in the editorial, provided that the gods of Polygon are in my favor.Edit: Solution added to the editorial (actually explained in a slightly different manner, but hopefully correct).
 » 2 months ago, # |   0 The Key for Problem B is only one will be the winner and he will be superior to everyone! By the way very good questions
 » 2 months ago, # |   +1 One of the best tutorial sections of all time! Though I got demoted to pupil :(, still a nice contest! @cip999
 » 2 months ago, # |   +15 Magnificent editorial! I wish all editorials would be at least as detailed as this!
 » 2 months ago, # |   0 Best Editorial Ever. Would like to have such types of more Editorials :)
 » 2 months ago, # |   +8 I really liked the contest, since it had a lot of interesting and fun problems.For me personally it was a bit sad, that my "solutions" A, B, C & D all passed the pretest without any problems, but later my solution for D failed with a TLE although it only took me ~300 ms to pass the pretests. Since I am new to codeforces, I would like to ask if this is the standard (you are responsible for your own code, so you have to calculate the complexity) or if you normally should be rather safe with a ~300 ms.Great contest! Looking forward to more :)
 » 2 months ago, # |   +19 Thank you for the contest!
 » 2 months ago, # |   -13 bad pretest for B:,(
•  » » 2 months ago, # ^ |   -13 I think so :(
 » 2 months ago, # |   0 Finally I became an International Master after this Round.Thanks to cip999 and dario2994 :)
 » 2 months ago, # |   0 I can come up with a solution to problem B, which is referred to as 3rd Solution.I define a comparison between athlete $i$ and athlete $j$, athlete $j$ is called "greater" than athlete $i$ if and only if athlete $i$ is superior to athlete $j$. After sorting the athletes by this compare, each of them, except the first one, will have at least one athlete that come up before and superior to them.Finally, we check whether the first athlete is superior to everyone else or not.
•  » » 2 months ago, # ^ |   0 actually i also tried this type but in the cmp funtion their i messed up 123750135
•  » » » 2 months ago, # ^ |   0 WRONG bool cmp(vector a, vector b) { int cnt = 0; rep(i, 0, 5) { if (a[i] < b[i]) cnt++; } if (cnt > 2) return a < b; return b > a; } ACCEPT bool cmp(vector a, vector b) { int cnt = 0; rep(i, 0, 5) { if (a[i] < b[i]) cnt++; } return cnt > 2; } 
•  » » 2 months ago, # ^ |   +1 This solution is broken, because it relies on undefined behaviour. The input data and the comparator do not satisfy the transitivity requirement. If A < B and B < C, then A < C must be also true. This kind of violation is similar to relying on a wrong use of <= operator in a comparator (which is known a bit better to the general public).Now I'm not sure if it's really possible to hack your solution in practice. Some implementations of sort could theoretically go into an infinite loop and give you a TLE. The others could crash. Using various combinations of search keywords "transitivity", "sort" "crash", "segfault", "infinite loop" on google shows that bad outcomes happened to be a reality at least in some cases.Just consider yourself lucky and don't do it again. An unintended bad thing about problem B from this contest is that it rewards incorrect code with a positive stimulus.
 » 2 months ago, # |   0 I solved the D problem with a approach different from the editorial . Have a look at it. I find it interesting. 123742321
 » 2 months ago, # |   -10 i got first time +140 in this round XDthe best ever contest for me
 » 2 months ago, # |   +3 The problem C is very very difficult.
 » 2 months ago, # |   +11 Can someone who solved E during Contest explain what went through their mind while solving it? Did you prove the solution u coded ? And what's the first thing came to your mind when u looked at weird ceil(n/(k-1)) constraint?
•  » » 2 months ago, # ^ |   +25 What came to my mind was that there might be a way to split colors into groups of $k - 1$ such that the intervals in each group do not intersect with each other.
•  » » 2 months ago, # ^ |   0 I tried basic strategy on samples + few handwritten tests, and it gave correct answers. I tried to prove but without hope. There was nothing to do. So I've just implemented it. It passed pretests, so even though if it was wrong solution, I didn't care. So if FST would happen I would just "well, shit happens". Ah... it was second solution from editorial.
 » 2 months ago, # | ← Rev. 2 →   0 If there is more than such one athlete, print any of them. Can Someone told me important of this line in Problem B.
•  » » 2 months ago, # ^ |   0 I think they just didn't want to make the observation that there is always at most 1 athlete obvious
•  » » 2 months ago, # ^ |   +15 It's normal question from participant: what if several athletes might be answer, which one output? To avoid giving key hint that it's always unique, this statement is included.Also, there is often statement "Output -1 if there is no solution" in problems that always have solution.
 » 2 months ago, # |   0 Anyone else try doing B with bitmasks?
 » 2 months ago, # | ← Rev. 2 →   0 In problem B I tried defining a class of runners and defined the way for the array of runners to be sorted (Check if first runner has better rank in at least three marathons than the second runner). The test cases passed but I kept getting runtime error on my submissions. Can anyone point out why? Here's my code:123745722Edit: Got it. The relation between runners is not transitive.
 » 2 months ago, # |   0 Can someone tell me why my randomized solution didn't work? https://codeforces.cc/contest/1552/submission/123740930Also I tried copy pasting the solution given in editorial but it got TLE as well. https://codeforces.cc/contest/1552/submission/123800021
 » 2 months ago, # |   0 Can anyone please tell me why I am getting a TLE in my solution of problem B?? 123801888
•  » » 2 months ago, # ^ |   0 Your Solution is correct Just pass your 2D vector to check function by reference and it will get pass ! bool check(vector &m,int j,int k)like this !
•  » » » 2 months ago, # ^ |   0 Thanks bro, Yeah it got AC but can you explain why it was getting TLE??
•  » » » » 2 months ago, # ^ |   0 By default the arguments are passed by copy. Every time you call that function, the vector must be copied. But you don't need that, you pass it by reference so it won't be copied, it will use the original vector
•  » » » » » 2 months ago, # ^ |   0 Thanks bro
 » 2 months ago, # |   +8 Federico in B made me think about Federico Chiesa. LOL :)). Anybody have the same imagination?
 » 2 months ago, # | ← Rev. 3 →   +3 I think I have an interesting and easy-to-understand solution for B. Here's the idea: Keep a knockout style tournament Each player will play 2 other players ( n-1, and n+1) Only those players who have won both their matches will advance to the next round Eventually, only one person will remain. (Possible winner) To check if he's the actual winner, see if he's superior to all other players. Example: First round -> 1, 2, 3, 4, 5, 6, 7 Second round -> 2, 4, 6 (2 won against 1,3; 4 won against 3,5; 7 won against 6,1) Third round -> 6 (Only 6 won against 4,2) Now, apart from 6, all other players have lost at least once, so they can't get the gold medal. The only thing remaining is to check if 6 is superior to all 6 other players. Code: https://codeforces.cc/contest/1552/submission/123742601 Complexity: O(n*logn)What are your thoughts?
•  » » 2 months ago, # ^ |   -10 Amazing way of explaining ! This approach will help me in future
 » 2 months ago, # |   0 For the problem B please add the two pointers tag as well. The situation in the problem is like a knockout tournament where one who loses a match would be eliminated and at last only one player would be left. Then simply check if this player can defeat all other players or not. If yes the answer is YES else NO. The time complexity is O(n). code
 » 2 months ago, # |   0 Can someone please share the code for D using knapsack!
 » 2 months ago, # |   +10 tourist is Lionel Messi of cp. GOAT.
 » 2 months ago, # |   0 Can anybody share the O(nlogn) algorithm mentioned in problem C solution?(=-=)
•  » » 2 months ago, # ^ |   0 Can Binary Search be applied? I could not come up with required O(NlogN) solution, but this may help someone You might have already thought about this Take vector> of all the chords, [ix,iy] Sort them according to ix Two conditions for chords i andj to intersect:iy > jx and iy < jy First condition(iy > jx) can be handled by binary search (upper bound). Helpful in reducing size of nested for loop, still O(N^2) But don't know how to handle second condition and take direct count. Somebody help
•  » » 2 months ago, # ^ | ← Rev. 2 →   +5 Submission Let's have two ranges [a,b] and [c,d] such that a
 » 2 months ago, # |   0 nu cuoi da tat vi mim qua dak
 » 2 months ago, # |   0 Best Editorial I have seen ever, thanks
 » 2 months ago, # |   0 I've seen some solutions for E that do not seem to explicitly check for the ceil(n/(k-1)) constraint and greedily make "n" passes over the array and on each pass tries to pick disjoint intervals whenever it can. (Here's a sample submission that does this). Does anyone have a proof that this won't violate the ceil(n/(k-1)) constraint ?
 » 2 months ago, # | ← Rev. 2 →   0 .
 » 2 months ago, # |   0 Why I am getting TLE in B .It is stillO(N). Spoiler... Your code here... #include #define ll long long int using namespace std; int get_sp(vector>a,int n,int index) { int sp=0; for(int i=0;ia[index][j]) c1++; } if(c1>=3) sp++; } return sp; } int find_sp(vector>a,int k,int i) { int c1=0; for(int j=0;j<5;j++){ if(a[i][j]=3) return i; else return k; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--){ int n; cin>>n; vector>a(n); for(int i=0;i>b; a[i].push_back(b); } } int arr[n]={0},x=0; int sp; for(int i=1;i
•  » » 2 months ago, # ^ |   0 You are calling the get_sp and find_sp as call by value and because of this the data copying is taking a lot of time. Instead , call the function by using call by reference methodology. Also, there is no meaning of calling the get_sp function again, you have already stored it's output in b variable (although it won't cause tle). Tuned Solution for reference(123892742)
 » 2 months ago, # | ← Rev. 3 →   +10 O(N log N) solution for problem C:I used indexed set but could also be done using segment tree. Spoiler #include using namespace std; #include using namespace __gnu_pbds; typedef tree,rb_tree_tag,tree_order_statistics_node_update>indexed_set; #define forn(i,m,n) for(ll i=m;i #define ii pair #define vii vv #define mp make_pair #define pb push_back #define PI 3.141592653589 #define ll long long #define pll pair #define vl vv #define ff first #define ss second #define MOD 1000000007 ll max(ll a,ll b){ return a>b?a:b; } ll min(ll a,ll b){ return a>n; indexed_set st,st1; //for maintaining unused points for(int i=1;i<=2*n;i++){ st.insert(i); st1.insert(i); } int k;cin>>k; vector> v; //for chords priority_queue>> pq; //(distance points between end points,(points)) for(int i=0;i>a>>b; v.pb({a,b}); pq.push({-min(abs(a-b),2*n-abs(a-b)),{a,b}}); //negative sign to maintain shortest chord on top of pq st.erase(a); st.erase(b); } for(int i=0;i x=pq.top().second; pq.pop(); int a=st1.order_of_key(x.first); int b=st1.order_of_key(x.second); int intersects=min(abs(a-b)-1,rem_pts-(abs(a-b))+1); ans+=intersects; rem_pts-=2; st1.erase(x.first); st1.erase(x.second); } cout<>te;while(te--) solve(); } 
 » 2 months ago, # |   +21 Seems like sansen is hacking everyone's G and most of them are failing with TLE, does that mean the system tests were weak? Sorry if I'm getting this wrong
•  » » 2 months ago, # ^ | ← Rev. 3 →   +18 Actually I am curious about that. I had worked pretty hard to make the tests decent (both to fight against randomized solutions and to fight against slow solutions), but I must have failed if $\ge 10$ solutions out of 50 are hacked. Please sansen explain your trick.
•  » » » 2 months ago, # ^ |   +48 Most of the hacked submissions are dp-like solution. The complexity is the same as Editorial, but it uses a lot of memory and has a large constant factor. However, in the prepared testcase, there were a lot of state collisions, so it was very fast.
 » 2 months ago, # |   0 problem E,why can construct it? I don't understand.who can help me?
•  » » 2 months ago, # ^ |   0 What didnot u understand? I can try to explain it to u.
•  » » » 2 months ago, # ^ |   -20 can you speak Chinese? ,my English is not good,but I accept English, my question is why can prove two intervals selected in different steps are disjoint,programme is understanded for me,but why?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Xi,s+1Xj,s+1 we have took j first ans then i. Xj,s+1 <= Xj,t because s
 » 2 months ago, # | ← Rev. 2 →   0 In problem E [n / (k-1)] can be 0, if k — 1 > n. In this case there is no answer, but "One can show that such a family of intervals always exists under the given constraints." Help me, please.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 got it
 » 2 months ago, # | ← Rev. 2 →   0 Can someone explain why do we swap c and d in the intersect function in problem C Is that done to cover the part 1 of the tutorial can someone clearly explain it please Just the second line of the intersect fucntion is enough to check the intersction is happening or not right?? why do we swap c and d??
 » 2 months ago, # | ← Rev. 3 →   +33 Interesting observation in Problem E I haven't seen mentioned yet. One can look at the special case $n=k-1$. Then we have the case, that each number belongs to at most $1$ interval. We can solve this and use the solution to solve the general case. In the general case we have $n$ and $k$ and at most $\left\lceil \frac{n}{k-1} \right\rceil$ intervals. Then we can split up the $n$ numbers arbitrary into $\left\lceil \frac{n}{k-1} \right\rceil$ separate groups with each containing no more than $k-1$ numbers, and solve each group separately. (I guess, this is the meaning behind hint 1.2)This isn't the best way to implement the solution, but this train of thought really helped me to come up with a solution.
 » 2 months ago, # | ← Rev. 2 →   0 Can B problem be classified as some sort of Celebrity Problem ?
 » 2 months ago, # |   +5 Can someone explain this part of greedy solution for problem E: We can say more: the rightmost endpoints of these intervals must belong to $[x_{i,j}, x_{i,j+1}]$; indeed, if it weren't the case for at least one interval $[a, b]$, the interval $[x_{i,j}, x_{i,j+1}]$ would come before $[a, b]$ in the ordering, so it would actually have been selected. I agree that interval $[x_{i,j}, x_{i,j+1}]$ would come before $[a, b]$ in this case. But we might not select it based on requirement #2. Am I missing something?
•  » » 2 months ago, # ^ |   +5 The contradiction is exactly what happens if we don't choose any segments because of requirement #2.For each of the k-1 segments we could choose there was already (n)/(k-1) segments that had their right endpoints inside of [xij,xij+1] (otherwise, it would come before in the ordering and be choosen instead). That way there should be (n)/(k-1)*(k-1) distinct segments, or n segments for n-1 colors, leading to a contradiction.
•  » » » 2 months ago, # ^ |   0 He was asking why $[x_{i,j}, x_{i,j+1}]$ must have been selected if it comes before $[a, b]$.
•  » » » » 2 months ago, # ^ |   0 And i was answering that. Funnily enough i think we both said the same thing with different words
•  » » » » » 2 months ago, # ^ |   0 My bad. I didn't fully understand your comment so I wrote my own. Just reread yours and it's much clearer now.
•  » » » 2 months ago, # ^ |   0 Took me an hour to understand the explanation :D I finally did! Thank you!
•  » » 2 months ago, # ^ |   +8 I think the author meant we can always find $\left\lceil \frac{n}{k - 1} \right\rceil$ intervals with their right endpoints inside $[x_{i,j}, x_{i,j+1}]$. If it were not the case, at the time we considered $[x_{i,j}, x_{i,j+1}]$, we would have selected it.Now for each of the $k-1$ intervals for color $i$, we have $\left\lceil \frac{n}{k - 1} \right\rceil$ distinct intervals. In total, we have $(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$ distinct intervals, leading to a contradiction since we can not have $n$ intervals for $n-1$ colors.
 » 2 months ago, # |   0 in problem B, any two pairs, one must be superior to the other, right?
•  » » 7 weeks ago, # ^ |   0 Correct
 » 2 months ago, # | ← Rev. 2 →   0 I solved problem C differently.Suppose, total numbers of point is 2n, and there is an unselected point say, P. There is also an array usp[2n+1] where usp[i] contains the total number of unselected points before i th point.If I can find another unselected point x > P such that value of min(usp[x]-usp[P],total_unselected_points — usp[x]) is maximum, then we can connect P and x. We can do this for all unselected points from 1 to 2n, which will lead to the optimal configuration.My Submission
 » 2 months ago, # |   0 Why the wrong answer for the submission?submission
 » 7 weeks ago, # |   0 however you choose 3 chords that connect 3 disjoint pairs of points, no point strictly inside the circle belongs to all 3 chords. what does this means?
•  » » 7 weeks ago, # ^ |   +1 That means if you choose any 3 chords, they won't intersect in a single point (like this: "Ж")
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 even if they intersect at a single point, i think the number of intersection remains the same
 » 7 weeks ago, # | ← Rev. 2 →   0 Especially problem D was great.
 » 7 weeks ago, # |   0 Can someone tell me the $O(3^{n/2})$ meet-in-middle solution for D?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 we want to check if there is some mask with sum == 0, we can split the array in two and for every mask in the first half with sum = x, we check if we can make sum = -x with the second half. of course if we can make sum = 0 using the first half only or the second half only we are done. you can check my code 124122316
 » 7 weeks ago, # |   +20 You have nice problem ideas. You have good English skills. You are devoted to the thing you do. Although I just do the virtual contest (and solved only A), I can say: "Nice problemset!" Thank you very much, sir!
 » 7 weeks ago, # |   0 What does the anti-random case look like on problem G?
•  » » 7 weeks ago, # ^ |   +18 Here is how to construct an anti-random case.Choose "reasonably" the first $k-1$ sets $S_1, S_2, \dots, S_{k-1}$ (reasonably $=$ each element belongs to at least one such set, they are not sufficient to sort); then execute the solution for this family. You will get a family of $(k-1)$-achievable functions. As in problem A of the contest, for each of them you identify the minimal subsequence that needs to be sorted and you compute the union of these sets. This yields a set $Z$. Notice that for the family $S_1,S_2,\dots, S_{k-1}, Z$ the answer would be ACCEPTED. Now, you remove from $Z$ the element $z\in Z$ which minimizes the number of $(k-1)$-achievable functions whose "minimal subsequence that needs to be sorted" contains $z$. Notice that for the family $S_1,S_2,\dots, S_{k-1},Z\setminus{z}$ the answer would be REJECTED.Now you execute your favourite random solution (the most efficient one seems to be the one which simply tries random permutations). If, after $2$ seconds of computation it cannot find any permutation which is not sorted by $S_1,S_2,\dots, S_{k-1},Z\setminus{z}$ then you have found your anti-random case. Otherwise, you start again.
 » 7 weeks ago, # |   0 Why is the Task I a recurrence of 243E - Matrix? What a shame.
 » 7 weeks ago, # | ← Rev. 2 →   +10 The solution to I contains a bug. Observe that the set $I$ is nonempty. Let us consider various cases: This doesn't necessarily hold. For example, if $(Z_1, \ldots, Z_3) = (\{1\}, \{2\}, \{3\})$ and $S = \{1, 3\}$, we have $I = \emptyset$.This is not a critical one though. One can easily extend the solution's idea to the case of $I = \emptyset$ (and it's done in my submission: https://codeforces.cc/contest/1552/submission/124438016)
•  » » 7 weeks ago, # ^ |   +10 Thank you for spotting the mistake in the editorial. Fixed.
 » 7 weeks ago, # |   +8 My solution for H isn't based on any proof, only on the expectation that a lot of queried sets will give different answers for different shapes. I don't believe there's a single test where this doesn't hold.Naturally, I start with finding $ab$, where $a$ and $b$ are the number of rows and number of columns of points belonging to the rectangle (why bother with writing $+1$). I find all candidate pairs $(a,b)$; quick testing shows there's at most $26$ of them, so we only need each query to select up to 1/3 of current candidates to succeed.Let's pick a set where possible answers for each $(a,b)$ are simple to find. I go for some integers $d_a$ and $d_b$ and points $(x,y)$ where $d_a | x-1$ or $d_b | y-1$: rows with spacing $d_a$ and columns with spacing $d_b$. A rectangle with $(a,b)$ will cover $\left\lfloor \frac{a}{d_a} \right\rfloor \le k \le \left\lceil \frac{a}{d_a} \right\rceil$ of the selected rows and $\left\lfloor \frac{b}{d_b} \right\rfloor \le l \le \left\lceil \frac{b}{d_b} \right\rceil$ of the selected columns. That's up to $4$ answers, each is $bk+al-kl$.For each query, I try all possible $d_a$ and $d_b$, since there are just $40,000$ of them. For each of them, I find all possible answers for each remaining candidate $(a,b)$, then find the answer that corresponds to the largest number of candidates. I pick $(d_a,d_b)$ which minimises this maximum, ensuring that the number of candidates remaining after the query is small even in the worst case. I ask the query and filter candidates that can give the answer returned by the judge. It works!
•  » » 7 weeks ago, # ^ |   0 Very nice solution!
 » 6 weeks ago, # | ← Rev. 2 →   +9 Very nice problems!
 » 5 weeks ago, # |   0 In problem B can anyone give me test case where we have more than one potential candidate as winner?