ojuz When should the mirror contest be available? I am looking forward to trying the mirror this year. IIRC last year the mirror contest was up after ~3 hours or something

briX1210 orz. He's not even 14 years old.

bump.

Okay, not really though. Some silly predictions:

• This is entirely assuming that we're working with themed tasks (aka: Tasks that actually fits with the host city/country) here, but some funny things can happen:

• Alexandria (specifically) and Egypt has a LOT of grounds to work with in cooking up task legends. As I haven't spent 4 days looking at the wikipedia page for Alexandria just yet, the first thing that came into my head was......the Library of Alexandria. Which has a lot of things. And was burned. I'm fairly certain that this year's DS task will be themed around this infamous library. (Or, perhaps, we might get to see another communication task that asks something among the lines of "yes, these books were burned, go recover them" for the first time since IOI2011's Parrots or something. On that topic: It's really weird that we haven't got any (proper, completely) Communications task in recent IOIs, given that those tasks are too common to the point literally every other OI contests have one every other year (at least, JOI has one every year, my national TST has three of them for the past three years, with one being literally reconstructing VK codes or something, ....))

• One other VERY notable person who was born in Alexandria: Ptolemy. Those who are former MO people (literally 99% OI-ers lmao who am I kidding, the venn diagram between OIers and MOers are nearly a complete circle) would've heard about some crazy geometry bullshit created by none other than Ptolemy..... so there might be one or several dreaded geometry tasks here. Everyone knows how unfun geometry questions could be. Furthermore, most of Ptolemy's contribution is on the field of Astrology (stars and constellations and stuffs dude singlehandedly named half of them or something)...........which is clear major grounds for some funny graph thing.

• But.....why Ptolemy in particular? Well, upon reading the IOI meetings records or something (yes, this guy have read pretty much every single IOI meetings transcripts last year or something) for IOI19 or IOI20 (can't remember exactly), IOI23 was set in Hungary as 2023 was the 130th anniversary of Jon von Neumann's birth — it'd be somewhat reasonable to think that when picking Alexandria as the location for IOI24, the ISC might have something in mind. (And, on that, IOI23's Robot Contest was literally "construct a cellular automata that solves a maze and deletes everything but the solution"....... in the IOI that was mostly there for the celebration of the person who came up with cellular automata in the first place......so there's that. While it's probably a moment of coincidental genius, this might've been the initial idea?)

(totally unrelated to the things above: ahihi1234 was the first 10th grader in Vietnam to ever made it to our national IOI team (after winning the national TST by a landslide and solving Magic Shitshow from APIO24), which is.....notable enough.

As a reference for how impressive this is:

1) Until now, he was the 3rd 10th grader to EVER made it to Vietnam's International Olympiad teams. The other two (former) 10th grader won a gold medal in their first attempt — so there's that. (may kieu j cung top bac hoac bottom-middle gold ay)

2) 10th grader making it to APIO in Vietnam is rare enough (there were only 2 such cases in the past, AFAIK). The two cases were...........

• fexivity thenymphsofdelphi, only CPer who've collected 5 different Regional/International Olympiad medals. His standing in Vietnamese TST 2021 was (actually I forgot but he definitely didn't won the contest by a landslide and got a silver in APIO2021, so there's that)

• user202729_, perfect score in APIO2020, gold medal in IOI19/20. In 10th grade, he made it to #8 in Vietnamese TST. Once again, not winning by a landslide

(yes, this is an intense praising post. Please gimme a printout of the Day1 and Day2 problemset as souvernir)

Do we know whether there is going to be a live scoreboard this year?

What's that? The scoreboard? https://ranking.ioi2024.eg/

What's the IOI3 team?

I'm doing some commentary while watching the leaderboard https://www.twitch.tv/errichto

recording: https://www.youtube.com/live/YMXdOl2Ets8?si=udg3jmWXAqc8Qfv1
see you on day 2

orzdevinwang : sleep time

orzdevinwang All Kill IOI Day1！！！

Congrats orzdevinwang, just 3 hours pass and he already AK IOI day 1.

orzdevinwang bosssss

orzdevinwang AK IOI DAY1!

orzdevinwang is so hurried to eat lunch that he AK in 3 hrs

wow, you're still love haiender288 since I last seen TLEOJ team :penguin:

IOI 2024 day 1 tasks: https://jonathanirvin.gs/files/ioi2024/

These are the v0 version of the English task statements distributed at the start of the translation night. I forgot to re-download the tasks after all of the modifications. But there isn't any significant change.

EDIT: Deleted the day 1 tasks on my server. Refer to https://www.ioi2024.eg/competition-tasks instead.

I made a new discussion thread

Tried offline mirror yesterday. What I could currently think of:

Nile: implement wrong/50% to correct solution for 3 hours — sort the list, then start DSU-ing to calculate the answer. What I thought was "for each component, keep 4 cases of "both ends are free","left end is free" "right end is free" and "no end is free", then merge the answer accordingly " (which failed the sample testcase). From what I've heard the actual solution is not that far off: when merging 2 components, we keep track of the first and last 2 elements instead (as we can observe that an artifact at pos i should only ever be matched with i+-2, since if i can be matched with i+-3 onwards, there exists a way to rewire the matching such that all matches to i+-2 or not. Still can't understand the massive amount of AC on this, this actually seems harder than most P1s in recent years (Beech Tree is excluded).

Message: cannot think of anything, absolute witchery. The fact that the lowerbound is 66 queries and simply transporting 16 bit at a time requires 64 messages means that either we'll have to determine the 15 bits in 2 queries (what?) or transmit in a way such that even the scam bits can convey infomation (HOW?). Absolute witchery.

Tree: can't even re-formulate the statement to come up with a way to solve subtask 1. Too hard.

Any thoughts/ideas on the tasks?

Update: Found a written editorial for Message (in Vietnamese) here, which was.....wow. Here's a rough translation (only the non-free parts + some obvious optimizations when possible):

1. Q=80 (4+1+ 15x5):

• Use first 4 query to send all 0-1 array to form a bitseq of length 4, denoting thr position of the FIRST good bit (the PP makes it so that there must be a good bit in position 0...15). Call this bit G(0) and the list of 16 good bits G(0..15). These queries are purely fodder, no information of S here

• Use 1 query to send length of S. Also no info of S here.

• For the next 15 batches of 5 query: use bit G0 to transmit the bits in a bitseq of length 5 denoting the position of the i-th good bit. In the OTHER 15 good bits, transmit S.

• After B receives all 80 query, determine the 16 good bits, then read the sequence S accordingly after going through the last 75 query (do remember to stop reading S after the transmitted length has been reached). Can transmit 75 x 15 = 1025 bit (again, just enough, wow)

1. Q=71 (4+1+30+36)

Same as above, but after the 5th query, use bit G0 to answer "is the i-th bit excluding G0 good or not". Can transmit 30x15 + 36x16 = 1026 bits. Again, wow

3) Q = 66

• Let d(i) be the positive distance between G(i) and G(i+1) on a circle length 31. Notice that 66 x 16 — 1024 = 32 i.e we only have 32 spare good bits to transmit the good bits, and, most importantly: the sum of all d(i) is PRECISELY THE LENGTH OF THE CIRCLE, 31. We then do the following:

• For the i-th good bit, we transmit d(i)-1 0, one 1, then start using it to transmit the good bits normally. This way, we'll waste EXACTLY 31 bits.

• We find the good bits as follows: We look at the first 16 queries, then look for the first 1 sent for each of the 31 bits. Construct a graph where there exists a directed edge between i and (i+id of query where 1st bit 1 in position i was sent). The 16 good bits will form a cycle of length 16 on that graph with 31 edges. It is well known that in a graph with N vertices and N edges, all the components are either a perfect cycle, or a line which then leads to a cycle (if you've spent a decent amount of time working with subtask 3 òd Roller Coaster Railroad, you'd definitely know). As the cycle length 16 takes a majority, it is unique, and we've found the 16 good bits. Done!

My general thoughts:

• Wow this is so fire.

• My guess is that this problem was setted by none other than our beloved, trusty Hazem Issa — the author of IOI22's Insects and IOI23's Longest Trip, from the extremely tight bound (FYI, the bound of Rarest Insects is literally exactly N + N/2 +N/4 +.... = 2N, and the bound on Longest Trip is literally 3N/2 + 2logN-1 +1)

• Communication problems are bound to have some shenaighans happening. Seriously. After you've heard about it the solution for Q=70 just sounds silly AF, yet not many could actually come up with that in-contest (even Rainboy, rip, at least he still have next year to AK IOI).

orzdevinwang is not so hungry today so he AK in 4.5 hrs

orzdevinwang AKed. Absolute legend of IOI&CP.

orzdevinwang AK IOI!!!!!Orz!

Zhou Kangyang has AK IOI!

Zhouak has AKed IOI!

Day 2 tasks: https://jonathanirvin.gs/files/ioi2024/

The results are up: Link One participant from China got disqualified for having his phone turned on while in a contest, and the other two got their scores halved by having a phone, but it was turned off.

Back from the dead here: I've updated the statistic of the IOI tasks spreadsheet.....but messed up REALLY badly, and now the 6 added tasks aren't counted in the sortings. I have 0 experiences working with Excel. Please send help

I was shocked when hearing sjy dq and hlt's ans kubic's score devide by two. As a Chinese, I was happy yesterday as zky AKed and China got 4 Au. But now, only 2 Au and 1 Ag. Bad to me.

.

(at some point, this has stopped being a proper discussion thread, and turned into a bashing thread. Very nice, definitely!)

Given this comment and stuffs that happened in the Vietnamese community, I want to say a few words.

1. First of all to make it clear, I don't have anything against you. I'm very supportive of people of all ratings to talk about / discuss / learn from IOI problems (they are usually very fun and educational) — precisely why I wrote some IOI editorials in ways such that anyone can understand.

2. Most people are upset with you bad-mouthing Vietnamese IOIers (including messages from last year + comment this year where you tag xuanquang1999). I give you the benefit of the doubt and attributed at least some of these to your lack of ability to communicate properly (also note I already forgot what happened last year and I also don't fully understand the situation with xuanquang1999). However you need to learn from this and communicate better. (Do note that some of the Vietnamese CPers have the habit of saying things like "X code ngu" or similar, myself included. These are usually said jokingly or tactfully, between friends or people who know each other well. Even then I need to be aware that people might be angry / offended if I say such things).

3. Some people gave you good advice. Re-read everything that MofK told you in the Discord server a few times. Many others indeed bullied you or had shitty behaviour. My advice is to give up talking to them, as it seems indeed impossible for you to improve your image in their mind. Again, learn to communicate better in future.

4. In general, you can't have good opinion on problems unless you have either solved it or previously solved thousands of problems in Competitive Programming. Reading your comments, some are good and some are very stupid. My advice would be: don't say anything about the problem before you AC it. And also solve more problems.

Essentially mindsolved the question within 2 hours of thinking today. Current ideas:

P4 (UCS): No

P5 (Mosaic):

• I initially thought that "Okay, this problem is going to be relatively complicated combinatorics contribution counting similar to IOI22's Digital Circuit", and was pretty much stuck without any ideas for 2 minutes. Then I thought that "okay, there should be some pattern here, spent 2 minutes coding a random 28 x 28 board that is valid, runs it several times, and, uhhhh

Basically, it is clear enough that: Aside from the first 2 row/column, every TopLeft-BottomRight diagonals (indexed by their value of x-y, with x being the row and y being the col of each cell) has the same value......so you can simply iterate through all the intersection of each diagonals and the queried submatrix (with a bit of casework for when the first 2 row/cols are touched).....and you're good to go. 78pts, although the casework could be tricky. For 100pts it'd probably require more stuffs, but I've spent a grand total of 15 minutes on this (and would prefer to think about P6 more), so there's that.

More specifically:

• Subtask 1,2,3,4: Build the entire board and use 2d prefix sums, duh.

• Subtask 5: Chessboard coloring for col and row 3 onwards. Major hint for "it is similar from col/row 3 onwards". I initially thought that things will already be the same after the first row/col.

• Subtask 6/7: Simply calculate the value on each diagonal, use a prefix sum on the values of the diagonals (or a prefix sum on the first 2 row of the board if the queried submatrix is in this section isntead).

General thoughts: Bad problem. This is not an output only or a Div2B. This is a fricking IOI problem. IOI contestants would usually expect state-of-the-art problems popularizing some insane tricks (Aliens', Warewolves'), beautiful construction (Parks', Split), or some cool ideas. Not this. Some people were unfortunate enough to NOT think of "just output the entire board", thinking that this was an IOI problem, no way that's supposed to work (it is actually a standard problem stolen from ARC instead), and lose a ton of points. This is kind of in the same vein as the infamous Nowruz, where the "stupid" idea ended up working with little to no novelty and botched the scoreboard to an unimaginable extent, although MUCH less horrible. Still, though, an IOI task KNOWINGLY taken from an online source made it in? Come on, man. (On this, read ko_osaga's thread instead)

P6 — Sphinx:

• Subtask 1: Duh

• Subtask 2: For each vertex, pick a random adjacent vertex, color all but those 2 vertices with color 0 and iterate through the list of N colors on the 2nd vertex. This will determine the colors of all vertices in N^2 queries.

• Subtask 3 (checking if adjacent vertices has same color or not): ......iterate through the edge list? No, seriously, it's just as simple as....that. For all of the N-1 edges, set all node not on the 2 ends of this edge to color 0. This will easily determine whether those 2 nodes have the same color or not. Easiest 16.5pts ever existed

• Subtask 4:

• Notice that each monochromatic component is also a clique. To decompose the large cliques into multiple cliques, we do the following:

1) Index every vertex from 1.....N. We then find all positions i where i is the index of the SMALLEST appearance of a color in 1...N (or, in other words, determine all positions i that has no other vertices with the same color in range 1....i-1). We can do this by asking N-1 queries, where in the i-th query, we'll keep the color of all vertices in range 1...i, while setting all other vertices to color 0. The returned value of each query will be (number of different colors in 1..i + 1). If the returned value of the i-th query is different from the i-1th query (more precisely, equal to the returned value of the i-1th query + 1), vertex i is what we'll need to find. Push this into a vector or something, and mark this as "selected"

2) For all unmarked vertices u, we will binary search for its color (which out of the selected vertices at position < u has the same color with u). We set the color of all vertices with index > u and all unmarked vertices at position < u to color 0. Assuming that there are C marked vertices with index < u, the return value of the query function will be C+1. We then binsearch on the prefix of length C of the vector of marked vertices:

• If we set Mid elements in the prefix length C and the returned value of the query is C + 1 — Mid, this means that the marked vertex with similar color to U isn't in this prefix.

• Otherwise, if the returned value of the query is C + 1 — Mid — 1, this means that the marked vertex with similar color tu U is in this prefix (of the list of marked vertices).

Doing the same thing for all vertices, we can decompose the big clique into multiple cliques, and get 50% of the points for this subtask

• After decomposing the graph into multiple cliques, we can determine the color of each sub-clique by doing the following things:

1) We already knew the amount of different colors in the graph (the list of marked vertices), denote it as D. If we "compress" each subclique to a node in a secondary graph, the 2nd graph will also be a clique with no 2 nodes sharing the same color. We simply pick 2 random node in the 2nd graph and iterate through all N colors. If the returned val is D-1, it means that this color exists in the graph.

2) To determine the color of each subclique, do the same thing as what we do in the "subclique decomposition" above once again.

What the Chinese team wrote in blood red with their two gold medals:

$$$ {\color{Red}{ CHECK \ YOUR \ ELECTRONIC \ DEVICES}} $$$