Sorting Across Restarts
National Olympiad — National round (2023 season)
Submission name: pravetz.cpp
Problem summary
Sort an unsigned array stored in an external memory service. Each call may use local variables, but all information needed by later calls must survive only in the supplied memory. The score rewards small per-call read sets and avoiding extra cells.
Input
Grader calls bool sort_array(int N, bool start); start is true only on the first call. Read unsigned int get_memory(int index), write void set_memory(int index, unsigned int value).
Output
Return false to request another call and true once cells 0…N−1 are sorted. Submit pravetz.cpp including pravetz.h, without main or standard I/O.
Constraints
20 ≤ N ≤ 65536; 0 ≤ ai < 65536; cells 0…2N exist; extra cells initially zero; at most 10000000 calls. Repeated simulations must issue identical memory operations. Score = extra × min(1,num/gets), with extra=1 without extra memory and c otherwise. Subtasks (N bound, value bound,c,num): (1024,N,0.7,10), (16384,N,0.3,3), (65536,N,0.3,3), (16384,65536,0.3,4).
Worked example
The official communication uses N=5 outside the graded bounds and shows one possible sequence. The displayed input/output is a local mock summary of its initial and final arrays, not a standard-input submission protocol.
Input
5 2 1 1 0 4
Output
0 1 1 2 4
Solution analysis
- Keep a max heap in the original array and reserve cell N for the phase and next operation. Heap construction sifts roots N/2−1 down to 0; extraction swaps the maximum with the last active element and restores the shorter heap. One complete sift is one call.
- An unsigned state below 2^31 stores the number of roots still to build. Its high bit marks extraction, and its low bits store the last active index. No mutable C++ global state is needed, so a restart between calls cannot change the operation sequence.
- For the demonstration array, heap construction produces a maximum of 4. Extraction fixes 4 at index 4, then 2 at index 3, then the two 1s, leaving 0 at index 0. This is a full-domain sorting method with an explicit score tradeoff: it uses extra memory, and one call may inspect up to 35 distinct cells.
Why it works
Bottom-up heap construction is valid because both child heaps have already been built before their parent is sifted. A sift moves the larger child upward until its saved value can be placed without violating heap order. Extraction fixes the active maximum at its final position and preserves a heap on the remaining prefix. Induction proves sorting. The only persistent state is in cell N; deterministic comparisons and writes give identical operations in every simulation.
Watch out. Do not retain the heap cursor in a C++ global. Compare values as unsigned. Include the persistent state cell when measuring gets.
Commented C++17 solution
Actual grader submission. This implementation deliberately trades score for simple bounded sifts; it does not claim maximum score. The extra-memory multiplier c applies.
#include"pravetz.h"
#include<algorithm>
// Algorithm: Keep a max heap in the original array and reserve cell N for the phase and next
// operation.
void sift(int root,int size){
unsigned int value=get_memory(root);
while(2*root+1<size){
int child=2*root+1;
unsigned int next=get_memory(child);
if(child+1<size){
unsigned int right=get_memory(child+1);
if(right>next){
++child;
next=right;
}
}
if(value>=next){
break;
}
set_memory(root,next);
root=child;
}
set_memory(root,value);
}
bool sort_array(int n,bool start){
const unsigned int extracting=1U<<31;
if(start){
set_memory(n,static_cast<unsigned int>(n/2));
return false;
}
unsigned int state=get_memory(n);
if((state&extracting)==0){
if(state!=0){
sift(static_cast<int>(state)-1,n);
set_memory(n,state-1);
}
else{
set_memory(n,extracting|static_cast<unsigned int>(n-1));
}
return false;
}
int end=static_cast<int>(state&~extracting);
unsigned int maximum=get_memory(0);
unsigned int last=get_memory(end);
set_memory(0,last);
set_memory(end,maximum);
sift(0,end);
if(end==1){
return true;
}
set_memory(n,extracting|static_cast<unsigned int>(end-1));
return false;
}