In the case of $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersecting for the case $$$k = 3$$$, the idea that we could have finished in 2 operations by taking the union is not correct. Thanks to xyzt8988998 for reaching out with the mistake. The right claim is:

Claim: If the ranges intersect then there is either a prefix or a suffix that has as many 1 as 0.

First of all, since after applying $$$[l_1, r_2]$$$ the range is compressed into one element, if $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect, then $$$l_2 \leq l_1$$$ and $$$r_1 \leq r_2$$$.

• If $$$l_2 \gt 1$$$ and $$$r_2 \lt n$$$ then either the prefix $$$[1, l_2 - 1]$$$ or the suffix $$$[r_2 + 1, n]$$$ has as many 1s as 0s. Otherwise, no matter what would be the majority value in $$$[l_2, r_2]$$$, the third operation will have strictly less 1s then 0s and we could not have finished in 3 operations.
• If $$$l_2 = 1$$$ or $$$r_2 = n$$$, without loss of generality, let's assume that $$$l_2 = 1$$$. When $$$r_2 = n$$$, the same arguments can be applied just by reversing the string. If (after applying operation $$$[l_1, r_1]$$$) the majority element in $$$[1, r_2]$$$ is 0, suffix $$$[r_2 + 1, n]$$$ has strictly more 1 then 0, since we finished in 3 operations. However, then we could have completed this case in 2 operations instead. Hence, $$$[1, r_2]$$$ has majority value as 1 (after applying $$$[l_1, r_1]$$$). Also, observe that since we finished in one operation after applying $$$[l_2, r_2]$$$ and it had 1 as majority value, let $$$x$$$ be the number of 0s in the range $$$[r_2 + 1, n]$$$ then the number of 1s in the range is at least $$$x - 1$$$.
  • If the majority element in $$$[l_1, r_1]$$$ is 1, then the majority element in $$$[1, r_2]$$$ is 1 (in the initial string). Our claim in met.
  • If the majority element in $$$[l_1, r_1]$$$ is 0, then again either the prefix $$$[1, l_1 - 1]$$$ or range $$$[r_1 + 1, r_2]$$$ has strictly more 1 than 0.
    • The first case can not happen, from the same thought process as above.
    • The second case, when the range $$$[r_1 + 1, r_2]$$$ has strictly more 1 than 0, let y be the number of 1s. Then number of 0s is at most (y — 1). Then the number of 1s in $$$[r_1 + 1, n]$$$ is at least $$$y + x - 1$$$ and number of 0s in $$$[r_1 + 1, n]$$$ is at most $$$x + y - 1$$$. Therefore, the suffix $$$[r_1 + 1, n]$$$ has as many 1s as 0s. Our claim is met again.

You can look at cases which operations could have been applied and come up with sufficient and necessary conditions for those cases.

If $$$k = 2$$$, then some operation $$$[l, r]$$$ was applied after which the operation was applied on the whole string. Suppose that the majority value in $$$[l, r]$$$ was 1. Then we can show that we could have finished in one operation. Therefore the majority value in $$$[l, r]$$$ must have been 0. Let $$$z$$$ / $$$o$$$ be the number of zeroes / ones outside $$$[l, r]$$$, respectively. Then $$$z + 1 \leq o$$$ or in other words $$$z \lt o$$$, since we finished in one operation after applying $$$[l, r]$$$. From here you can show that either prefix before $$$l$$$ or suffix after $$$r$$$ has strictly more ones than zeroes. Similarly, with this condition on prefix/suffix you can show that you can finish in 2 operations. Hence, these are sufficient and necessary.

If $$$k = 3$$$, two operations $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ applied before finishing with operation on the whole string. Let $$$[l_2, r_2]$$$ represent the range applied in the second operation corresponding to the range from the initial string. We can consider two cases here:

• If $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect, then we could have taken the union of the ranges instead as one operation and finished in 2 operations instead. We can show this by considering the cases of majority values in these ranges.

• If $$$r_1 \lt l_2$$$ (i.e. ranges do not intersect), then with the similar argument as above, if at least one of the operations had 1 as majority, we could have finished in 2 operations. Hence, 0 was the majority value in $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$. Let $$$z_l$$$, $$$z_m$$$, $$$z_r$$$ denote the number of zeroes in ranges $$$[1, l_1 - 1]$$$, $$$[r_1 + 1, l_2 - 1]$$$ and $$$[r_2 + 1, n]$$$ respectively. Similarly, let $$$o_l$$$, $$$o_m$$$, and $$$o_r$$$ denote number of ones in the same ranges. Then $$$z_l + z_m + z_r + 2 \leq o_l + o_m + o_r$$$. Which means that either $$$o_m \geq z_m + 2$$$ or $$$o_l \geq z_l$$$ or $$$o_r \geq z_r$$$. Since we can show that if these conditions hold we can finish in 3 operations, just by removing one of the operations from case with 4 operations, we have showed that these are necessary and sufficient conditions.

Hope it helped. Feel free to ask any questions if some parts are unclear.

I personally think dynamic programming approaches are more intuitive due to the step-by-step structure of the dynamic programming. Similar to proofs using induction, the idea of computing the answer for $$$n - 1$$$ steps and understanding the relationship between consecutive steps, hence being able to compute the next step makes a lot of sense. I think in general it is just more intuitive to more people. If you understand what you need to compute, then the relationship and transition between states also makes sense.

It just seems to be less abstract and less general. You don't need to understand every case of the problem, you can break it down into few cases and resolve them using the answers for "previous" step. While in greedy ideas, often understanding more general and abstract ideas and structure of the problem play key role. Since you need to understand the problem very well in order to understand the correctness of greedy approaches, it seems harder to come up with.

I personally think, teaching any kind of idea or approach in a simple manner stems from asking the right questions and "teaching" how to ask the right questions. For example, often in dp problems the right question might be, if I know the answer for case $$$n - 1$$$, can I compute the answer for $$$n$$$? Is there some sort of structure between steps and how can I use it?

For example, in LIS(Longest Increasing Subsequence), if I know the answer for first $$$n - 1$$$ elements, I can't easily compute the answer for $$$n$$$. However, any LIS among the first $$$n$$$ elements either

• contains the $$$n$$$-th element or
• is the LIS of first $$$n - 1$$$ elements. So we can understand the connection between consecutive steps. What happens if I remove the $$$n$$$-th element from LIS in the first case? Then, it has some last element among $$$1 \ldots n - 1$$$. So on and so forth with the right questioning and most of the questions you have listed are resolved with an answer.

I am not a teaching expert, but I believe, if you ask the right questions to the student and let them think for themselves and try to navigate (maybe help a little) their thought process through those questions, it will help them understand the topic more easily.

Finally, just a thought: the issue you are facing might be related more to the student’s lack of interest than to their intuition. I think that when a student is genuinely interested in a topic, intuition often follows naturally. Although I am not confident with my the last claim :)

My bad, I meant “weak samples”

I think in problem C, finding and understanding the case where the obvious greedy solution does not work is the major part of the problem. So if the sample test shows this case, major part of the problem becomes obvious. Therefore, I believe, the case is not included among the sample tests. I think it is not fair to call this instance "weak samples".

Sounds like a challenge.

The correct answer is 4, with possible pairs

(2, 4)
(3, 7)
(5, 8)
(6, 9)

Consider the following test

9
1 2 1 4 5 1 7 8

Slope trick is just optimization of dynamic programming in case when function is convex and linear. I think if you view the problem from this point, it is apparent how the ideas work together?

Participate in more contest.

Finally found someone with same opinion on F. Though I didn't solve it during the contest because I suck at coding, I thought of the solution while reading the statement.

If it has become pointless, what was the point of it before?

I think doing 5 hour IOI style virtual contests helps a lot. That way you can get used to the duration and be more comfortable. One thing I did was to record the screen and camera during the contest and analyze it afterwards. If I did something wrong, try to find the reason and improve in the next one. Through this kind virtual contests I came up with a strategy which optimized my performance. The strategy is divided into 2 parts, first 2 hours and the last 3 hours.

First 2 hours of the contest is broken down into 3 blocks of 40 minutes which I spend reading the problem 1-3 respectively and trying to get some easy subtasks (usually 1 — 3) and familiarize myself with the problem. I would sometimes come up with some ideas for bigger subtasks during this period, but as soon as 40 minutes past I switch to the next problem. Even if I have 0 points or have some amazing idea for the latter subtask or even full. After reading all the problems and getting simple subtasks (3 hours remain), I choose a problem which seems the easiest and try to get more points on that problem. By this time usually I have some raw ideas for bigger subtask and try to polish it and get the point.

Being strict with the time management helps to not be stuck on some problem for a long time. I had an incident on IOI23 where I misread the problem A in the beginning of the contest. At 40 minutes I had 0 points on A and no idea how to solve the subtask 1. I moved to next problem and after getting points on the problem B and C, I returned to A with clearer mind and decided to reread the statement. Realizing my mistake, I only had enough time to get first few subtasks. Although the strategy does not guarantee best performance, I personally think its better for me compared to improvising during the contest.

I don't have a strict strategy for the last 3 hours of the contest. I think by doing a lot of virtual contests you can get natural feel on what is the best way to spend this time. If at some point I get hard stuck on anything, the general tips such as going to the bathroom, having some drink or a snack and just going away from the table for a minute or so usually helps. Doing this after the part 1 helps to refresh your mind as well.

In general, I think the best advice I can give is to do virtual contest. Everything else is supplementary. Good luck on the team selection test.

https://ranking.comprog.art/

KAIST slowforce: aimoon + cunhenry01

Third team member couldn't compete.

Is there a typo in solution for problem G?

Any greedy approach to general graph coloring problem will be doomed to fail. Since general graph coloring problem is NP-Complete, you can not solve it in polynomial time, unless P = NP. In this type of problems most probably you have to build certain construction for specific type of graph. In this case we need to use the fact that complete bipartite graph is given.

In my approach I did the following. Think about each color separately, and try to use certain edges for this color such that the graph induced by these edges does not contain a cycle, i.e. is a forest. Then you try to cover the whole set of edges using these forests for each color.

If n < m your solution does not find the answer. While answer exists in some cases. Consider n = 3, m = 4.

YES
1 3 3 2
1 1 3 3
2 1 1 3
2 2 1 1
3 2 2 1
3 3 2 2 

Agreed. Problems felt refreshing with tough but not impossible ideas. Haven't felt like this after the contest in a while. It even makes me want to upsolve the contest :)

I used to listen, but I realized now that I do better when I don't listen to music. Sometimes when I don't think and just code I like to put on some fast-paced heavier music.

Obviously Mike won, he has the DAD strength.

The greatest carrying the team moment in the history.

Greeting everyone from beautiful lake of Issyk-Kul in Kyrgyzstan!! There are 3 members of Kyrgyz IOI team on this photo. Guess who is who :) Btw, I made the delegation team and can't wait to meet everyone on the IOI. Share your team photos too!

Yeah definitely, we should!! :D Will you come to IOI 24?

We have only 11 grades in Kyrgyzstan and I went to school one year early. So yeah, last year was my last chance, despite me being 17 right now. However, this year I will hopefully be in Kyrgyz IOI delegation and help out guys to get the first gold for Kyrgyzstan. Good luck to contestants from all countries.

I think that CF rarely correlates with IOI. To do good at IOI the best option is to do a lot of IOI style problems. I mean, of course if you are 2700+ rated, than you will probably do good at IOI. However, if you are lower rated and want to do good at IOI, training just for IOI is more optimal.

I think these things helped me to become better at IOI style contests:

• Finishing most of USACO silver and gold problems.

• Training on AtCoder problems.

• Trying different IOI style olympiads on oj.uz. I think JOI problems are very helpfull, because they are interesting and challending. Last year 3 out of 6 problems on IOI were proposed by Yoneda brothers from Japan. Therefore, I think it's a good idea to train on JOI contests.

Not pointing any fingers, but I think you are underestimating someone

GL&HF everyone. Hope our streak with Kitsune will be continued.

Kyrgyzstan's IOI 23 team:

• Tengiz Bekkoyonov (Kitsune) — 0 attempts left

• Alihan Aidarbekov (Alihan_8) — 2 attempts left

• Baytoro Mayrambekov (Baytoro) — 1 attempt left

• Aidar Munduzbaev (aimoon) — 0 attempts left

Why isn't it dementia 2022?

Even though I didn't solve F during the contest, I solved it afterwards. I solved for x axis and y axis seperetly. When I solved let's say for example for the x axis, I just run simple bfs, and checked if it's possible to reach $$$i^{th}$$$ coordinate in even or odd moves. And at the end I check if it's possible to reach both $$$t_x$$$ and $$$t_y$$$ in even or odd moves, and if the number of moves for some of them is smaller, then I just repeat any move twice to equalise the number of moves.

UPD: Now you can solve problems in group ACM Kazakhstan.

I was looking for different cases to find my mistake in the solution for the problem B2. I spent like an hour or so writing stres to check, and I accidently realised that I didn't print $$$":"$$$ in some of the cases. I had a lot of this kind of stupid moments on different contests on codeforces and even on IOI, but I guess this is my biggest and at the same time so tiny mistake. I feel so dumb right now. I guess this will be a big lesson for me, so that I won't make any this type of stupid mistakes from now on. Be very careful reading the problem and looking at the output format, and hope my story helped you.

here is the difference between correct and incorrect solutions.

Ohh, that's nice. I didn't think about that. But still, why my solution where I went through each kids passed for full.

It passed 6 minutes since I posted this comment, and while I was rewatching my screencast video, I found one more mistake. I need problems to be posted somewhere for upsolving, so I can check if this was the reason my code failed. Please release them as soon as possible.

Hi everyone. IZhO is finished, and I want to share with my experience on this contest. I got 353 points (100/ 100/ 30/ 51/ 67/ 5). Sorry if I will make a lot of mistakes, it's 4 at night, and I'm writing this comment just because I'm bored. So, let's start.

• Problem A of the first day. I got 100 points. It was pretty good problem for it's place as the easiest of the first day. It's not too hard, yet not that easy. You need some observations and simplifications to solve it. Points distribution was good. The full soltuion reminded me of the problem Farmer 2. I ain't got much to say about this problem.

• Problem B of the first day. It was interesting problem in my opinion. First I quickly got first subtask. Then started solving for the line. I kind of moved my root through the tree, and when we more rood from position $$$i$$$ to position $$$i+1$$$, the only 2 subtrees that changes in the first tree is the sizes of the subtrees in $$$i^{th}$$$ and $$$i+1^{th}$$$ positions. So I can recalculate the subtree size for them, and for the next tree we need to keep the answer for all possible roots, we can do it in the segment tree. To do so, we need to look at the case when for the duplicate for the $$$i^{th}$$$ vertex, it's on the right or on the left or the root. We need to consider this two cases and calculate the subtree size in different cases and according to that update the answer for the possible roots to the left of it or to the right. After I solved for the line, I thought I came up with the full solution. But then realised that my soltion works in the $$$O(\sum deg^{1}_{a} \times deg^{2}_{a} \times log(n))$$$ (let's say that $$$deg^1_a$$$ is the degree of $$$a$$$ in first tree and $$$deg^2_a$$$ is in the second one) complexity. Each time I moved from let's say parent $$$p$$$ of the vertex $$$v$$$, I needed to go through all the kids of $$$p$$$ in the second tree. So in the worst case it's $$$O(N^2log(N))$$$. So I kind of got upset. But I still tried it to get 4th subtask, because maximum degree of the vertex in this subtask is $$$3$$$. After I submitted it passed for full. I was surprised and confused if I calculated the complexity correctly. I thought a win is a win, so I didn't spend much time on this and passed to the next problem. I may be wrong, but I think that test data was week. Let me know if you wrote similar solution and it also passed for full. Also, I came up with the $$$N\sqrt{N}log(N)$$$ solution, uptimizing times where we need to update the tree. It might somehow pass for the second subtask, but I doubt it.

• Problem C of the first day. Maybe I was tired after previous two problems, or was very happy to get 100 on two problems in one day of the contest, I'm not sure. But I didn't felt like solving this problem and just got 30 points and I was done. Or I just didn't like this problem. Also I was sick on both days, so that may be the reason I didn't want to solve this problem.

Any way I finished 13th (with like 10 people having the same points as I got). So I needed to do good in second day, in order to keep my position.

Next day, when I woke up my throat hurt a lot. So I took some medicine from my teacher, and 2 hours before the contest, I started feeling sleepy. Fortunately, at the beginning of the contest, my mind cleared, after I started solving problems. Also 2 hours before the contest all our participants received message with the problems of the second day in math and physics. After like 5-10 minutes, the link to the access to the problems was closed. I thought that second day may be postponed because of this, but organizers simply said to maintain academic integrity. This was very weird. I guess they tried to send this message to the translators for the international participants, but they accidently sent it to the participants. Anyway, let's talk about problems.

• Problem A of the second day. I solved it for 51 points. I think it's an interesting problem. I think after I solved it for 51 points, I came up with the solution for the 63 points. But I thought like, I will probably spend like 15 minutes writing this segment tree, while I already spent an hour, so I decided to move to the next problem.

• Problem B of the second day. I got 67 in this problem. When I started solving this problem I misunderstood problem, and spent 35 minutes on it. After I submitted my code for first subtask, it got 0. So for some time I tried to find the bug in the code, but I couldn't. And then, I reread the problem statement, and finally understood that I was solving totally different problem. Then I quickly changed the code, and got the first subtaks. I came up with the solution for the case where they choose just start the game, without doing any moves. I coded solution for the line, writing some of the part of the solution for the tree. But I had some stupid bug, and I wrote the solution just for line, and stresstested using it as the brute force solution. After getting points for line, I changed some parts of the code to get the points for the tree. But this solution also contained some bugs, which were pretty stupid as well, so I needed to code the solution for the $$$n, q \leq 10$$$, and stresstest using this solution. And finally after getting 56 points(it was already 4:15, I had like 45 minutes till the end), I decided to finish this problem for full, I didn't even read the problem C, but I had 44 points left in this problem, and clear solution in my mind (I thought it was crystal clear at the time). So after changing solution for full, I got 67 points. So it passed for little tree, but it didn't for the big one. I tried so hard to find some bugs or cases I didn't take into account. I found some, and fixed them, but it still didn't pass. When 20 minutes left, I decided to get at least few points in the problem C, and gave up B.

• Problem C of the second day. I rushed to problem C, read it really quickly, and got 5 points. I did what I could in this 10-15 minutes I had. Also, since I was in a rush, my mind didn't work clearly, so I couldn't get any more points.

And that's how my contest ended. I was unsure with my position in the ranking, but obviously I hoped for good position in top 30 (usually they give gold to top 30). I was very nervous but the next day morning my coach sent me the message that I'm 22nd, and I was very happy. I'm happy with my performance, although I think I could have done a little better. I still don't understand the problem in my solution for the B of the second day and why my $$$N^2log(N)$$$ solution for the B of the first day passed. Anyway, I am waiting for the problems to be posted in the ACM Kazakhstan group or in the oj.uz. Congratulations if you achieved your expectations, if you didn't, it's the experience which worth the most, so keep up the work, do your best in the next one. It was my last IZhO, so thank you for reading this story and bye.

Guys, did you receive problems in math and physics of second day?

Among whom I know, from Kyrgyzstan

• aimoon
• Kitsune
• Baytoro
• moday
• Relice
• Alihan_8
• 101degrees
• 10g0
• Cutebol

will participate

link

You can check my solution, I think it's pretty easy, and the code is short.

Kyrgyzstan team is confirmed

In div1E part where we calculate answer

Why

Thanks for solution. I had the first idea at the beginning, but could not improve. Didn't see that number of segments does not exceed O(N), and that they don't intersect. Very cool solution.

Yeah, I also thought of this solution, cause a similar problem appeared in 2017 APIO, it was called Rainbow. But I thought that our graph might not be connected. So I solved it differently.

I made a segment tree that maintains answer and for cells in the rightmost and leftmost column, which component they belong to. It was slow, but using some optimizations it passed. Here is the code.

standings of day 1 + day 2

standings of day 1

I think it's SPFA, Shortest Path Fast Algorithm. It will run in approximately O(N + M). It doesn't get TL because it's hard to construct a good graph.

Thank you

Problem B was interesting for me. I didn't manage to solve it during the contest, but after it, my friend (Kitsune) told me his idea for it, which he couldn't implement during the contest.

When we put same number on indexes $$$i$$$ and $$$j$$$, this must hold

Or we can say like this

So if we take all indexes from 0 to 2 * n - 1 modulo m, then we need to divide them into n pairs with the above condition. First of all, let's group indexes with the same value modulo m. For example if n = 3 and m = 2, we have indexes

if we take values modulo m, then it will become

and we will group indexes with the same value,

So now, we have ranges with the same value, and for some elements, we can't choose its pair from its own range, and we can do dp with it.

dp states will go like this

dp[i][j] = number of variants if we match sets from 1 to i and j elements will remain not paired. When we do a transition from i to i + 1, we choose x elements from a set i and pair them with x unpaired elements from previous sets. When we counted the number of different pairings, we multiply it by N! * (2 ^ N), because we can put values to those indexes in N! ways, and we can color them in 2 ^ N ways.

And the time complexity is

So it should pass if we are not mistaken. Very upset that I didn't come up with the idea, and Kitsune, hadn't enough time to write it. Here is code.

Thank for reading. By the way, where can we upsolve the problems?

Me :

• Day 1 : 177
• Day 2 : 98

Kitsune

• Day 1 : 130
• Day 2 : 114

We know that an array is bad if it has a terrible subsequence. If the length of our terrible subsequence is bigger than 3, then we can remove some elements and it will remain terrible.

So the array of three elements is terrible of a[1] < AVG < a[2]. If a[1] != a[2], then a[1] always smaller then AVG. So now we need to check AVG < a[2] -> (a[1] + a[2] + a[3]) / 3 < a[2] -> a[1] + a[2] + a[3] < 3 * a[2] -> a[1] + a[3] < 2 * a[2] -> a[3] — a[2] < a[2] — a[1]. If in our array exists three elements (i < j < k) such that a[k] — a[j] < a[j] — a[i] then our array is bad. If we take the first element as i, our a[j] — a[i] will be maximized, and if we take two consecutive j and k then our a[k] — a[j] will be minimized. We can only check all consecutive j and j + 1 if a[j+1] — a[j] < a[j] — a[1], and if it's true in at least one j then our array is bad if it's always false then our array is good.

Hope I understand the hint and explained it correctly.

Please, can somebody help with my solution for G. I did everthing as in the editorial but used ordered_set instead of multiset or BIT. I spent almost an hour trying to find problem, but I couldn't.

UPD: I found problem. It was because erase in ordered_multiset doesn't work. So if you want to erase you need to erase using iterator of lower_bound, but I forgot that in ordered_multiset the lower_bound and upper_bound functions are swapped.

Yeah I know that you did like that, but I'm just saying that C(n1 + n2, n1) and C(n1 + n2 + 1, n2) are not same. You just said that they are equivalent which is not true.

No they are not. We do C(n1 + n2 + 1, n2) because we have n2 pairs out of range from l to x, so we can remove them at any time, that means we don't need to remove them before we remove [l,x] pair.

rainboy is the guy who solves problems on contests in reverse order. He starts from the hardest problem and goes to the easiest. I don't want to tag him (he might not like it). You can just search his handle(his handle is rainboy).

I think heuristica will win. But I'm not fully sure in it. Becuse there gamegame and duality.

Kyrgyzstan

• juggernaut (Daniyar Beishekeev), has 1 attempt left.
• HideoSatou (Islam Davletov), has 0 attempts left.
• Kitsune (Tengiz Bekkoyonov), has 2 attempts left.
• dream_is_real (Artur Aidarov), has 0 attempts left.

Thanks a lot

When will we be able to upsolve the problems?

You can do it in group ACM in Kazakhstan here is the link: https://mirror.codeforces.com/group/Uo1lq8ZyWf/contests

.