ICPCNews's blog

By ICPCNews, 5 weeks ago, In English

text 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:

Some useful links:

Scoreboards:

46 47

All available broadcasts:

MAIN AR RU ES PT CN ID

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

Split screen 46 Split screen 47

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

  • Vote: I like it
  • +698
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Why is the Mirror linking to tourist's twitch?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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 :).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes, you are correct, added this link to post

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the meaning of double world finals?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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).

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. Will there be separate problemsets?
      2. Single team can participate in both at the same time?
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it
        1. We don't know anything about problems before the beginning of the contest
        2. Not, only one team per contest. 2022-2023 season of regional contest qualified with extra selection rules
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -25 Vote: I do not like it

          The problems are the same for both ICPCs?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it -7 Vote: I do not like it

            Definitely, NO. You can notice the different solve counts on 46th and 47th scoreboards even problems letters A->K 47 P->Z 46

            But there might be some intersections

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it -27 Vote: I do not like it

              Maybe same problems but shuffled ??

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it +34 Vote: I do not like it

                Available now, 47th PS 46th PS

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

fix the live stream plz!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

fix the stream. wtf?

»
5 weeks ago, # |
  Vote: I like it +85 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The IDs of Zhejiang Normal University in 2022 looks incorrect

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -64 Vote: I do not like it

    No, just practice the first problemset for 5 hours, then the second for 2.5 — 3 hours. Or practice them simultaneously for 8 hours. There are plenty of options as you can see, choose what you want.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Who won? Can anyone tell from stream who won?

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

I wanna go home :((

»
5 weeks ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

jiangly won 1st place.

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

kudos to Um_nik for being such a wonderful host

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +150 Vote: I do not like it

      Bro i swear i thought this was you

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +253 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what did he do

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +85 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
5 weeks ago, # |
  Vote: I like it -73 Vote: I do not like it

so happy MIT didnt win a second time

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Congratulations to jiangly!!!

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

My Approach
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +38 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        SnapDragon has uploaded his code to GitHub.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +36 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +48 Vote: I do not like it

              I think we should be able to get a three-cycle whenever two cycles meet at 2+ vertices

              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.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    yes they aked with 2min left

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Link for results table?

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They've uploaded solution videos here

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Do not interfere in our contest

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

jiangly orz !!!!!

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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!

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

When will editorials be made available?

»
4 weeks ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

_*_*_

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.