Салем Codeforces!
We are glad to invite you to follow 2024 ICPC World Finals in Astana, Kazakhstan!
This is the third ICPC World Finals to be held this year. It is the culmination of the 2023-2024 ICPC season, and we have over 140 teams competing for the title of ICPC champion. Advancing from the regional contest, 141 of the world’s strongest students teams of programmers will compete at the 48th ICPC World Championship in Astana!
2024 ICPC World Finals Astana will begin on September 19, 2024 at 11:00 (UTC+5). We are thrilled to invite you to join the live broadcast of the main event of the year in the world of sports programming!
Teams qualified to ICPC WF Astana:
Some useful links:
- Official ICPC World Finals website
- Schedule of Events
- Live broadcast
- Photo Gallery
- Astana brochure
- Mirror contest
- Teams' submit reactions
- Non-official scoreboard with CF handles from zibada
- Qingyu Chinese Stream at BiliBili
All available broadcasts:
Also, you can observe teams' monitors and web cameras on the separate broadcast before frozen hour. Sent team's hashtag to the chat to see your favorite!
Follow ICPC World Finals Mirror contest of team ksun48 + Petr + KAN:
- Mirror contest stream
- More details in Petr's blog
Сәттіліқ тілейміз, жақсы нәтиже көрсетулеріңізге тілектеспіз! Good luck, enjoy your time at the ICPC World Finals!
Does the mirror contest start at a specific hour or you can start whenever you want?
Friendly reminder that this event is run by a private corporation with questionable board members.
I am sorry, but what he has to do with final in Astana?
In previous years, he was the MC at the closing ceremony. And guess what, he was annoying af...
yea and the amount of money they take for the ECPC and ACPC is astounding tbh...
why downvoted. 100% correct
Apparently, after registering for the Mirror Contest, it says that the contest is scheduled to start in 2025
List of teams with team member names
Thank you! Added link to text
Live standings with CF handles:
https://zibada.guru/finals/
How to calculate the ranking?
Is it allowed to see scoreboard for participant when ICPC going?
when are the final results gonna be out?
Who wins the CHAMPION?
Peking University
MIPT told Ecnerwala that they solved one problem in last hour. i guess they might win it all.
Other gold medal teams didn't tell anything about last hour but they didn't seemed confident
something happen with team University of Maryland they have good hand with CP
last 10 in standings is shocking
What but how can -ve years exist XD
wait so prob C bruteforce = AC? edit: nvm I just saw SnapDragon ran AI on it, it was probably a giveaway problem
Go atcoderr japan became champion
Peking University takes the cup — ICPC 2024 WC! Congratulations.
What happened to University of Maryland?
Why the University of Maryland scored so low? Anyone knows? I was rooting for them
Jokes aside, can it be that Shayan was too tired after a push-up duel with Mike?
How many acs can o1 AI get?
Hope we'll know soon. They seem to have their online judge open for general public, don't they? If so, someone will definitely test the model.
Talking about individual problems, I'm betting on it AC'ing J since it was a slightly buffed Nile and it was able to get 100 in Nile.
When we tried it, o1-preview failed on B and C, but got F. AI is coming for us all...
So answer is like 1 or 2 ACs maybe?
Today, I learnt that problem L had a testing tool, and this was nowhere mentioned in the problem statement. I did an unofficial mirror, but there is a non-zero chance that some of the onsite team did not notice it.
cc tourist SnapDragon
Also, since we are at it, can someone help me with a counter testcase for this solution?
Many teams that I asked (including our team) didn't know about this :^)
On all other contests that I can think of (for example EUC) it was written in bold at the begining of the statement that the interactive has a visualizer in the attachments.
Was this supposed to be some type of gotcha to test if teams read the fine print?
Hmm, looks like we mentioned the tool in QC QC (our first interactive problem) in 2020, but not in Sphinx in 2022-23. If teams are missing it, then I agree, we should probably mention it in the statement next time.
For your "Where Am I Now?" solution, think more about what the 3rd sample input means...
You can go to the center and say you are in (2, 2).
I have love for coding but I get frustrated when I can't solve any problem... What is the solution?plz help..my dream one day i will participate ICPC
Is the archive with the solutions of the contestants available or will be available somewhere? It would be interesting to see how close were 2nd, 3rd and 4th teams to getting the 10th problem accepted, especially how close was MIPT team who had a TL attempt for problem E at 04:59:59.
In case it's helpful / any of the authors see this, I wanted to share a few thoughts on the problem set. My apologies if this comes off as a soapbox--I'm hoping it's at least somewhat constructive!
To be honest, I was not a fan of this year's set--that opinion is probably partly the result of my disappointment in my own performance, but I also think the problems were not up to the standard set by the 2022/23 WFs (which I think were probably the all-time best WF sets). (Caveat: I haven't spent much time with the hard end of the set, but in practice I imagine the vast majority of teams spent approx. zero time on the four hard problems.)
Broadly, I think the eight problems approachable for all but the strongest teams were heavy on standard implementation and extremely light on original ideas. More specific feedback:
A: Nice idea, but I think it's well-known (I vaguely remembered the idea from somewhere and some friends remembered definitely seeing it before). I would have liked this problem a lot had it been the most standard thing in the set, and the math component makes it particularly well-suited to a team contest, but in the context of the rest of the set it contributed to the excess of unoriginal ideas.
B: Pretty good easy problem. While this didn't trip me up during the contest, I would have phrased "assuming the order of the numbers is uniformly random" as "assuming the order of the numbers is chosen uniformly at random among all permutations of the n * k numbers on the sheets". A friend pointed out that one might read the problem and assume that in each round, one of the numbers still remaining on some sheet is called out at random (e.g. if two 1s, a 2, and a 3 remain, each number has a 1/3 chance of being called next; in the correct interpretation 1 has a 1/2 chance of being called next). While I think the current phrasing does imply the correct interpretation, it seems better to state the sampling rule more precisely.
C: Pretty much a straight implementation problem. Not exciting, but not the worst problem either (though I do think whether you can count negative years towards your citizenship should be specified explicitly).
D: Probably my favorite of the six easy problems. It's pretty clear that it's going to work out with some kind of greedy strategy, but once you have the right strategy in mind, getting some intuition for why it works and implementing the idea are not too hard.
F: Extremely standard exercise; I'm a little disappointed that this problem was used on the WF. The problem basically consists of slapping together three standard pieces of implementation (binary search, connected components, knapsack), so not only does this problem not offer new ideas for teams to think about, it also forces them to spend a fair amount of time typing standard code instead of thinking about more exciting problems.
I: I am 100% certain I have solved either this exact problem or the functionally equivalent version where you are given the maximum distance allowed and need to minimize the number of fire engines used. (Citations would be appreciated if anyone has them--a friend pointed out that this appeared on the Singapore NOI in 2020, but that's not where I've seen it. Note that the NOI problem even has similar flavor text!)
J: While this problem was basically the reason we fell behind (I spent 90 minutes implementing an idea that was either incorrect or vastly overcomplicated before realizing that there was a cleaner solution and finishing up 15 minutes later), I actually think it's one of the better problems in this set. Like A, I would have liked it a lot if it was one of the most standard problems in the set, but "segtree problem where you have to store some special info in the state" is a fairly standard trope at this point and so this does contribute to the overall standard feel of the set.
L: My least favorite problem in the set; I dislike it both from a theoretical standpoint and due to some issues with its preparation. For the most part, this problem felt like an implementation exercise; for the most part the idea is to just do the most obvious possible thing, and the only tricky part is noticing the tricky center-of-a-square case (where multiple orientations could work, but some points' positions are still uniquely determined). I think it's a little sad that medals in this contest were largely determined by a combination of implementation / corner case hunting (and on a personal level, I was disappointed to end up not solving this problem after noticing the corner case before touching the keyboard...)
I also have a few points of criticism related to the problem's preparation. First, the existence of the testing tool was not mentioned in the problem statement, and I had no idea the tool existed during the contest. I'm still a little bitter about this because I'm pretty confident that I would have been able to debug my implementation had I actually been able to test it without spending a ridiculous amount of time manually interacting. (I'm also curious if any team that didn't use the testing tool ACed this problem, and how many other teams also didn't know the testing tool existed--I know at least several others did, but not sure how widespread a problem this was. It would be especially sad if medals were basically determined by who noticed the testing tool!)
I realize the judging notes mentioned that there might be a testing tool for any interactive problems. However, it's easy to forget because for most interactive problems testing tools are not necessary because manual testing is sufficiently fast. Moreover, in most contest platforms, testing tools are often not provided for interactive problems and are thus explicitly mentioned in the statement when they exist. I think the testing tool should thus have been mentioned in the statement, but if that isn't possible, I'd support announcing before the contest/the dress rehearsal that interactive problems may offer testing tools even when not specified in the problem statement, since this is an important detail that one could easily miss while skimming the judging notes.
Second, the statement of the problem makes any invalid queries undefined behavior. On Codeforces/many other platforms, the behavior of the interactor is typically specified even for invalid queries: e.g. if you submit an invalid query, the interactor outputs -1 and you must exit in order to receive WA; otherwise you may receive an arbitrary verdict. No such guarantee was made for this problem, meaning that verdicts were essentially completely arbitrary (e.g., my solution got TLE and I have no idea whether the issue was a typical cause of TLE, e.g. my logic went past the time limit or I took too long to provide a new query, or if I actually submitted an invalid query and then exceeded the time limit while waiting for input on my next query).
With all of this said, thanks to everyone involved in organizing the contest! I do think a lot of things went very well, and from an organizational standpoint this WF was an improvement over Dhaka, the last one I attended. (Some particular highlights: I thought the chillzone had better activities; I appreciated that time was set aside for an excursion; less time was spent listening to speeches, although that still took up more time than I'd like; I enjoyed the banquet during the awards ceremony and appreciated not having to wait until after awards to eat dinner.)
A minor error : in the correct interpretation of B, 1 has a 1 / 2 chance and 2, 3 have 1 / 4 chance in the given example
Something about C : What i really hate about this is not even that the ambiguous statement, it happens, But wf's jury's decision about what to do about it.
For some reason, they decided to reply "no comments, read the statement" to every clarification about it. (And i was not the only one, i know atleast 3 other teams even among just my friends with the same misunderstanding, and i think 2 of them asked a clarification about it too)
I read the statement over and over again, i still cannot seem to find it non-ambiguous.
As a future request, even if it is given in the statement, can you just please reply to the clarifications?
For anyone interested, here was my clarification "are you allowed to output year 0 when y = 1, 2?"
Thanks, fixed the typo!
I agree that clarification requests about this issue should have received responses (though for several reasons I'm not convinced that it makes sense to respond to clarifications about things that are clearly specified in the problem statement).
Why? Other than too many clarifications (which i hope there woouldn't be), i can't imagine any harm
I think "too many clarifications" is actually a pretty meaningful issue--I think this is pretty clearly true on CF, but even at the ICPC level, it takes a surprising amount of time to formulate a good response to a clarification that answers the question without giving away more than intended, and it seems bad to let a queue of clarifications build up. This is both an incentives issue (when you're more likely to get a response to a clarification, you're more likely to submit a clarification instead of reading the problem more closely) and an increase in the cost of processing each clarification (because you can no longer paste "read the problem statement" for most requests).
I also think that when you start responding to questions clearly answered in the statement, it becomes harder to draw the line between clarifications that should and should not receive responses. There are a number of things that are factually true given the problem statement but that you probably wouldn't want to give to contestants via clarifications (e.g. the answer to arbitrary test inputs), and I'm not sure how to fairly decide what information can be given out as a result. You basically need to determine "is this obvious given the problem statement", which seems pretty subjective.
i have been a codeforces round setter, and i saw how many clarifications came including ones that are clearly written in the statement (usually from lower rated people). We replied to most questions without resorting to read the statement i believe. Despite that, with only 3 people replying, we were able to keep up with the rate.
ICPC WF is a lot better in 2 regards :
The people are on average higher rated
There are less participants
Of course if participants start abusing your clarification system, change it, but I don't think such would be the case.
answer questions like this "Do the subsets have to be continous? or in a case like 4,5,6,7 a valid subset can be 4,7?", i answered "yes valid subset" (quoted from my round). Ask to rephrase and specify their question instead of an arbitrary input if needed.
reply no comments to questions like this : "for 4 islands , if there are 4 bridges that can be destroyed , we attleast visit 3 islands , why is 1 the answer"
it is not that hard imo....
First off: thanks a lot for the feedback. As a judge, and a part of the problem selection committee; hearing back from competitors is important to make the competition better. I would also love to hear your feedback on the harder end of the set (E, G, H, K), and I actually would also love to hear a similar discussion of the problemset in Luxor (which I'm really glad you liked, as I was involved in that one as well :) )
I find your classification of "the eight problems approachable for all but the strongest teams" somewhat confusing. The only I think were approachable for all the teams were B, C, I and F. Nothing else got solved by teams in the lower 25% of the scoreboard. As for the middle of the pack (say, the middle 50% of the scoreboard, between the 25% and 75% marks), the approachable problems were those four plus A and D — there were exactly two solves of anything else by teams ranked 35th and below. If you look at teams ranked up to 24th place (so, teams with 6 or less problems), you'll see 3 solves of J, 2 of L, and one of K — while there are 30 or more solves of everything in A, B, C, D, F, I. Or, in other words, I don't think grouping J and L with the other six is super-useful.
That said: we definitely messed up with L by not being very explicit about the testing tool. It's a bit unfortunate we didn't notice before — because we did the same thing in Luxor (where the testing tool wasn't mentioned in the description of Sphinx), and in Dhaka (where the testing tool wasn't mentioned in the description of the first Where Am I Now) — we only did it right in Moscow, with QCQC. If we did this right, the implementation cost of L is not horrible, and the core of the problem becomes "did you think through your solution well enough to notice the edge case" (and maybe then the problem does actually belong with A and D).
One thing I do take away from your analysis is that we made the "easy" part of the contest too tedious. Ideally, the top teams (I'll use the top 23 teams — the teams that got 7 or more problems in this contest) would get through the medium-easy part of the problemset (in this case, ABCDFI) in between 2 and 2.5 hours, and spend the majority of their time on the hard end. In this case, the average time to get those six problems was over 3 hours, which I agree is too much.
Another thing you say is that the "hard" part of the contest contained two problems which you see as "kinda easy" (J and L), and not super-interesting. I'll comment a bit more below.
I'll also comment on a few specific problems.
One thing that surprised me, personally, was how obvious the combination of ideas for F was to people. Of course, you're right that the building blocks are standard; but I thought that the decomposition of the problem into those building blocks wouldn't be immediately obvious to most teams. I'm still not sure it was — you're not "most teams" — but I also didn't predict this to be the second-easiest problem, I thought it was comparable to D. I'm the original author of the problem (and of problem G, just to show I can also do something less standard :) ), so it's hard for me to judge, but I wasn't the only judge expecting this to be harder.
Another thing that surprised me is how well J went. J is the only problem in the set that I didn't solve — that is, when reviewing the various problem proposals, I came up with solutions to all the other problems in the set; but wasn't able to come up with a solution to J (and then I coded up the solutions I came up with to the other stuff, I didn't end up coding J). I guess that shows that I'm not up-to-date with the standard tricks in the higher end of the current competitive programming meta.
(I also hoped that someone would've solved G; but I think we didn't really give this a chance to happen by slowing teams down so much with the medium-easy stuff)
I wonder how much would your opinion of the set change if we removed some two problems from the medium-easy end (say, I and F, or A and F), and made sure that the testing tool for L was clearly marked (that makes the implementation much easier — I know, as I tried to implement it without, and eventually gave up and just wrote a testing tool)? I expect it would still not be your favorite set — I see you weren't excited about any of the ideas in the eight problems you discussed (I wonder which of the problems in the medium-easy part of the Luxor contests you liked), but I'm interested if such a change would help?
And, again, thank you for your feedback!
Thanks so much for the thoughtful reply--I really appreciate your willingness to engage with my comments. A few responses:
I haven't looked at these problems closely and probably won't until I'm more emotionally removed from the contest, but happy to send you a message if I end up spending time with them in the future :)
I didn't phrase this especially well--what I meant to say is that these were the only eight problems solved by a large number of non-gold medalist teams, not that every team could approach these eight problems. (My main point is that these eight problems were the main ones that affected most teams' experience at the contest, which is why I felt okay giving feedback without full information on the four hard problems.) I agree that J/L are in a different category from the other six.
I think I agree with this--I'd still feel like L contributes to the implementation-heavy nature of the problemset, but in isolation I wouldn't mind it too much if every team knew about the testing tool and if there were more other problems that involved more thinking time/less implementation time. (The main other thing I don't love about it is that "did you notice the edge case" ended up being a significant determinant of the medals, and stylistically I prefer for awards to be determined by "did you come up with the substantive idea for a hard problem". I think WF22 R, WF23 B, and WF24 J are all problems I like better as medal deciders.)
Agreed. I do think, though, that even if the easy problems went faster than this, it'd still be nice to have more novel ideas since the weaker teams will spend most/all of their contest on these problems (and even stronger teams can enjoy easy problems if they're nice). WF22 Q and U were good examples of this--they were solvable by most teams, but the ideas were novel and they're still interesting to solve for very strong teams.
I don't think I'd characterize J this way; it felt like an appropriate difficulty for where it was in the set. My only issue with J is that data structures are naturally a little repetitive/implementation-heavy, which is fine if they're some of the most implementation-heavy problems in the set (which is usually the case). I just didn't love another standard-ish problem in the context of the other, more standard problems in this set. (In isolation, I think J is on the better end of DS problems and I think it'd be a good problem in most ICPC sets.) Re: L, I don't think I'd characterize it as easy in general, I just think the vast majority of the difficulty comes from the implementation and noticing the edge case and not from the general idea.
I think a lot of the stronger teams, especially those with former OI contestants, are pretty well-trained on problems where you take a segtree and basically use it to encode a DP state. (Nile from this year's IOI is spiritually similar, as a particularly recent example.)
I think these would both be good changes (especially clearly indicating the testing tool for L). I think if we knew about the testing tool, my feelings after the contest would mostly have been disappointment in my own skill issue on J (to be clear, I think J was a pretty good problem, I'm just mad at myself for messing up on it) rather than frustration at missing L for reasons that felt a little bit out of my control.
I do think -F and -some other easier problem might have left some less experienced teams without enough approachable problems to do, so ideally some other easy problems would be added in their place. (That said, my team finished the easy problems in a little under two hours, so they weren't as much of a bottleneck for us as they were for a lot of teams. Thus I wasn't upset with them keeping us from the harder problems, it was more that I was hoping to see some cool new ideas in the early half of the contest.)
WF22 Q, U and WF23 H were all especially good easy/medium problems (and I didn't especially mind any of the easy problems in those WFs except maybe WF23 I, which felt a little silly). Turning Red was a little standard, but other than that I felt like the easy-medium problems all involved original ideas (and I didn't mind Turning Red because it was the most standard thing in the set).
Some feedback on the medium/hard end from Luxor: I really liked Three Kinds of Dice--"hidden convex hull problem" is always a satisfying thing to figure out and it doesn't feel like it's been overdone at this point; it really isn't obvious from the problem statement that there will end up being a geometry component. WF23K (Alea Iacta Est) is one of my all-time favorite ICPC problems, although I'm disappointed that it could be solved using iterative methods and I'm disappointed in every team at the actual contest for solving it this way :) I solved it using the intended solution, which I think is a quite nice way to understand the problem, and figuring out how to represent the states in a useful way is a satisfying puzzle. This kind of graph search-style approach was also not something I had seen before, so the idea really felt novel and exciting.
Also, while I generally don't like implementation deciding medals at WF, I think WF22X (Quartets) was on the better end of implementation-heavy problems, because you actually had to think some about how to represent the information effectively in order to make the implementation work. (Amusingly, when I VCed WF22, this was the third problem I attempted, after the two easiest problems. I think I got midway through implementing it, but when I realized I'd have to do the matching step I decided there was no way it was actually on the easy end of the set, and I ended up coming back to it later.) While R and X were collectively a little implementation-heavy, I think WF22R/V/X worked well at collectively deciding medals, and I really liked WF23B/K as medal deciders (if not for the fact that WF23K basically ended up being a test of "do you try to implement the iterative approach" rather than of whether you actually come up with the intended idea).
Thanks for all your work on these contests!
Thanks again! I'll try to summarize what I think is actionable (and I'll briefly comment on what I think are judgement errors on our part that are hard to make actionable).
The contest would benefit from more "nice ideas" the easy-medium part. This is, of course, subjective, but I think it's clear that at least A, C and I don't even attempt to be "nice idea" problems. This was exacerbated by the fact that the "first hard problems" (L and J) contained one that wasn't an idea problem (L), and one where the idea was somewhat standard, and so less likely to excite and amaze (J) (what I mean here is that I think people would describe J as "nice" or "decent", but unlikely to describe it as "beautiful").
Out of the three remaining problems; I think you're right that there's nothing in there that would bring a smile like, say, WF23'Q (Container Shuffle). B has a nice idea (I'd probably see it as similar to WF23'Y, Compression), but it's just too easy a problem to register for the stronger participants; D is interesting, like many greedy problems are, but not awesome (I'd probably compare it to WF22'H, Jetlag, although it was, I think, somewhat harder), and I think we (judges) totally overestimated the difficulty of coming up with the right sequence of steps in F.
The contest would, somewhat relatedly, benefit from less implementation focus on the medium-easy end. Here, I think A, C and I are the main contributors, F doesn't help, and the fact that the next two problems are L and J doesn't help either (and, of course, the miss on the testing tool hurts).
I'll also comment that figuring out what are going to be the medal-deciders is super-hard, and possibly impossible. Looking back, I still don't understand why teams focused on solving L and J, rather than attacking, say, K. I think in practice there's a lot of "herding" in these contests (people attack problems that other people solved, on the assumption they're easier), and that's somewhat of a chaotic process.
I agree with a lot of this summary--one minor thought:
After reading this comment, I spent a little while thinking about K, and the approach isn't obvious to me. Maybe with a little more time the solution would become obvious, and then the implementation would be shorter than J/L, but I do think that teams will naturally gravitate towards problems where the solution idea materializes fastest.
I think rather than a scoreboard effect, it's more likely that the judges underestimated how good strong ICPC teams are at segtree problems, how quickly teams will see the general idea for L, etc. (I also think you should expect the number of teams that attempt L to be biased up by the fact that the hard part of the problem is pretty subtle and one could easily start typing L without realizing it's an issue.) I don't blame you at all for this, it's notoriously difficult to estimate the difficulty of your own problems (I've had very confident/very incorrect opinions about contests I've tested before), but it does seem like a bit of a leap to say that this was a leaderboard effect.
I think one thing is to remove problems that have been seen too many times (like A and I) and try to balance the ratio between implementing and thinking by simply removing L.
here is my feedback, I will be talking of the problems ABCDFI. I did not have time to try any other problems unfortunately.
Problem B : This is a great first problem imo. Simple and short. Only issue is the statement being somewhat informal leading to it being misintrepretable. More on that later.
problem F : Its just meh. From the onset, it is pretty obvious what to do. Each step is obvious and standard from the previous. Still, i think it's fine to have one such problem. Something I would like is : removing the recovery part of the problem. Maybe it only saves 5-10mins, but I think such small things of "caring about the contestant" adds up.
Problem C : Please kill implement the statement problems....they definitely should not exist. They are boring and only time killers, and you have to hope you don't get WA and lose even more time. There were other issues with this too, such as not being clear about whether brute force passes (it did) and the big negative years issue.
Problem I : I have seen this at least 2 — 3 times before, and so have most experienced contestants. I don't understand how WF jury thought it is fine to use this despite it being so repeated already. Surely most members from the WF jury have also encountered the exact same problem before? So, the only explanation I can think of is that they think its fine because no "internet access".
From a first time solving, O(n^2) is somewhat ok, while O(n) is just tedious and boring. (Fun fact : I was trying a puzzle by huawei 2 days before the contest, and it reminded me of this very problem. I even tried to remember its source and look it up then, but i was unsuccessful)
Problem D : Personally, I made a lot of mistakes in this problem which i found after stress testing, and that cost me a lot of time. Nevertheless, I think the problem was completely fine and decent.
Problem A : I have seen the idea before, and all that was left for me to do is actually implement the lines thing, which is very tedious personally for me. unfortunately, I ran out of time in WF while debugging this (I had a division by 0 error for a long time). Here are some variations I would have liked more :
Lower constraints to allow $$$O(n^2 \cdot log(n))$$$ solutions : This in itself would be a good improvement I think
Remove the linear function section altogether : Either, make the function simpler (like ranges of constants, instead of ranges of linears) or change it to something like "functions are hidden, but you can query the integral in a range".
For the "you are allowed to query integral of a range", There exists a cool solution in nlog^2 using Divide and Conquer. I want the problems to be more focused on ideas like these, rather than pointless wasting time thinking how to handle several linear functions within the time limit. (Funfact : Infact, i was told how to solve this very problem by our IOI leader while travelling to IOI 2023)
Summary
Within the 6 problems I mentioned, I think only B, D and F are fit to be used as is. A could have been made a lot better, while I and C just need to go.
I would very much enjoy if ICPC WF wasn't so implementation oriented, where the difficulty lies in implementing the idea rather than coming up with the solutions. I was implementing for maybe 3 — 4 hours in contest. Somebody rightly mentioned "ICPC gives you 15 hours of thinking time, and 5 hours of implementing time, while in reality you need the reverse".
Strong contestants are held back from trying hard problems. Weaker contestants are left frustated as they keep failing to implement correctly. I don't think it helps anyone.
Somewhat related to this is "Try to make the contestant's lives easier". Maybe you found a cool problem in $$$O(n^2)$$$, but then it is tedious (and also much harder) to solve in $$$O(n)$$$. I would request authors to not use the harder version. Anytime you want to use a harder version, I think you should always argue if it adds much to the problem compared to the amount of effort needed. For example, problem A linear functions and problem I $$$O(n)$$$ doesn't add much to the problem, while they both take considerable amount of effort.
Statements : There were multiple places where I had ambiguity in understanding statements. Personally, I prefer Atcoder style statements, but I can understand having stories. What I think is really really necessary, and why this issue even arises in the first place is not being mathematically formal in the important parts. Write your story, but please also give me an accurate definition. The best example can be gotten in geothermal's suggestion to B.
I agree with a lot of this, but I disagree with a few of your points on A:
Btw, you should take a look at the scoreboard for A. Since its practically impossible to have wrong idea (your first guess is also the solution) these many penalties were all caused by a mix of implementation and tle issues.
I did not implement n^2 logn myself because i do not trust it to pass in n <= 5000 anymore (i have bad experiences with this even just a simple sort). iit delhi team did however, and they got tle before they optimized to n^2, i am not sure whether they had log (e) or log(n)). Some other of my friends also claimed to have tle issues with n^2 log(n).
As for issues, i ran into division by 0, and epsilon issues causing RTEs (totally my fault i should be more careful). Then I fixed both 2minutes before contest end and got WA (no time to fix)
I was not a participant, but I read some of the easier tasks. Here's my thought:
B: My initial interpretation of the task is that the game master can call any number in the sheets, but the distribution of the numbers in the sheet does not matter. So if number A appears twice and number B appears once in the sheet, my interpretation is that the game master can call number A and B infinitely many times, and each number has a probability of 0.5 to be called each time.
C: Annoying hardcoding date-parsing task, but I'm not surprised this appears on WF.
F and I: I am surprised that these tasks appear on WF. As mentioned by others above, these tasks are just too classical.
Can someone explain proof for A and the DP states for I? I watched the solution videos but couldn't understand properly.
For A, if I understood correctly, we start from the leftmost part of the billboard, $$$l = 0$$$ and see which sponsor would require the least $$$r$$$ such that the area under the curve in $$$[l,r]$$$ covers $$$\frac{1}{n}$$$ of their area, and we assign this part of the billboard to that sponsor, and similarly proceed for the rest of the billboard and remaining sponsors. I don't understand why is it optimal to assign sections this way, is it not possible to have a better solution by assigning the first section of the billboard to some other sponsor?
For I, I didn't really understand anything that was mentioned in the video, it seemed a little incomprehensive to me, I understood that we do binary search and some tree DP but didn't understand the states of the DP, can someone explain the states in a simple way, I'll try to think of the transitions myself, thanks!
its a simple proof by induction that it can always be solved by assigning in this way, and thus while it may be suboptimal for different condition, it does satisfy the required condition. (Everyone has at least 1 — 1 / n part left after removing the first guy, just normalize their remaining parts to 1, and we go into a smaller subproblem thus by induction it is always solvable)
Here is my solution. first of all, of course binary search. Let the parameter be $$$k$$$. Let's come up with $$$O(n^2)$$$. Let $$$d(u, v)$$$ be the distance between $$$2$$$ vertices.
Let $$$a_u = maximum(d(u, v))$$$ such that $$$v$$$ is unmarked and $$$v$$$ lies in the subtree of $$$u$$$. Pick any node with $$$a_u \le k$$$ but $$$a_{par_u} > k$$$ and mark it, and mark all the nodes which satisfy $$$d(u, v) \le k$$$. Continue this process till all nodes are marked.
It's fairly obvious to see that the above greedy is optimal, so we only need to optimize it to $$$O(n)$$$. Here the details are slightly complicated, the basic idea is we will start from the leaves and go upwards, maintaining the value of $$$a_u$$$. Whenever $$$a_u + parent_w$$$ exceeds $$$k$$$, we need to mark the node $$$u$$$. Note that as a result of marking $$$u$$$, some nodes in other subtrees of $$$par_u$$$ might also get marked, so you will need to maintain the "minimum distance chosen node for each $$$u$$$ in it's subtree".
Another explanation for I (probably the same logic under the hood, but hopefully the motivation is helpful):
Let's assume you've thought to try binary search and some kind of tree DP (I think once you've seen enough problems both of these are fairly motivated; tree problems that don't relate to things like path queries/LCA structures/etc often involve tree DP and the duality between "minimize the cost that can be achieved using X operations" and "minimize the number of operations necessary to achieve Y cost" comes up pretty frequently). It's pretty natural to store the number of fire engines used in a subtree in your DP state, but what else might you want to keep track of?
Let's think about what determines the best possible state for your subtree. We'd obviously rather use fewer fire engines in the subtree. Aside from that, cases where the entire subtree is covered (and we may have a station that can move upwards and cover vertices outside the subtree) seem better than cases where some vertex is not covered (and thus, some vertex up above needs to cover a vertex in our subtree). Within the former case, we'd rather have our last station have as much range left over as possible, and within the latter case we'd rather the deepest uncovered vertex be as close to the root as possible (so that it's easier for some fire engine outside this subtree to cover our vertex).
It turns out that we can compare these states greedily. The intuition is that if we have two options for the state of subtree $$$v$$$, one which contains $$$f$$$ engines and the other containing $$$f+1$$$ or more fire engines, then when we move to the parent of $$$v$$$ from the first state, we can achieve the best possible state using $$$f+1$$$ fire engines (plus however many engines are used in the neighbor subtrees of $$$v$$$) by placing a fire engine at the parent of $$$v$$$, so there's no reason to ever use $$$f+1$$$ or more fire engines in the subtree of $$$v$$$.
With that in mind, our state will include the minimum possible number of fire engines that we can use in the subtree of $$$v$$$, and an indicator showing whether it is possible to cover every vertex in this subtree while using that number of fire engines. If so, then we also store the greatest possible range a fire engine could move outside of our subtree, and if not, we store the greatest depth within the subtree of a vertex not covered by a fire engine. As you suggested, I'll leave the transitions as an exercise to work on.
When will it be available for upsolving?