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.
1. Add a variable for each node, and a variable for each output edge from stations.
2. For each reservoir add equality constraints to the sum of incoming edges with the coefficients given in the problem.
3. For each station add equality constraints between the weighted sum of its inputs (which is 1 for the root station) and its outputs (which are the variables we added).
4. Add an out_edge >= 0 constraint for each output edge on stations to forbid illegal negative flows.
5. Add a variable m which is constrained to be less than all the output station variables.
6. Maximize m.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.
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.
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!
> 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.
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...