Sunday, December 31, 2023

A run twice week

The 2nd Universal Cup Stage 15: Macau took place last week, but its results were not public when I wrote the last summary (problems, results, top 5 on the left, analysis). Similar to the previous stages, this seems to have originated as an ICPC regional contest, but this time the top onsite team got quite high place 11 on the Universal Cup scoreboard (still with 9 problems, which seems to be a universal constant) — I guess we need to keep an eye at the Peking University team at one of the upcoming World Finals :) Congratulations to USA1 and HoMaMaOvO, the clear top 2 in the overall standings as well, on solving everything!

The 2nd Universal Cup Stage 16: Run Twice followed this Saturday (problems, results, top 5 on the left, analysis). The round featured 11 problems in the relatively new run-twice format (announcement), which I think is an awesome idea that extends the boundaries of what an algorithmic contest problem can be. The new format did not bring a new winner, as team HoMaMaOvO solved everything with an hour to go. Well done!

I did not participate in this round, but I checked out the problems because the topic was so interesting, and I'd like to highlight problem F: your program is executed twice. In the first run, you are given a graph with n=1000 (note that it is not n<=1000, but exactly n=1000) vertices, and 2000<=m<=5000 edges. It is guaranteed that this graph was generated randomly by adding a uniformly random non-existing edge m times. You can make at most 5 changes to this graph, where one change is adding an edge between two vertices not connected by an edge, or removing an edge. The first run of your program ends there. The graph with your changes applied is then shuffled (randomly permute vertices, edges, and ends of an edge), and is given as input to the second run of your program. The trick is that your program is not told whether it is the first run or the second run, and instead needs to detect it itself. In other words, you need to apply such changes in the first run that you'd be able to detect that the graph was changed from a random one in the second run. Do you see a way?

In continuing another great Open Cup tradition, Universal Cup is holding a Prime Contest this and next week. Given the higher amount of Universal Cup rounds, the Prime Contest appears practially infinite with problem numbers going up to 167, and nevertheless 36 out of 39 problems have already been solved, and even more amazingly 26 of those were solved by the same team! There are still 5 days left and 3 problems have not yet been solved, so maybe this is your chance — but remember that those problems are not for the faint-hearted :) You need an Universal Cup login to participate, and I believe you can get one via the registration form.

Codeforces Good Bye 2023 wrapped up the competitive year (problems, results, top 5 on the left). The round was not received well (1, 2, 3), but nevertheless congratulations to ksun48 on being the only one to solve everything and therefore getting a clear first place!

Thanks for reading, and check back in 2024.

1 comment:

  1. I took a lot of time for problem F since there's just so many different possible approaches: (approximate) diameter, cycles, components, ... . Eventually my solution was to add 5 edges between 4 largest-degree vertices. On the second run, I can check for (4th vertex's degree > 5th) and there are at least 5 out of possible 6 edges between the 4 top vertices. Now that I had more time to think, maybe dealing with cliques is possible, but I couldn't work out the probability.