Final Results are out! Congratulations to everyone, especially:
- orzdevinwang for the first place
- Adam_GS for the second place
- kes0716 for the first place in Korea (decided to be Gold at the very last minute!)
IOI 2024 is held in Alexandria, Egypt. Good luck to all participants! I'm also attending as a student coach (Guest) as well; please say hi if you see me!
All times are in UTC+3 (Egypt — Eastern European Summer Time).
- Day 1: 2024.09.03 09:00 — 14:00
- Day 2: 2024.09.05 09:00 — 14:00
- Closing Ceremony: 2024.09.06 19:00 — 21:00
Links
- Official Results
- Problems (temporary Dropbox link)
- Scoreboard
- Upsolving
- Unofficial Stream (Errichto)
- Previous thread
Please, keep all discussions civil and according to the IOI Code of Conduct. Please.
Why "Please" twice what happened
Refer to my discussion thread (that's what happens when a Gray made a discussion blog on the largest/2nd largest CP contest, I guess)
On the Codeforces mirror, how does the submission for problem B work?
UDP: Nevermind, I figured it out. Just implement the functions in the problem statement.
However,I think orzdevinwang will AK IOI!!!
orzdevinwang AK IOI!!!
hi! I can't see you but I want to, where are you/what are you planning to do today?
I'll be in the translation session, so not much window today. I'm likely around in the closing ceremony.
There is no problem statement for any of the problems at ioi.codeforces.com IOI 2024 day 1 (the link above), I only see the input and output.
See the attachments.
Here are the 100-point codes for all Day 1 problems — I wrote them while waiting for the bus to AASTMT :)
Shoutout to dillon0108 for sharing his beautiful solution of Message. Absolute legend.
In the last iteration of the loop at line 42 in tree, UB is invoked as W[W.size()] is accessed.
Fixed, thanks!
Are there any "easy" solution for Niles? I can't find an approach to it that isn't related to DSU (and requires some mild-heavy casework)
The other solutions involve segment tree or set or similar stuff the require more case work than DSU.
Still can't understand how this problem even have 82 AC....... this is definitely harder than IOI22's Fish, around as difficult as Digital Circuit, definitely harder than Closing Time, yet the AC amount says otherwise........ (Still can't find a way to code the DSU without bruteforcing the 16 cases when merging 2 components though
I can see how this problem has 82 ACs.
Sort everything in increasing order of $$$W$$$.
To solve the 67-point subtask, observe all matchings of $$$B$$$ are of the form $$$BB$$$ or $$$BAB$$$. Then, you can use a linear-time DP for each query.
It is standard to maintain this DP on updates with segment trees, where each node contains a 3x3 matrix.
DSU solution requires a bit more thinking, but I heard that the implementation is shorter. if you have 16 cases, then you should probably find a better way.
I can't think of anything lower than the 16 cases corresponding to the connected state of the first and last 2 elements. What are the stored states for each component in the "proper" dsu solution?
A common solution, and the one I did, is to:
sort by W
subtract B from A
for each node, find the distance between it and the next, and between its right and left neighbour, and store this in two sorted lists
have a dsu that stores int min_odd, min_even, min_internal; storing the min value of A at odd positions, even positions, and nodes that can be skipped
iterating through values of E in increasing:
for every distance of the first type with value less than E, unite(), maintining the min_*
for every distance of the second type, min the node's value into min_internal of its component
the answers are now sum(min(min_even,min_internal)), which can be maintained through the operations, totaling O(nlogn) for sorting and O(n a(n)) for dsu.
Thanks for your help. Also, how to spoiler texts/images?
After sorting by W, say for each D, we can group (i, i-1), or (i, i-2) depending on the contrast <=D. TC of each D is O(n), but u can sort those distance i.e (i,i-1), (i,i-2), and E[i]. Then iterate and set a position to 1-> maintain the maximum sum of a[i]-b[i] that you currently can group. use segment tree of continuous positions that have been set. The merging should be just casework
I feel quite surprised that the solution of message does not involve any kind of randomness :)
Should it require ANY kind of randomness, we'll have another Magic Show again......inan international contest. You know how well that went — clever bit manipulation, DSU and 250 lines of intricate code? Nope, 15 lines of CRT it is!
Since the grader is adaptive, any solution with randomness will be highly likely to be wrong
says APIO2024 problem C
Can you explain the logic behind the tree problem?
Pretend that subtasks 1, 2, 3, and 6 don't exist.
Is there any better way to reformulate the problem in a way that makes subtask 2,3 easier to approach? I'm cpmpletely lost on that here
Use the subtask 5 solution. For each $$$1 \le x \le 10^6$$$, Assign $$$W^\prime[v] = 0$$$ if $$$W[v] \le x-1$$$, and $$$W^\prime[v] = 1$$$ if $$$W[v] \ge x$$$. Take the $$$W^\prime$$$ as the 0-1 cost function and solve it. Sum this cost for all $$$x$$$.
This takes $$$1000000 \times N$$$ or $$$N^2$$$ time. To optimize this, observe that you are assigning $$$W^\prime[v] = 1$$$ to some suffix of $$$v$$$ in terms of cost. So you can maintain the quantity in DSU.
The intuition is that whatever greedy procedure you use (small-to-large, or simply naive stuff) will only care about the smallest/largest element you hold.
Thanks, nice method.
in how much time you solved them?(an estimate)
For day 1, I used about 2 hours to come up with 283 pts solution. Then I just read solution to the messages one. It took about 60-90 min to write them.
Hi, for Nile I think the 3x3 matrix solution is really cool. I'd like to ask: can this be extended to more general recurrence relations? It seems to me that because of the way you are calculating the matrix multiplication: $$$ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k])$$$;
You can only use this for recurrences of type $$$dp[i] = min(dp[i — 1] + C_1 , dp[i — 2] + C_2, ...)$$$ where $$$C_1$$$, ... are constants. Is it possible to extend this technique for more general linear recurrence relations such as: $$$dp[i] = min(A_1 * dp[i — 1] + C_1, A_2 * dp[i — 2] + C_2, ...) $$$?
Thank you!
Unfortunately, I'm not aware of an approach for $$$A_i \neq 1$$$.
For message, did anyone end up using the return value of send_packet? Seems to me like it was just a red herring ...
Not a contestant, but I found a way to improve the 70 packet solution (4 packets to send 4 bits to locate a good position, 31 to send the whole C on that position while using remaining 15 to send the message, then just send the message) to a 69 packet solution using it:
First, let P be the message S followed by one 1 and some zeroes so it's length is 1025. We're sending P to avoid sending the length of S directly. Call a position in C good if it's not controlled by Cleopatra.
As Aisha, find a good position with index 0-15, and call it X. First 3 messages, send 1 bit each message (by sending all 1s or all 0s) to send three bits of X. Now, Bob knows X is one of some two positions from 0-15. Call the other one Y. Next 30 messages, Aisha sends 30 bits of C at position X, skipping X itself (which has to be 0), while sending P on remaining good positions.
Now, construct array C_X and C_Y, which represent "how would C look if X/Y had the role of X". Basma knows these, but not which is which. If C_Y has a different amount of 1s than 15, Basma knows C_X is C, so Aisha can start using all 16 bits to send P. Otherwise, let A be the smallest position that has a 0 both in C_X and C_Y. Now, use A to send the remaining bit of X, while sending P elsewhere. Now Basma knows X, and therefore C_X, and therefore C, so Aisha can start sending P on all 16 good bits.
It legal for join IOI by doing TST in many country same time? I make new account for ask this, seem like MYS3 join Malaysia TST and Singapore NOI. For NOI, go round 2. This maybe mean they take spot from someone in SG who can go IOI, that not legal? I send email to organizer but they no reply, so this only way to tell people. What do now? Legal or no? Cheater at IOI?
I'm pretty sure it depends on the selection criteria for each country. I know that Indonesia team selection can technically have someone from outside Indonesia participating if they go to certain schools but in practice no one has ever even qualified to Indonesia TST from that route.
I don't think it would be considered cheating at all. A lot of people in Malaysia and Indonesia go to school in Singapore and through some weird coincidence could qualify for both TSTs.
On another hand, we also got William Lin who got banned from being a representative for Taiwan, as he was studying in an American school, and the Taiwanese delegates apparently only accepts students from pure-Taiwanese schools to "display the superiority of Taiwanese education", which then forced him to get in the USA team. We all know how that ended
Live 2 day watch party / unofficial commentary https://www.twitch.tv/errichto & https://www.youtube.com/errichto2/live
orzdevinwang AK IOI！！！
Congratulation！！！
Zhou Kangyang AK IOI!
orzdevinwang has AKed IOI!!!!! Congratulation!!!!
Even though Day 2 did not go his way but he did well in the end. Congrats kshitij_sodani on winning Gold.
Also congrats to orzdevinwang on winning IOI 2024.
orzdevinwang has AKed IOI!
Congratulation!
Day 2 tasks: https://jonathanirvin.gs/files/ioi2024/
Average Score Per Country
We have rank 7 in the average score but rank 20 in the medal ranking (which we send to our government) sadness...
Not anymore!
Let's see how long until people pointed out which task is similar to which existing task :)
(For those in the GA meeting, no spoilers! :) )
Second problem (of second day) looks like it might be from atcoder..
How could that problem even be new, though....... I'm pretty sure I've seen a similar problem somewhere.
If I have to guess, Nile is strongly inspired by IOI17's Wiring?
As the major objector, I would like to spoil, but I'm waiting for someone to spoil it for me.
Wait, you made it to the ISC already? Wow. Nice.
Nope, just a deputy leader, at least according to IOI Statistics.
https://atcoder.jp/contests/arc107/tasks/arc107_e ?
Yes!
Three girls are getting gold medals this year. This must be a record. Are there any statistics about this?
Are you around after the closing ceremony? The vietnam team wants a picture with you XD.
Sure!
Where did you go ToT
There is this well-known problem CF713C, also known as linear isotonic regression or BOI2004 Sequence — the standard $$$O(n \log n)$$$ approach to this problem uses slope trick. The downside of this approach is that the slope trick is pretty hard (to the extent that I don't say I understand it fully), and the backtracking procedure is not intuitive.
In summer 2022, I found an approachable solution to linear isotonic regression. This uses the same trick from Day1C — You simply try all suffixes of $$$C$$$ (using segment trees), assign $$$1$$$ to them, and sum all the costs. The structure of this problem is simple, so the formal proof is also very simple (if you increase the number of $$$1$$$, the demarcation point decreases). So we can obtain a straightforward construction as well.
Since this was one of the most incredible discoveries for me (and browsing through the CF archive, I was somewhat sure it wasn't well known in China, although you can never really be sure), I created a problem on this subject and proposed it to IOI 2023 call for tasks. In that problem, you have $$$0 \le C[i] \le 25$$$, and you should maintain the cost under updates of $$$C[v] = x$$$. The problem was rejected.
The proposed task has a setup that is really standard, and the solution ideas (in some cases, the exact solutions themselves) to all but the last subtask are well known “textbook” methods.
Even the idea for the full solution may be known by experienced contestants, as similar techniques have appeared before in other problems with different setups
(at least, multiple SC members were familiar with the full solution techniques and ideas).
So it was used in KOI 2023 Final Problem 4. It was solved by 5 contestants, which I believe will correspond to 60 solves in IOI. After opening the IOI 2023 problemset, I found the problems almost perfect. So, I thought (and still think) the rejection as reasonable.
This summer, my friend azberjibiou liked this idea and, using it as an inspiration, proposed the following problem in a local Korean contest. It was kind of a big contest (held offline). One of our Korean IOI team members tested this specific problem, and the other three virtually participated in this.
In the day 1 translation, I opened the third problem and immediately recalled the problem from me and azberjibiou. Two things went through my head — wtf is that rejection letter if you just put basically the same problem (where multiple SC members are familiar with the full solution)? And then, should I file a major objection since the azberjibiou's task is possibly dangerously similar to this one?
The first thing made me salty, but I love this idea, so it's good that people enjoy both high-quality IOI 2023 problems and this problem. I thought I can sacrifice it for the public good. For the second, I did not file a major objection because I think it's not dangerously similar to the cost of summoning a backup problem (after all that 0/1 idea descends from the era of Knuth). My decision was (unfortunately) proved correct as no participant from the Korean team solved this problem.
And then, in the day 2 translation, there was some heat as we had two major objections on problems (as hinted by jonathanirvings). While explaining their decision to use the current problem set, ISC said (something along a line of) "the easiest way to land your problem to IOI is to propose easy/middle problems as there aren't a lot of them, there is at least 50% chance of getting accepted". Then I became sad again since I proposed a easy/middle problem, got rejected, and next year found the harder problem that has the same idea.
Also on P3: Are there any suspicion from 1 of the 5 AC contestants being Indonesian (the same as the author's)?
I also think that IOI23's problemset is generally really awesome — literally 0 remotely "bad" tasks, all with interesting concepts (especially Soccer, what kind of demon thought of that thing, utterly beautiful; and Robot, which is.......probably the best IOI task up to date),......and then there's Mosaic, which I can hardly believe is 100% new. At least it's nowhere nearly bad enough to the point of being another Wiring incident (or, even worse, yet another final-touches-to-task-"Game"-was-finished-half-an-hour-before-day-2 moment).
By the way, what's the expected difficulty of the tasks, sorted by chronological order? Mosaic < Nile < Tree < Riddle < Hiegraphs < Message?
wow, that is indeed very suspicious
Mathew Allan did badly on every other task other than those his country set and is also only Master rating (I know there are several people with high performances being only master, but it indeed adds suspicion)
Niles can probably be explained since it was an easy task, Tree on the other hand....
I think better evidence should be provided to make an accusation of such kind.
I don't have an expected difficulty data from the ISC (if they have one). I guess I will mostly agree with the # of solutions for that.
i mean they are certainly quite suspicious circumstances, you can check his performance....
Sure, its not proof. Nobody claimed it so.
I however think that some kind of "home advantage" happens in general (even in non-suspicious way).
It can be explained by the following mechanism:
I understand that home advantage exists. But, do take a look at the difficulties too.
Tree had only 5 solves and was one of the hardest tasks... looking at the other tasks other than nile and tree, he barely had a bronze level performance, but in this he had a top 5 performance?
In my mind, I am 100% sure he cheated. I am also 95% sure nothing can be done about it...
Honestly I see where you're coming from, cause I definitely messed up my day two (spent too long on a fake solve for hieroglyphs, so didn't have much time to solve the others).
I'd like to clarify that I didn't cheat. I also didn't expect the number of solves for tree to be that bad. My solution was an extension of the Wi<=1 subtask and if you looked at the timeline I actually solved it with a lot of submissions.
And to the "only master" thing, I was IM before, but dropped a lot when I did a contest abroad.
Someone can solve a hard problem sometimes and not solve easy problems.
This is a serious claim. You cannot publicly accuse others of cheating with little to no evidence.
Well it's not unreasonable that someone just outperformed himself on that one particular day, or someone did particularly poorly on another day, especially considering how brutal day 2 was. I don't think it's fair to draw any correlation or suspicioun between the task author and 1 out of 5 solve.
On P4's unusual difficulty, it really seems like the one-liner questions are the difficult ones.
Any idea on why the scores are so low, though (Not that the task is any easy, or I can do better than 3pts, for all that matter). Once again, totally surprised that "Given 2 sequence A and B, determine if every common subsequence of A and B is a subsequence of LCS(A,B)" hasn't been given yet (and actually seems to be a very difficult thing). (but, then, again, IOI18's Meetings is nowhere near trivial)
....Again, I'd still wish that IOI discussion threads can (at least) have some short writeup on the solution for every tasks, the way it used to be in 2016-2019
I think this paper solves a generalized version of UCS in $$$O(nm)$$$ time.
In case I'm not hallucinating: Is subtask 4 of UCS......literally asking for the LCS of 2 sequence in O(NlogN)?
no....you can use properties of UCS to figure out when there can't be a UCS, otherwise the string is no longer a general string
Chinese participants scores reduced and one disqualified?
https://stats.ioinformatics.org/results/2024
One Chinese was disqualified. Two had half of their points taken away for the second day. Caught with cell phones
jesus
The fact that one of them still managed to get gold lmao
sphinx: Even though you figured out all the colors, there is another way to get only 50% of the points for the subtasks
What was the policy regarding cell phones and the likes in general? How do the ISC/HSC check for students' devices? Just asking, as I'm generally interested in the organization of IOIs, and it seems like a strange thing that such a devastating blow to the Chinese team could've happened
I took part in IOI 2022 and 2023. Phones are definitely forbidden in the contest hall. However, IOI generally works on an honor system, and they don't actually check people for phones, etc.
In IOI 2023 Indonesia team was told to keep our phones with our LO before entering the contest hall. If I'm not mistaken either our one of our delegation leaders/part of our delegation asked about this. In last year's IOI we were not allowed to take anything in the contest hall (food, mice, keyboards, pens, etc). At least I didn't see anyone bringing a bag into the contest hall.
....the joke flew over my head entirely. Wow.
(Not to be mean-spirited, but as a joke: Wow, the Chinese are so innovative, figuring out an entirely different solution from the ISC!)
Furthermore: Has this happened before? Should this affect China's trustworthyness in past contests (especially IOI20-21-22, those that were taken online)? Is the ISC/IC working on trying to prevent things like this from happening again?
As a former member of the Chinese team, I'm confident that none of my fellow students would attempt to cheat during the IOI.
This year, I heard it was the leader's first time serving as an onsite leader. In Chinese national contests, participants typically turn off their phones, place them in their bags, and leave the bags by the wall in the contest room. Without closely reviewing the rules, the leader assumed the procedure would be the same and didn’t instruct the students to remove their phones. As a result, three students unknowingly brought their phones into the contest. The only student who didn’t bring a phone had left it charging at the hotel after it ran out of battery.
I don't know why one student carried the phone with him instead of putting it in the bag. I understand that's suspicious. But I tend to think it's unintentional.
[UPD: I heard that the night before IOI, the leader will leave the students. In that case, it would be the guide's responsibility to ask the students to handle their phones. I apologize for my misunderstanding. ]
Isn't there video footage that can vouch for the 2 with the phones in their bags?Also where they caught by a check or did they casually take their phones out?
That's sad :(
To add, does someone know why there is no quarantine anymore?
I've heard that at the IOI 2019 team guides used to take participants' phones, so that there's little way to cheat (and current situation cannot happen). Also, at this or previous IChO quarantine took place, maybe at other olympiads too
I heard some talk that they dont do quarantines because currently there are so many eletronic devices that just taking away phones is not enough to prevent communication between setters and participants.
Also, what would actually prevent this from happening is better communication. When i went to my IOIs (2022 and 2023) knowing what we should do with our phones was a mess. Should we leave them with the guide? At the hotel room? With the team leaders? It felt like every day the answer was different. I imagine communication was similarly lacking this IOI.
In IOI 2023 I really thought that the guides (or whoever) would take our phones in the day before the contest day at like afternoon or something. They didn't and we just handed our phones to our guide right before we enter the contest space.
I don't suspect the 2 participants who put their phone inside the bag, turned off. But it is very suspicious that one went to the toilet with their phone on them, turned on, don't you think?
I agree. It’s suspicious indeed. The conditional probability p(turning on the phone + carry it to the toilet | not cheating) is low. However, my (personal) prior probability of cheating is also low; if we apply Bayesian rules, I can’t tell for sure.
I must say, this day two 50% cheating penalty must be one of the weirdest rulings that I've ever seen. Did they come up with this penalty on the spot or is this actually part of the IOI rules?
Agreed
I dont like such half measures...take one of the 2 actions.
If you think what they did amounts to cheating, diaqualify/void day 2. If you dont think so, any action is illegitimate.
There were three choices given by IC:
and the first choice was elected by a unanimous vote.
So why did IC didn't consider to DQ only 1 participant who had all means to use phone.
According to testimony above, It seems all others had it turned off and reasonable inaccessible, and while I agree that protocols should be followed, I think the students have no blame in the accident, and it should be attributed to local organizing committee
The two other guys got their phone "with them, but switch off and in their bags" — I think this means that the phones are still quite accessible?
Also, I think that there should be some sort of penalty to make guides and contestants more cautious regarding this problem.
Because the rules clearly said "Any attempts to bring any other items unlisted into the competition rooms are considered cheating." Below is more detailed explanation:
According to the IOI's calendar and related rules, participants should leave their mobile phones to their coach for most of the time because coach can get the full problemset several hours earlier to discuss and translate the statement. So the communication between coaches and participants is illegal at this time.
Btw it's so weird that they only checked CHN participants bags. I think checking all is fairer.
While there probably were such people, I personally don't know anyone who'd bring bag to contest hall, because I've thought it's a common sense you can't do that at ioi? So, well checking all would rather mean specifically looking for 5-10 who could also possibly have bags which, i guess, wasn't a solution in the after-contest mess.
While I think this is a good way to go about it, it may break the player's mind and not be conducive to a fair game.
Why was 4 DQs even an option, from the moment the contestants enter the hall their team doesn't matter.
That is incorrect.
I will first point out that according to IOI Contest Rules, mobile phones are explicitly prohibited and having one in the competition room is considered cheating.
IC has considered the case anonymously (only one voting member who was part of investigation was aware of the identity of contestants or country in question and the rest were not told) and after long deliberations IC has decided on disqualification of one contestant and 50% score reduction in Day 2 for the other two contestants.
This was then presented to the General Assembly who need to ratify IOI results according to Regulations. Although I cannot say currently with 100% certainty, but from my memory the ratification was unanimous in GA.
At no point IC has presented to GA any other options.
I heard this from some CHN people on site. Sorry if incorrect :(
But I think, for it was unanimous, so IC didn't need extra discussions or sth.
I attended the GA and can confirm that this is false. IC only presented their non-unanimous decision for 1 DQ and 2 half score. Of course the GA can argue about it, but surprisingly(?) there was not much argument.
I am certain there was no point where 3 DQs or 4 DQs were even mentioned by any IC or GA members.
The IC mentioned that they internally deliberated this issue for 1.5h before reaching the decision. So it's possible that the options you mentioned were on their table. We have to wait for the IC meeting minutes (if this topic will be included in their minutes).
they 100% came up with this penalty on the spot
upvoted
as a Chinese myself I support DQ 1 or DQ 3 but not this one
Y, Z 50% reduction sounds harsh to me...
Since MagicalFlower got a silver medal, does that mean that he can possibly participate next year?
China has a rule that every participant can participate in IOI at most once. So while he might still be eligible, he won't be able to represent China the next year.
I thought that you can't participate again only if you win a gold medal...
Oh, I see. I wasn't aware of that. Thanks!
You need to be qualified to China National Training Team to compete for National Team. Huang doesn’t participate in NOI this year(actually participated unofficially), so he is unable to participate in IOI again imo
It seems that he was confident in getting gold medals. How unlucky.
He (and the other two besides orzdevinwang) just graduated from high school, thus not qualified for IOI according to rules in China.
China only allows participating in the summer after grade 11(in the case of orzdevinwang) and after grade 12(in the case of the other three) for the full selection process lasts two years and candidate must be in high school(Grade 10~12) during the whole process.
The rule evenvalue mention is that if you got gold medal in Grade 11, you won't be eligible for the next. (Literally you can attend again if you got silver or lower, but no one did so for recent years)
oh, I forgot the age limit. Thanks for reminding me.
Congratulations to Esomer for first gold medal in Spain history!
My recollection on what happened on day 2 translation night. This should appear in IOI 2024 GA meeting minutes as well (which will only be released next year after IOI 2025 GA approves it).
A major objection was raised for q1, claiming that a similar task has appeared before and the solution is enough to solve some of the subtasks. SC rejected this objection by claiming some of the solutions of the similar task got 0 pts on the actual task since the similar task has a small alphabet size.
Another major objection was raised by Italy for q2 (as TheScrasse mentioned above) referencing https://atcoder.jp/contests/arc107/tasks/arc107_e. This triggered a lot more discussions. Another delegation echoed the similarity and strongly objected the task, claiming two of their contestants have solved the Atcoder task (kudos for the honesty!).
We could clearly see the SC had an intense internal discussion on these objections (photos in my tweet). After some time, they announced their recommendation to keep the task. The arguments include:
During the heated discussion that follows, the arguments that were presented by those who argued to replace the task include the following:
The arguments that were presented by those who argued to keep the task include the following:
In the end, a vote was taken whether to accept the task now or not (in the "no" case, IIUC, is to continue discussing). The result was almost equal, with the "yes" winning by a low margin (40-ish vs 30-ish, IIRC. The minutes should have this exact number). For the record, I, representing the Singapore delegation, voted "no". I was disappointed, but also understand that the GA would like to keep this task, and that we had to move on.
Following the conclusion of this task, the problemset was declared as final. The SC recognized that this was not the ideal solution given almost half of the room was not happy.
I believe that when we think about "submitting a problem for IOI", there is an assumption about the lower bound of the difficulty (as we fear that everyone can solve the problem that we purpose), and hence the lack of easy problems.
No need to worry about that, though, as we can always have yet another Fountain Parks incident again. While the model solution sounds almost silly and obvious the moment one sees it, it's still the hardest problem in IOI21, and gamegame's solution to it was literally "calculate some flows, merging components, ridiculously intricate DFS" and the likes, so......there particularly doesn't exist a problem that someone won't choke on (unless it was Cluedo or Memory or POI, in which case not solving them is just genuine 300cf behavior)
I believe that Fountain Parks is not intended to be the easiest problem on IOI21. Also, I see that you oversimplified the solution — good luck trying to solve the problem using your summarization of "literally "calculate some flows, merging components, ridiculously intricate DFS" and the likes"
I also think that we care about number of solves in general, if there are 150-200+ solves and some people choke then it is their problem. If no one chokes on a problem and everyone solves it, then what is the point of the problem anyway?
I didn't. gamegame did. It was literally his way to the solution (or, at least, what he decided to post on Codeforces). This is to say that: Regardless of the author's intended simple solution, contestants can and will manage to come up with their own ways to make the problem more challenging/less challenging than it was.
If anything, the IOI tasks should be used as grounds for popularizing some highly efficient techniques (DSU tree/Alien Trick) OR grounds for improving on previous solutions (in fact, within the 9 months between the task submission deadline of IOI23 and IOI23 Day 2, noone even thought that Z = 5 for Robot Contest was possible.....and it was). Giving "easy" problems to people who are expecting the equivalent of 3k5+ Codeforces problems IS grounds for some LGM to come up with the next revolutionary algorithm or something.....so there's precisely zero penalty on submitting things you'd thought to be trivial.
(Finally, on gamegame's solution, I kid you not, this was the monstrosity he thought up. If you REALLY thought that I was trying to say "yeah, the problem was trivial, his solution was just these simple things, bro!" instead of "This problem was intended to be the easiest task of IOI21 by the ISC, with a hilariously simple one-liner construction, yet some LGMs managed to come up with some absolute witchery 400-lines solution, so there's particularly no guarantee that people would NOT overestimate the difficulty of each tasks, no need to worry"........ignoring that I wrote a massive "hardest problem" right over there........you should definitely get your reading comprehension checked. No kidding)
Ey my bad on that "also" part. But I still believe that it is not supposed to be the easiest problem in the contest, just saying.
To your first comment: I don't think anyone thought that Fountain Parks was easy (including the author), and it didn't turn out to be an easy problem. I don't see any "incident" here.
From what I remember as a participant, Parks was intended to be the easiest problem on IOI 2021 Day 1. Obviously, this ended up not being the case, but it was a large factor in why DNA was used on Day 2.
Oh, so that's why the ISC decided to use the nerfed version of DNA (which is already easy enough as is) in day 2. Wow. never considered that
Second day is also availiable at https://ioi.contest.codeforces.com/group/32KGsXgiKA/blog
I don't think blindly halving the scores without being able to determine if the Chinese players are cheating or not is a convincing approach, I think we should give an accurate conclusion on whether they are cheating or not, cheating directly removes the scores, and obviously nothing should be done if they aren't cheating, and that should be what we all look forward to, not the vague results we have today!
you are right. there wasn't any camera in the contest hall? I guess we can figure out everything when we check it
Unfortunately, not allowing mobile phones is an official ban, which is very reasonable, because the coach or team leader will get the question earlier than the player to discuss the translation related matters, so the player should disconnect the Internet before the game, otherwise he may cheat before the game, which is also the reason for the ban.
Since the CN team has violated it, cheating or not, this is an official red line.
I think quarantine/disconnecting only the leader is more reasonable/convenient than disconnecting all the players, in order to prevent the leaking of the problems.
Of course, you also need to hand out the phones during the contest, but it is not related to problem leak anymore.
They had their phones with them, which is already cheating at that point. No ambiguity.
I think the issue here never was we have evidence if they cheated. Even if we know 100% they did not use their phones during the contest, bringing the phones itself is already against the rules. There are two parts in the IOI rules:
"Any attempts to bring any other items unlisted above into the competition rooms are considered cheating" and later, "Violating any of the following rules is considered cheating, and may result in disqualification"
Given this info, we know that the IC has the right to disqualify the two participants, but since the word "may" is used, they can decide on a lighter penalty.
To me it's similar to the law, where it states the maximum punishment for a crime is $X fine or Y years of jail, but the judge may choose to give a lighter punishment depending on the scenario. Of course we can discuss whether 50% is justified or not, but I'd argue this 50% is not meant to be a vague answer of "idk if they cheated", but what the IC judged to be an appropriate penalty of breaking the bringing of phone rule.
As a Chinese OIer,I believe the innocence of the two participants having their Day2 points halved is not in doubt.However this is indeed a violation of the clearly-written rules, and it just doesn't make sense not to penalize, even if the blame should be placed on the irresponsibility of the team leader.
I think some of the blame should also be put on the organizer as well for even allowing contestants to bring any items into the contest hall. Last year my team was told before hand that we were not allowed to bring anything and the rule was enforced during the contest days to avoid confusion.
its stated on the website that the team leaders are responsible for ensuring that their teams follow the rules. I think that's a terrible rule, but it is stated, so it's their fault sadly
When I heard the latest news, I couldn't believe it
how to solve sphinx ?
Ask
-1 c; whenever the answer is 1, that's the colour of node 0. Similar to finding the colour of node 1. $$$O(N^2)$$$ queriesThe same solution works, to check if node $$$u$$$ has color $$$c$$$, ask the perform following experiment - $$$E_j = -1$$$ if $$$j=u$$$ and $$$E_j = c$$$ otherwise. $$$O(N^2)$$$ queries
Since it's a complete graph, we can extend the previous ideas and perform a binary search for the node's colour. Let's say we want to check if the colour of $$$u$$$ lies between $$$L,R$$$; we can set $$$E_u = -1$$$, one node of each colour $$$L$$$, $$$L+1$$$,.. and so on, and all the remaining nodes of colour $$$N$$$.
If no of components is no of distinct values (including -1) in E, then $$$u$$$ does not have a colour between $$$L,R$$$; if no of component is one less than no of distinct values in E, then u has a colour between $$$L,R$$$.
$$$O(N*\log N)$$$ queries
Let's first find the colours of all odd nodes, and then we can do something similar to find the colours of all even nodes.
Let A be an array that contains a continuous range of nodes with common difference 2.
Check(A,C) returns if any node in A has colour C.
Since, A does not contain both the sides of an edge, we can perform following experiment —
$$$E_j = -1$$$ if j is in A, $$$E_j=C$$$ otherwise.
If no of components is size(A) + 1, then A does not contain any node with color C, if it is less than size(A)+1, then A contains at least one node with color C.
Find(A,C) all nodes with color C in array A. Its implementation is as follows -
If A does not contain any node with color C, return.
Otherwise,
P1 = half of the nodes of A, P2 = remaining half of the nodes of A.
Run Find(P1,C) and Find(P2,C).
This takes $$$O(2*N*\log N)$$$ queries, some tweaking needs to be done to get full points for this subtask.
Idk how to fetch remaining 36 points.
thanks very much
Do DFS, we solve for one vertex at a time. Let's assume we're solving vertex $$$v$$$, and we maintained all the "components" of all vertices we have processed previously (i.e., we consider edges where both endpoints have the same color and already processed).
Vertex $$$v$$$ possibly has some back edges to some of these components. We can binary search which component $$$v$$$ is connected to and merge them together (e.g., by coloring some components with color $$$N$$$). We can also know how many components that $$$v$$$ will be merged with total $$$N$$$ extra queries over all vertices.
If there are $$$C$$$ components in the graph, this part takes $$$N + (N - C) \lceil \log N \rceil$$$ queries. For $$$N=250$$$ this is at most $$$9N - 8C$$$ queries.
We already found all components, the problem is now figuring out the color of each component (also two components may have same color).
Merge each component into a super-node, add edges between two components if there is an edge between two vertices belonging to each of the two components. In this compressed graph, each super-node has a different color than its neighbors.
If there's only one super-node, we can solve it trivially.
Take some subset $$$S$$$ of the super-nodes such that every super-node in $$$S$$$ has a neighbor in $$$\overline{S}$$$ and vice versa. One easy way to get $$$S$$$ is to just take some arbitrary spanning tree of the super-nodes, and take $$$S$$$ to be the even-depth super-nodes in the spanning tree.
We solve $$$S$$$ and $$$\overline{S}$$$ separately. Iterate through all colors $$$0 \leq c < N$$$, and color all super-nodes in $$$\overline{S}$$$ with $$$c$$$, the rest with $$$-1$$$. By querying this, we can know whether there is some super-node in $$$S$$$ that has the color $$$c$$$. Binary search over $$$S$$$ (by coloring some of them with $$$N$$$) to find out which, and remove it from $$$S$$$. Recurse and do it for all $$$c$$$.
Done efficiently for both $$$S$$$ and $$$\overline{S}$$$, this will take at most $$$2N + \sum_{i=1}^C \lceil 1 + \log C \rceil$$$ queries. For $$$N = 250$$$ this is at most $$$2N + 8C$$$ queries.
Combined with the 50% solution, we have a total of $$$11N \leq 2750$$$ queries.
Some extra thoughts
I'm not sure whether there's a simpler or easy-to-implement solution. My solution requires to account for extra components caused by our own coloring which can be a bit annoying to handle... I feel like my bottleneck for this problem is implementation time over thinking time (though that may just be me being too rusty).
thanks very much
I have a problem regarding the incident of Chinese team: Did they come up with their plan of halving the Day 2 score of Kubic and MagicalFlower just on the spot? What's the point of neither just DQ them nor having their rankings unchanged?
I think there is a point, since realistically it will be easier to convince the Chinese team compared to 3 DQ, which is what the rule states.
Did they not announce the IOI 2025 dates in the closing ceremony?
Closing ceremony is later today
Have the dates for IOI25 been announced?
So the two chinese participants who got their points halved had phones found in their bags turned off. Did the committee check the bags only of the chinese team or all of the bags in the contest hall? I believe there were lots of participants who naturally put phones in their bags (with intention to leave the bags somewhere outside and have an easy access to them right after the contest) and accidentally brought the bags into the contest area due to unstrict rules. It would be strange to have exactly one team bringing their bags to the contest hall (and it accidentally appeared to be the chinese team). If the committee made a more thorough search and found phones in bags of like half of participants, would they penalize all of them?
If you caught one team member carrying a turned on phone, it's natural that you should check all of their team members. They are possibly the ones who were communicating with that team member. Doing so doesn't imply that you are obliged to check every 300+ participants in spite of resource and time limitation.
It's not possible to predict answer on your hypothetical scenario. A case with 3 people had already gone through extensive discussion. The assumed scenario is rather disastrous and would need even more discussion.
Is "there would have to be more discussion with others and it would be a disaster" a valid sole reason not to do the right thing, assuming that checking everyone's bag (thus enforcing the rules for everyone) instead of only one team is a right thing?
Also, I would assume that checking the bags must happen before participants enter the contest floor (since they allow bags at all, which is also not what I'm used to)
Read my comment again, "there would have to be more discussion with others and it would be a disaster", so: "It's not possible to predict answer".
It's weird that you assume that checking all 300+ bags are the only right thing to do after the incident. These 4 phones must be checked. If there is a murder mystery will you ask everyone in the city for fairness? Where do you draw a line?
And then, I don't have a good sense on how the onsite security checks were processed. Probably it wasn't too good, as we have this incident. What I only know is that electronic devices are strictly prohibited in the contest hall.
I don't understand your murder mystery analogy. So if someone is killed on the contest floor, you will not want to check all participants?
Electronic devices may be prohibited, but the rules delivery system is obviously flawed to say the least -- I don't remember reading any rules when I was a high schooler. Like, I knew that I mustn't use my phone. It didn't imply that I just leave it anywhere. Sometimes we were forced to give the phone to our team leader before the tour, sometimes we were forced to leave it with the organising committee, sometimes we probably didn't even leave it anywhere -- I was never bothered with any of these and always assumed that my only responsibility is to take care of defending the honour of my country on the contest floor and not the "switched off/left outside" choices
Whatever that helps. You encountered a possible cheating incident. Big question is if he cheated and whom he did with. You must check 3 phones of other team members to answer it. Then you may want to check other 300+ bag, possibly because you are obsessed with whatever fairness metric or you just have a lot of energy. You do you, you are fortunately not my policeman.
And then this complaints on the delivery system seems weird because you are obviously not a contestant. Electronic devices are strictly prohibited in the contest hall. If your intuition contradicts it, well, good luck.
(I'll try to not answer the possible upcoming replies)
I was a contestant in IOI2023
We didnt know what to do with our phones either. At the last moment, we left it with our guide.
I would not assume we are allowed to take them into the contest hall but if bags are allowed, surely phones within the bags are allowed right? Bags shouldnt be allowed but they were for some reason....which is the weirdest part
There definitely is an issue with how rules are communicated.
It seems that bags... aren't allowed?
On the competition days, contestants may not bring anything into the competition rooms, except for the following items under the proviso that they cannot transmit or store any data in electronic or printed or other written format (other than the purpose for which they have been designed):
mouse pads,
Bringing items with the exception of clothing, jewelry, and ID badge into the competition room requires prior approval from the Technical Committee. A contestant must submit these items by leaving them in a designated container provided by the technical committee on their workstation during the Practice Competition.
Which makes all of this even weirder — why didn't anyone warn the contestants about the bags when they entered the contest hall?
This is so weird. There are so much talking about whether to check the bags, when to check the bags, and whose bags to check.
But the bags are not permitted in the first place!
+1 on this. Our team members took everything without bags. Just weird talks
This
Seems like bad mamagement and pushing the mistakes onto the contestants....
eduardische can you tell how bags were allowed? It seems very natural to me to assume if bags are allowed, you can keep the phones in the bags (otherwise what even is the purpose of allowing bags) segtree template within the bag would be fine?
I’m speaking my personal thoughts now.
Ultimately, it is delegation responsibility to fully understand contest rules:
Bags are not allowed, although not explicitly. It was a surprise to learn that they were allowed on the contest floor. IC will work closely with the future hosts to ensure that this does not happen again. As the result, no action was taken because someone brought their bag. Mobile phones are explicitly prohibited however. But, given that it is possible to just accidentally forget the phone in the big bag, this resulted in different sanction for two of the contestants.
Were all other participants checked for phones within bags? It seems a very understandable error to me....
I was not part of the investigation, but from what I’ve been told, the main focus of the investigation was the concrete violation reported to relevant committees. During this process, it was deemed necessary to speak with entirety of delegation. At that time, the competition has ended so there was no possibility to search every bag on the contest floor.
So while it is possible that there were other violations of the contest rules, I personally don’t believe that it should prevent IC sanctioning known violations. On a personal note, as a past contestant, I am really surprised from this thread that there are a lot of contestants that are not personally familiar with contest rules that dictate what is and what is not allowed. That is not a risk I personally afforded when I was competing.
I think for fairness the committee should check all the bags. Just hope that in the future the committee can remind the participants of the rules and don't let the tragedy happen again
Come on, guys! We all know that thank to the punishment given to Chinese team, Korean get a gold. Stop downvoting Ko_osaga, he's doing his best for his nation!
Please abide by the IOI Code of Conduct. Insulting other teams' delegation, especially contestants, doesn't seem like doing your best for your nation.
orzdevinwang get 600 points in ioi2024!
He all kill ioi!
Congratulations to orzdevinwang for AK IOI. However,I was in the same high school as him and I graduated three years earlier than him (But I haven't participated in any OI contest). Have to feel the difference between people's talent,hope you can create more miracles in the near future!
Can anyone tell me about what did the Chinese contestants do on day 1. If on day 1, they had taken their phones to the contest zone, then the penalty should be applied for the points of that day also. If they had not taken their phones on day 1, then why did they take it on day 2.
The organizers probably didn't check their bags on day 1.
Any updates on IOI2025's timeframe and host for IOI27?
Some updates will happen at tomorrow’s General Assembly
Plot twist: The real reason all Chinese members carry their phone with (except for zhoukangyang) is simply to outright capture the moment Zhou solves all the tasks. I think the ISC was too harsh on them. Justice for China!
orzdevinwang AK IOI!
For the first time a Bangladeshi won gold medal in IOI 2024.Soumya1 Feeling happy for him.
Tasks authors now revealed! https://www.ioi2024.eg/competition-tasks
So the author of Thousand Islands setted UCS, the author of Digital Circuit setted Mosaic (now that I know, Mosaic is actually not stolen, just "similar idea that appeared before").
Will there be official editorial this year?
And it was announced that IOI 2027 will be held in Potsdam, Germany. Germany previously hosted IOI in 1992.
What would the timeframe for IOI25 to be?
Also huge Congratulations to kshitij_sodani !!
ASEAN teams at IOI 2024:
Thanks to everyone for joining in the photo. Lets try to get a better one (with proper lighting lol) next time!
Why do Iranian and Israeli students have asterisk(*) near their place?
And one German contestant. According to Regulations, everyone who competed remotely (9 contestants) would not count towards calculating medal boundaries but would be inserted into the table and given appropriate awards. The asterisk near rank denotes that as it does result in duplicate ranks, since on IOI Stats I keep ranks identical for medal boundary computations.
The scoreboard seems to be down (for now). Will there be an archive of the scoreboard similar to the last few years?
Hello everyone, author of Nile and Tree here! It had been my ultimate goal in competitive programming to author a problem in IOI. It was a bit unfortunate that they settled for one of the most generic titles for one of my problems (Tree) 😂😂 instead of going with my originally proposed title (Xylem). Nonetheless, I'm very grateful to have two problems used in IOI and I hope everyone enjoyed them as much as I did making them!
Great! Can you describe your process of coming up with these problems?
on Nile: Another problem with 2 approach. What was your original solution — DSU with merging states, or "Generic segtree where each node stores a 3x3 matrix"
on Tree: Again, aside from the obvious thing (how did you come up with the "trick" of summing suffixes combining with union by rank).....I still cannot understand how to solve the 0/1 version. Please help.
Now that dust is settled, I wonder if chinese team explained their side of the story. Was it some confusion that happened in terms of logistics, some failure in communication, a naive mistake made by a novice team leader, or the unlikely case where there was a real attempt to cheat. It must have been very hard for the chinese contestants.
They are most likely cheaters. That would explain why they get the best results every single year.
haters will always hate
https://new.qq.com/rain/a/20240907A01O6M00
I used ChatGPT to translate the above paragraph, which is quoted from the article linked above.
Are the solutions published anywhere?
bump😩
How to solve Hieroglyphs?
Let’s define the frequency of character $$$x$$$ in the string $$$S$$$ as $$$count(S, x)$$$. If a Universal Common Sequence (UCS) exists, the count of character $$$x$$$ in the UCS is $$$min(count(A, x), count(B, x))$$$. If $$$count(A, x) \leq count(B, x)$$$, we will call $$$x$$$ a character of $$$A$$$; otherwise, it will be a character of $$$B$$$.
For convenience, let’s denote a Universal Common Sequence as UCS and a Common Sequence as CS.
Let’s ignore characters $$$x$$$ for which $$$count(A, x) = 0$$$ or $$$count(B, x) = 0$$$. For each character $$$x$$$, we have $$$min(count(A, x), count(B, x)) = 1$$$. Let’s leverage the strength of UCS. The key idea is that any CS is a subsequence of a UCS. By determining whether a specific form of a string is a CS, we can identify a UCS. Assuming a UCS exists, let’s focus on the strings $$$ij$$$ and $$$ji$$$ for characters $$$i$$$ and $$$j$$$. Exactly one of these two strings is a CS. (If both are CS, it contradicts the condition that all characters in the UCS are distinct; if neither is CS, it contradicts the condition that all characters exist in the UCS). If $$$ij$$$ is a CS, then $$$i$$$ appears before $$$j$$$ in the UCS; if $$$ji$$$ is a CS, then $$$j$$$ appears before $$$i$$$ in the UCS. When we express that $$$i$$$ appears before $$$j$$$ as $$$i < j$$$, if the UCS is $$$a_1 a_2 \ldots a_n$$$, then for $$$i < j$$$, we must have $$$a_i < a_j$$$. An interesting point is that if $$$ij$$$ is a CS, then $$$i$$$ must appear before $$$j$$$ not only in the UCS but in all CSs. Therefore, if there exists $$$a_1, a_2, \ldots, a_n$$$ such that for any $$$i < j$$$, $$$a_i < a_j$$$, then $$$a_1 a_2 \ldots a_n$$$ satisfies the UCS conditions.
This time, since the existence of a UCS is guaranteed, we only need to know the order relation between two characters.
Let’s assume that for characters $$$i$$$ and $$$j$$$, each character has $$$c_i$$$ and $$$c_j$$$ occurrences in the UCS. To find the order relation between the $$$x$$$-th occurrence of $$$i$$$ and the $$$y$$$-th occurrence of $$$j$$$, we need to know whether the string $$$S = i \ldots i j \ldots j$$$ is a CS. Here, $$$S$$$ has $$$x$$$ occurrences of $$$i$$$ in the front and $$$c_j - y + 1$$$ occurrences of $$$j$$$ at the back.
To determine whether $$$S$$$ is a CS, we can check if $$$S$$$ is a subsequence of $$$A$$$ and $$$B$$$, which can be done in $$$O(1)$$$ time with appropriate preprocessing. Using this sorting function, we can solve Subtask 4 in $$$O(N \log N)$$$.
In Subtask 4, we found a candidate for UCS. The problem now shifts to determining whether the candidate string $$$C$$$ is actually a UCS.
First, let’s verify if $$$C$$$ is indeed a CS, and then check if it satisfies the UCS conditions. The CS verification can be done easily.
We want to find a string that is not a subsequence of UCS but is a CS. Here, we present a simple and evident greedy algorithm.
To show that string $$$X$$$ is a subsequence of string $$$Y$$$, we check the characters from the front of $$$Y$$$ to see if they match the starting character of $$$X$$$. If they do, we remove the starting character from $$$X$$$. This is a straightforward two-pointer algorithm.
Let’s define $$$f(X, Y)$$$ as the minimum $$$i$$$ such that $$$X$$$ is a subsequence of $$$Y[0..i]$$$. To show that $$$C$$$ is not a UCS, we need a string $$$S$$$ where $$$f(S, A) < |A|$$$, $$$f(S, B) < |B|$$$, and $$$f(S, C) = |C|$$$ satisfies. (For convenience, if $$$X$$$ is not a subsequence of $$$Y$$$, we define $$$f(X, Y) = |Y|$$$.)
In the way of LCS-style dynammic programming, let’s define $$$dp[i][j]$$$ as the maximum value of $$$f(S, C)$$$ among strings $$$S$$$ satisfying $$$f(S, A) \leq i$$$ and $$$f(S, B) \leq j$$$.
If $$$A[i] \neq B[j]$$$, we have $$$dp[i][j] = max(dp[i-1][j], dp[i][j-1])$$$.
If $$$A[i] = B[j]$$$, there is an additional dp transition. We find the minimum $$$k > dp[i-1][j-1]$$$ such that $$$C[k] = A[i]$$$ and set $$$dp[i][j] = min(dp[i][j], k)$$$. This can be computed in $$$O(1)$$$ with appropriate preprocessing, allowing us to solve the overall problem in $$$O(N^2)$$$.
There is a problem with the solution for Subtask 5. It does not escape the LCS-style dynamic programming. As it stands, we cannot reduce the number of DP states to below $$$O(N^2)$$$. Let’s make some observations.
Let’s define $$$match_A[i]$$$ as $$$f(C[0..i], A)$$$. In simple terms, it indicates the position in $$$A$$$ corresponding to $$$C[i]$$$ when matching $$$C$$$ to $$$A$$$. Similarly, define $$$match_B[i]$$$ for $$$B$$$. Through $$$match$$$, we can visualize the elements of $$$C$$$ as edges between elements of $$$A$$$ and $$$B$$$. Thus, $$$C[i] = A[match_A[i]] = B[match_B[i]]$$$.
Now, let’s define $$$g_A(S) = match_A[f(S, C)]$$$ and $$$g_B(S) = match_B[f(S, C)]$$$. Edge made by connecting $$$g_A(S)$$$ and $$$g_B(S)$$$ corresponds to edges formed by matching $$$S$$$ to $$$C$$$, which is represented as edges between $$$A$$$ and $$$B$$$.
For any string $$$S$$$, we have $$$f(S, A) \leq g_A(S)$$$ and $$$f(S, B) \leq g_B(S)$$$. To put it more plainly, edges created by matching $$$S$$$ to $$$A$$$ and $$$B$$$ are always to the left of the edges selected by matching $$$S$$$ to $$$C$$$, which is represented as edges between $$$A$$$ and $$$B$$$.
The reasoning is straightforward: $$$f(S, A)$$$ defines the minimum $$$i$$$ such that $$$S$$$ is a subsequence of $$$A[0..i]$$$. Since $$$g_A(S[0..i])$$$ corresponds to the elements of $$$A$$$ matched by $$$S[i]$$$, the elements $$$g_A(S[0..0]), g_A(S[0..1]), \ldots, g_A(S[0..|S|-1]) = g_A(S)$$$ must include all elements forming $$$S$$$. Thus, $$$g_A(S) \geq f(S, A)$$$.
(Here, the red edges connect $$$f(S, A)$$$ and $$$f(S, B)$$$, while the blue edges connect $$$g_A(S)$$$ and $$$g_B(S)$$$. The $$$i$$$-th red edge is always to the left of the $$$i$$$-th blue edge.)
An important observation is that if there exists an $$$S$$$ such that $$$f(S, A) < match_A[f(S, C)]$$$ and $$$f(S, B) < match_B[f(S, C)]$$$, then $$$C$$$ does not satisfy the UCS conditions. If the last character of $$$S$$$ is $$$i$$$, we can attach as many $$$i$$$s as possible to form a CS that is not a subsequence of $$$C$$$.
What does it mean to flip the DP formula? The previous DP formula computed $$$f(S, C)$$$ while fixing $$$f(S, A)$$$ and $$$f(S, B)$$$. Now, we will fix $$$f(S, C)$$$ and compute the minimum $$$f(S, B)$$$ when $$$f(S, A) = g_A(S)$$$, and vice versa. This reduces the number of DP states to $$$O(N)$$$.
Let’s define $$$dp[i][0]$$$ as the minimum $$$f(S, A)$$$ for strings $$$S$$$ that satisfy $$$f(S, C) = i$$$ and $$$f(S, B) = g_B(S)$$$. Similarly, define $$$dp[i][1]$$$ for $$$f(S, C) = i$$$ and $$$f(S, A) = g_A(S)$$$.
Let's consider adding a character $$$c$$$ to the end of the string $$$S$$$.
Define $$$k_X$$$ as the smallest $$$k > i_X$$$ such that $$$X[k] = c$$$ for $$$X=A, B, C$$$. Here, $$$i_A = dp[i][0]$$$, $$$i_B = g_B(S) = match_B[i]$$$, and $$$i_C = i$$$. If $$$k_A < match_A[k_C]$$$ and $$$k_B < match_B[k_C]$$$, then the string $$$S'$$$ formed by adding $$$c$$$ to the end of $$$S$$$ will satisfy $$$k_A = f(S', A) < g_A(S') = match_A[k_C]$$$ and $$$k_B = f(S', B) < g_B(S') = match_B[k_C]$$$. This leads us to conclude that $$$C$$$ is not a UCS.
If $$$k_A = match_A[k_C]$$$, we perform the transition $$$dp[k_C][1] = min(dp[k_C][1], k_B)$$$; if $$$k_B = match_B[k_C]$$$, we perform the transition $$$dp[k_C][0] = min(dp[k_C][0], k_A)$$$.
Although the number of dp states is $$$O(N)$$$, the process of checking whether the string $$$S'$$$ formed by appending $$$c$$$ satisfies $$$f(S', A) = g_A(S')$$$ or $$$f(S', B) = g_B(S')$$$ still takes $$$O(N^2)$$$. We should aim to make this process more efficient.
We need to solve whether there exists a character $$$c$$$ that satisfies $$$f(S', A) < g_A(S')$$$ and $$$f(S', B) < g_B(S')$$$ for the string $$$S'$$$ formed by adding the character $$$c$$$ to the end of $$$S$$$. If such a $$$c$$$ exists, it would demonstrate that $$$C$$$ is not a UCS.
Assume $$$g_A(S) > f(A, S)$$$ and $$$g_B(S) = f(B, S)$$$. Let $$$c$$$ be a character in $$$A$$$ of index between $$$f(A, S)$$$ and $$$g_A(S)$$$. If the count of $$$c$$$ in $$$A[g_A(S) + 1 .. |A| - 1]$$$ is less than the count of $$$c$$$ in $$$B[g_B(S) + 1 .. |B| - 1]$$$, then we can keep appending $$$c$$$ to $$$S$$$ to form a string that is a common subsequence (CS) but not a subsequence of $$$C$$$.
If the count of $$$c$$$ in $$$A[g_A(S) + 1 .. |A| - 1]$$$ is greater than or equal to the count of $$$c$$$ in $$$B[g_B(S) + 1 .. |B| - 1]$$$, then all occurrences of $$$c$$$ in $$$B$$$ must be included in the UCS. This means that $$$match_B[k_C] = k_B$$$.
Thus, for every character $$$c$$$ in $$$A[dp[i][0]+1 .. match_A[i]]$$$, we need to check whether the count of $$$c$$$ in $$$A[match_A[i] + 1 .. |A| - 1]$$$ is greater than or equal to the count of $$$c$$$ in $$$B[match_B[i] + 1 .. |B| - 1]$$$.
If all CS $$$S$$$ satisfy $$$f(S, A) = g_A(S)$$$ or $$$f(S, B) = g_B(S)$$$, then we can conclude that $$$C$$$ meets the UCS conditions. For a CS $$$S$$$ to not be a subsequence of $$$C$$$, there must exist some prefix of $$$S$$$, denoted as $$$S'$$$, such that $$$f(S', A) < g_A(S')$$$ and $$$f(S', B) < g_B(S')$$$.
Let’s calculate $$$dp[i][0]$$$. When the last character of $$$S$$$ is $$$c$$$, we have $$$A[match_A[i]] = B[match_B[i]] = c$$$. For dp transition from $$$dp[j][0]$$$ to $$$dp[i][0]$$$, there should be no occurrences of $$$c$$$ in $$$B[match_B[j] + 1 .. match_B[i] - 1]$$$.
Let $$$k$$$ be the minimum index of $$$C$$$ such that $$$C[k + 1 .. i]$$$ contains no $$$c$$$. Let $$$t$$$ be the minimum of $$$dp[j][0]$$$ for $$$k \leq j < i$$$. Then, $$$dp[i][0]$$$ will be the smallest $$$l$$$ such that $$$A[l] = c$$$ and $$$l > t$$$. This type of transition can be handled in $$$O(\log N)$$$ using a segment tree. The same process can be applied to compute $$$dp[i][1]$$$.
One question that might arise is why we don’t consider the transition from $$$dp[j][1]$$$ to $$$dp[i][0]$$$. Such transitions are not necessary to consider because for strings $$$S$$$ that account for $$$dp[j][1]$$$, we have $$$f(A, S) = match_A[j]$$$, and what matters for calculating $$$dp[i][0]$$$ is minimum $$$f(A, S)$$$. Since for all strings $$$S'$$$ considering $$$dp[j][0]$$$, we have $$$f(A, S') \leq match_A[j]$$$, we don’t need to take those into account.
Now, we need to check for any character between the $$$(dp[i][0]+1)$$$-th character of $$$A$$$ and the $$$match_A[i]$$$-th character that does not satisfy the conditions from Observation 2. We will do this using a sweeping approach. As we increment $$$i$$$, we will track whether count of $$$c$$$ in $$$A[match_A[i] + 1 .. |A| - 1]$$$ is less than the count of $$$c$$$ in $$$B[match_B[i] + 1 .. |B| - 1]$$$. For those $$$c$$$, we will maintain a set of maximum indices $$$k$$$ such that $$$A[k] = c$$$ and $$$k < match_A[i]$$$ using std::set. If $$$dp[i][0]$$$ is less than the maximum element in this set, then $$$C$$$ is not a UCS.
If there are no $$$dp[i][0]$$$ or $$$dp[i][1]$$$ that do not satisfy the conditions from Observation 2, we can conclude that $$$C$$$ meets the UCS conditions. A brief explanation for this can be found at the end of section Observation 2.
Thus, we can solve the entire problem in $$$O(N \log N)$$$.