I was onsite today watching the contest live, and great atmosphere all around. One surprising outcome: the team in 17th place solved the same number of problems as the team that won gold in 4th place. Hopefully that isn't too demotivating to any team and we can see better separation in the future. After all, it can only mean that the problemsetters underestimated the contestants ;)
Congratulations to all the teams!
> the problemsetters underestimated the contestants
Except for problem C, which was only submitted by 4 teams, all unsuccessfully.
I don't blame them. That problem statement seems to be deliberately confusing.
Yes, I meant to imply that the problemsetters are to blame.
I doesn't seem that unclear to me? I absolutely don't have the skill to solve it, but it took <2 minutes to understand the problem and goal.
It doesn't seem that hard to solve to me either. It's solvable with basic linear programming.
This happens every now and then. Basic LP isn’t conceptually so bad, but the ICPC environment doesn’t come with CPLEX or Gurobi, let alone a less fancy open source tool. And there is definitely not a copy of cvxopt around to make this easy. Even if you want to quickly kludge up an interior point solver, you don’t have a linear algebra package available (sorry, no numpy or BLAS).
What you can do is to submit a 25 page PDF that the organizers will print and stick on your desk for the competition. And you could put a careful implementation of a very basic simplex solver using dense matrices that is optimized for ease of transcription, taking up, say, half a page. You would hope not to use it because it’s absurd, but then if this problem C shows up, the fastest typist on the team can type it in verbatim.
If I, personally, did this and won the contest as a result, I would feel slightly bad. In my opinion, the contest organizers should either provide an LP solver or refrain from giving obvious LP problems like this.
Obviously OpenAI could kick everyone’s butt by typing faster than any human and by effectively having a large memorized library of pre-written code. Honestly, LLMs vs humans in the ICPC feels a bit like IBM’s old Jeopardy stunt where the machine had a huge advantage in its ability to push the button.
The team manual I referred to when I was in university does in fact contain such a basic simplex LP solver: https://github.com/ludopulles/tcr/blob/master/tcr.pdf (page 22).
I'd just like to clarify that I'm not saying this is necessarily the solution the problem writers were looking for, or that it will run within the allocated time. Just that it's a feasible solution.
Amazing! Thanks for sharing.
The farthest I got in the ICPC was regionals. I was tasked to make the team binder. I was a budding LaTeX enthusiast then but our coach wanted me to do it in...MS Word. Not that he didn't know LaTeX either (he's a published math/CS researcher after all), it's just the cultural ubiquity and comfort of MS Word. :(
The result was something more like https://github.com/ludopulles/tcr/blob/master/TCR-Sudo.pdf . I love how information-dense tcr.pdf looks in comparison. They even have a table of contents!
Wow, incredibly interesting to see what one of these manuals looks like! Thanks for sharing.
Mine did too :). But I never used it except for practice.
I suspect the lack of success of the teams resulted from overfitting for the more standard pattern that is solving a max flow, and I also suspect the organizers are deliberately using this to trick the contestants. Spending time to practice coding vanilla algorithms to solve either max flow or a linear program is a waste of time for >99% of computer scientists.
Replying again, having actually read the problem more carefully: the problem isn’t that simple. There will be a few tens of thousands of variables. The LP is extremely sparse, and I’m sure a good solver could solve it within the time limit, but a little team-notebook-sized dense solver would take at least a few trillion operations to finish and would not be nearly fast enough.
As I mentioned in my other comment:
> I'd just like to clarify that I'm not saying this is necessarily the solution the problem writers were looking for, or that it will run within the allocated time. Just that it's a feasible solution.
I don't doubt there's a clever dedicated flow algorithm the problem writers intended instead of the blunt tool which is LP.
I solved C using LP. You may attempt to submit a solution here if you want to try: https://open.kattis.com/problems/brideofpipestream
You may view (one of) the judge's solution to this problem (and the rest of the problems) here: https://github.com/SnapDragon64/ACMFinalsSolutions/blob/mast...