These notes are written by someone who didn't use AI, who did probe the public test cases fairly aggressively, and who was placed 125th on the scores of the public test cases.
I didn't go much beyond implementing some forms of greedy algorithm, with a certain amount of switching the greedy criteria depending on what appears to work.
There are three things to optimise:
- Total time from first arrival to final output
- Average time from arrival to end of the output ready (called TDR)
- Average time first output to last output (called tpot)
For most of the test cases, the critical resource is the processing power of the remote computers. To minimise the required remote processor usage, for each task we do the whole prefill (P PROC) operation in one go, and batch up the decode (D PROC) operations to do as many tasks as possible at once. (There are some tests (e.g. case #19) where a batch of 69 tasks is faster than many other batch sizes.)
To minimise TDR, we do all prefill (the P PRE/P PROC/P POST) operations first. After they have completed, we do the decode (the D PRE/D PROC/D POST) operations. The decode operations can be batched together, and usually the processor time required is smaller for larger batches. So the greedy approach is to combine the operations into large batches.
To minimise tdr, you have to minimise the time for the prefill operations. Generally the time to process larger (larger l_in) tasks is greater than the time to process smaller tasks. And at some stage the tasks are limited by processing or bandwidth. If the time for each task is A, B, C, D, ..., then the average time is roughly (A + (A+B) + (A+B+C) + ... )/N. To minimise this average we want to sort the tasks so that A<B<C<D<.... So we aim to process smaller tasks first.
The tasks have to be distributed over the remote computers. Sometimes the tasks arrive with sizes in a definite cycle (say 1, 2, 4, 8, 1, 2, 4, 8, 1, ...), and the number of output tokens for each task follows a similar cycle. If the tasks are allocated sequentially to remote computers 0,1,2,3,0,1,2,3,0,... then this would result in all size 1 tasks going to the same computer. Generally it is better for each remote computer to have a mix of tasks, so we need some sort of allocation algorithm.
To minimise the ouput stage time, there seem to be two main choices:
First choice is to do one D PRE stage for all tasks, then a batch of D PROC on each remote computer, and then one D POST stage. This minimizes the overheads caused by the S and latency-in-ms values from the settings.
The second choice is to interleave the local tasks with the remote tasks. So roughly half the tasks are running on the local computer while the other half are running on the remote computer. And then swap over. This will make parallel use of the local and remote computers, and parallel use of the upstream and downstream communication paths.
The problem description has a mechanism to split the P PROC stage into pieces, each piece is a non-empty segment of parts numbered [ls,le). I never found a test case where this was useful.
Probing
It was relatively easy to probe the test cases and reconstruct them. If the submitted code sent a string where the judge expected an integer, the judge would generate an error of the form
4: WRONG_ANSWER [15ms, 0MB]: wrong answer bad integer: the-bad-string-upto-about-450-characters
so one submission could fetch about 450 characters of information. At this rate it doesn't take a huge number of submissions to reconstruct most of the test cases. Case 21 appears to have 2000 tasks with random arrival times. The others test cases are much more regular.
At some times of day codeforces enforced a limit of 2 submissions in 15 minutes. At other times there were no such restrictions.
A few more thoughts
We have to assume that the final test cases will be somewhat similar to the provisional test cases. Having to guess how Huawei will implement "somewhat similar" is deeply unsatisfying. The competition would be better if "somewhat similar" was better defined, either as some python code that generates more test cases, or as some sort of probability distributions.
Decoding the public test cases seems to be an obvious step. I would have struggled to implement the scoring code correctly with reconstructing some of the test cases. The competition would have been better if the sample tests had been published together with more examples than just the Example 1 in the problem description.
Hiding the number of tasks, or the number of iterations for each task, just introduces guesswork. This doesn't improve the challenge.
My Best Results
Finally
Thank you for running the competition. I am amazed to see how much can be done with AI solvers. I look forward to seeing the final results.
