Hello Codeforces!

The 2023 ICPC World Finals Luxor will begin on April 18, 2024 at 10:00 UTC. This time, we have a double World Finals. You can distinguish them by colors: blue (fish emoji) and green (crocodile). Join us on the live broadcast for this awesome double event of the year in competitive programming; commentators will include ecnerwala, SecondThread, Egor, and more!

ICPC World Finals Luxor is hosted by The Arab Academy for Science, Technology, & Maritime Transport (AASTMT), the ICPC World Finalist teams for two seasons will compete for World Championship awards, prizes, and bragging rights. More than 130 teams of each season represent the best of great universities of eight ICPC regions.

Teams qualified to ICPC WF Luxor:

- Official list — select region
- Non-official list with CF rating: 46 47

Some useful links:

- Official website of the ICPC
- Official ICPC WF Luxor website
- Schedule of Events
- Live broadcast
- Photo Gallery
- Mirrow Contest
- ICPC World Finals Mirror (ksun48 + Petr + tourist)
- Luxor brochure

Scoreboards:

All available broadcasts:

Also, you can observe teams' monitors and web cameras on the separate broadcast. Sent team's hashtag to the chat to see your favorite! All hashtags for both seasons were collected in this list

We wish good luck to all competing teams to have a great time spending, and to do the best to get amazing results!

ecnerwala orz

Why is the Mirror linking to tourist's twitch?

he will do a livestream, look at the streams section of codeforces

But a mirror's supposed to be a live contest?

Will be there any live contest mirror? Can you please share the link?

On their main website icpc.global, they have a link to an online mirror: https://onlinejudge.icpc.global/. The icpc.global website top-left menu has pretty useful links :).

Yes, you are correct, added this link to post

what is the meaning of double world finals?

Due to Covid ICPC WF Moscow was rescheduled to October 2021. In Luxor are hosted both ICPC Finals of 46 and 47 seasons (2021-2022 regionals and 2022-2023).

The problems are the same for both ICPCs?

Definitely,

NO. You can notice the different solve counts on 46th and 47th scoreboards even problems letters A->K 47 P->Z 46But there might be some intersections

Maybe same problems but shuffled ??

Available now, 47th PS 46th PS

There are different problems but some intersections as well with some shuffle, but overall they aren't identical.

Is there a prize for winning an ICPC world final? or just normal contest?

around $$$10^4$$$ dollars for the first place

oh okk thanks!

For all official and mirror participants, good luck and don't forget to have fun!

fix the live stream plz!

fix the stream. wtf?

here we go again:

https://zibada.guru/finals/

separate pages:

https://zibada.guru/finals/2022/

https://zibada.guru/finals/2023/

The IDs of Zhejiang Normal University in 2022 looks incorrect

Looks like the intersection of the problemsets is 5 problems. Shame. Now for training purposes you have to choose one or the other.

I had expected 10-13 common problems. 5 is great.

Who won? Can anyone tell from stream who won?

Peking U beats MIT with minor advantage.(10AC)

Who won '23?

orz

I want to congratulate the [HSE] FFTilted team on their well-deserved victory at the 47th ICPC World Final!

I wanna go home :((

Me too :-(

#metoo

Me too

orz

Please feed cowboys to the sharks and let someone else announce the results.

jiangly won 1st place.

kudos to Um_nik for being such a wonderful host

what? I wasn't even in Egypt, not to mention hosting anything.

Bro i swear i thought this was you

Don't you dare compare me to such a horrible person

You did not try to solve the contest? I am pretty much sure you would have solved all of them.

what did he do

That man bans anyone say a word about him from the ACPC.. Fortunately, you are in North America!

Good to know that I am in North America...

If antontrygubO_o has a million fans, then I am one of them. If antontrygubO_o has ten fans, then I am one of them. If antontrygubO_o has only one fan, then that is me. If antontrygubO_o has no fans, then that means I am no longer on earth. If the world is against antontrygubO_o, then I am against the world.

Idol.

Bro legends never cry

Same

Congratulations to the Peking Universe and National Research University Higher School of Economics！And thanks to all the competitors for performing such an excellent game！

so happy MIT didnt win a second time

Congratulations to jiangly!!!

Are solution sketches available anywhere? In particular, I'm wondering what's the intended solution to problem E.

My ApproachFor each continuation of length 4 up to a certain bound, count the number of recurrences with that continuation. This allows us to find the first four values of the continuation. Then, given the first four values of the continuation, we can enumerate all recurrences with that continuation, which turns out to be bounded by $$$4836557$$$ for the given constraints. Though I had to spend several hours to fix the MLE / TLE / WA verdicts (the memory usage is barely under 2TB) ...

We had the same approach. But we couldn't code it clearly and we didn't have enough time. The author's solution is also interesting. If you find an editorial, please share.

That looks largely correct. The main idea to speed up the solution and reduce its memory consumption is: for each continuation, instead of just counting the number of recurrences that begin with that continuation, compute all possible next values to this continuation, along with their frequencies. This lets you prune out a bunch of useless continuations since the values get very sparse after the first few values in the sequence.

Would you mind providing solution code? Don't quite understand how the pruning works.

SnapDragon has uploaded his code to GitHub.

Great, I'll take a look.

Btw, anyone know the proofs for Zoo Management / Schedule? I came up with the necessary condition / some reasonable construction, though I wasn't able to show that the condition is sufficient / the construction is the best possible when the answer is odd.

For zoo management:

There are a lot of results you can get from this: https://en.wikipedia.org/wiki/Jordan%27s_theorem_%28symmetric_group%29 (assume we are talking about a BCC that is not just a cycle--I think the permutation group generated by the cycles is always primitive and transitive)

There is a three-cycle we can get by taking the commutator of two cycles that share a single vertex; so this is enough for the "even permutations only" case and it is enough whenever two cycles meet at just a vertex.

I think we should be able to get a three-cycle whenever two cycles meet at 2+ vertices, but the most interesting thing I can construct (also by the commutator of these two) is a pair of transpositions that are "displaced". My guess is that you can produce either a single transposition or a three-cycle by some conjugation and three of these moves.

Please let me know if you can finish the second bullet, since I'm also struggling to finish this.

The nice idea here is that in this case you actually have three simple cycles in a graph.

So if you draw a picture of 2 cycles like

`OO`

with intersection in the middle, you can rotate these 2 cycles clockwise, and then rotate the outer cycle counterclockwise (the outer being formed by a set of edges from symmetric difference of 2 "`O`

" cycles). And that gives you a single trasposition.Beautiful! Thank you!

Did tourist, petr and ksun manage to solve all the problems during their stream?

yes they aked with 2min left

Pretty amazing stuff. It seemed that they started a bit slow (relative to some of the competitors), but they have caught up during the contest (I missed the latter part of their stream). Glad that they finished in time!

Link for results table?

46

47

what algorithms book and resources gennady korotkevich (tourist) read?

Where is solution?I don't know why my solution to problem U got WA...

What would be pretty cool is if someone can create a scatter plot of the average Codeforces rating of each team vs the number of problems they have solved.

As a member of Jiangly Fan Club, I'm so excited that jiangly won the 46th ICPC world finals!

Nice!

Will there be an editorial? I'm really curious Alea Iacta Est and three kinds of dice.

They've uploaded solution videos here

Yeah it was helpful for most of the problems that I was curious about, but Alea Iacta Est is still confusing to me. I am having trouble visualizing the state graph, and how the cycles happens, and how using the min heap helps with cycles. I wonder if someone can provide a larger example of state graph than the video editorial. I recognize the problem is beyond my skill level, but it I feel I'm just too close to understanding it now. If I could just understand the state graph I think I would get the transitions and how min heap applies.

I think I have a general picture of it a little now, but this part I'm having trouble rationalizing. best_expectation = (pw + current_expectation[mask]) / counts[mask] This is how I roughly interpret it.

pw is a variable that represents if I select subset of dice to roll {1, 3}, this calculates the number of possible configurations from that subset, so for this it is 6^2. And it represents the number of expected rolls to achieve the current target configuration.

current_expectation[mask] is the accumulated expected number of rolls to take a given configuration with some dice fixed to a face value, and picking the subset of dice to roll {1, 3} to achieve a configuration in the dictionary.

counts[mask] is the total number of visited complete configurations (all face values fixed) that are rolled from this current mask with some fixed face values.

Some observations

counts[mask] = 6^number_of_dice_to_roll, after it finishes exploring everything, so like if mask represents A?B?, then it will have 6^2 = 36 counts at the end.

It first explores complete configurations that are in dictionary, and in those cases the current_expectation[mask] = 0, and the best_expectation = pw / counts[mask] really, so if there are 3 complete configurations that can be reached from some state of dice to roll selection, then it will be pw / 3, which seems reasonable.

Then it explores the lowest expectation values for incomplete states, and finds all the unvisited complete configurations that are intermediate, that is they could lead to config in dictionary. Or in other words, for all the possible selection states of rolling -> PACB -> ?ACB -> KACB (in dictionary). I think this is where my understanding really starts to drop off.

Do not interfere in our contest

jiangly orz !!!!!

Congratulations to the Peking Universe and National Research University Higher School of Economics！And thanks to all the competitors for performing such an excellent game！

When will editorials be made available?

Here we go

_*_*_

hmmmm, Alea Iacta Est has the same code as provided by snapDragon, link

*_*

Is there any way I can resubmit for the problems? I was busy during the mirror contest (which is ended) and now I really want to try.

You can solve the problems at Kattis, either here, here, or here.

Do you know where can I get the complete problemset?