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.

Allocation and Optimisation

There are three things to optimise:

1. Total time from first arrival to final output
2. Average time from arrival to end of the output ready (called TDR)
3. 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 and the total time, 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 further minimise TDR, you have to minimise the average time for 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 and become queued. 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 might 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. Some degree of randomization is needed to ensure tasks with certain R_out values are distributed over the remote computers.

To minimise the decode 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 so is harder work to capture. 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 and gentle criticism

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. I believe the competition would be better if "somewhat similar" was better defined, perhaps 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 without reconstructing some of the test cases. But it does seem to be an unnecessary piece of work. The competition would have been better if the sample tests had been published together with more worked examples than just the Example 1 ad 2 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

16356.924 points

#1 points 500.00 tp=0.022222 mean_tdr=30.000000 mean_tpot=0.000000 
#2 points 500.00 tp=0.005755 mean_tdr=126.158679 mean_tpot=0.000000
#3 points 500.56 tp=0.003880 mean_tdr=1329.849832 mean_tpot=56.462313 
#4 points 803.20 tp=0.059310 mean_tdr=465.222957 mean_tpot=80.093178 
#5 points 478.36 tp=1.173719 mean_tdr=1497.254452 mean_tpot=65.194854 
#6 points 406.05 tp=0.734853 mean_tdr=3464.632192 mean_tpot=52.371189 
#7 points 922.70 tp=0.009621 mean_tdr=860.122989 mean_tpot=63.174151 
#8 points 835.04 tp=0.013324 mean_tdr=1086.885839 mean_tpot=93.943311 
#9 points 689.54 tp=0.004384 mean_tdr=6642.505060 mean_tpot=0.000000
#10 points 684.20 tp=0.007630 mean_tdr=182681.018486 mean_tpot=83.339770
#11 points 500.18 tp=0.000007 mean_tdr=32780482.884393 mean_tpot=16199.089335 
#12 points 798.61 tp=0.000024 mean_tdr=1057070.901985 mean_tpot=921.802736 
#13 points 733.00 tp=0.027147 mean_tdr=1678.364473 mean_tpot=69.414102 
#14 points 415.26 tp=0.003564 mean_tdr=192.489397 mean_tpot=184.378198
#15 points 882.67 tp=0.000009 mean_tdr=7741873.670045 mean_tpot=0.000000 
#16 points 981.13 tp=0.029799 mean_tdr=41824.181140 mean_tpot=71.672983
#17 points 943.20 tp=0.000520 mean_tdr=8526717.412787 mean_tpot=24464.523308 
#18 points 916.20 tp=0.000009 mean_tdr=17713632.378469 mean_tpot=0.000000 
#19 points 946.99 tp=0.707554 mean_tdr=150.745068 mean_tpot=205.856666 
#20 points 998.18 tp=0.005607 mean_tdr=1245.882662 mean_tpot=172.801195 
#21 points 967.02 tp=0.012490 mean_tdr=41861.056998 mean_tpot=0.000000 
#22 points 954.73 tp=39.863087 mean_tdr=2320.474649 mean_tpot=6.008085

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.