Compress an LCS into a Short Hint
Autumn Tournament (2021)
Submission name: hint.cpp
Problem summary
Implement two grader functions. genHint receives sequences A,B and one optimal longest common subsequence and returns a bit vector. solve receives only A,B and those bits and must reconstruct some optimal LCS. Calls run in separate processes, so shared globals cannot transmit information. Shorter hints earn a higher score.
Source clarification. The block corridor uses at most639 bits, meeting the full hint-length threshold; this is not a claim of official judge acceptance.
Input
Official interface: genHint(a,b,sol) and solve(a,b,hint), declared by hint.h. The included LOCAL driver reads N M, A, B, K, and K elements of an optimal LCS.
Output
Officially return the bit vector and reconstructed LCS. The LOCAL driver prints hint length, LCS length, then its values.
Constraints
1≤N,M≤200000; 0≤Ai,Bj<min(N,M). Score multiplier min((640/(L+1))^0.3,1), where L is the largest hint length in the subtask.
Worked example
New LOCAL-driver worked example; the original interface statement has no sample.
Input
3 3 0 1 2 0 2 1 2 0 2
Output
4 2 0 2
Solution analysis
- An LCS is a monotone alignment through the usual dynamic-programming grid. Divide rows and columns into blocks of side B=ceil((N+M)/640). Instead of sending all matched pairs, send the downward and rightward moves of a block path containing them.
- Greedily embed the supplied optimal sol into both sequences to find increasing match coordinates. Start in block(0,0). For each match move right before down to its block, encoding right as1 and down as0. Finish at the bottom-right block. Right-before-down preserves the diagonal predecessor needed for a matching pair. The hint has ceil(N/B)+ceil(M/B)-2≤639 bits.
- Decoding recovers each row block’s contiguous visited column-block interval. Run the ordinary LCS recurrence only in this staircase corridor. Values outside the previous row’s valid range are unreachable, not zero; along a new left boundary carry the preceding value vertically.
- The supplied optimal alignment can move monotonically through these blocks. The encoder’s right-before-down choice allows its matching diagonals and the skips between them. Thus at least one global optimum is retained. Restricting the grid cannot create a larger LCS, so the corridor optimum is exactly the original optimum.
- Keep only two score rows. For reconstruction store a two-bit direction per visited cell: up,left,diagonal. Per-block-row offsets locate these packed directions. Left boundary cells implicitly move upward. This is much smaller than storing an integer at every corridor cell.
- For A=[0,1,2], B=[0,2,1], sol=[0,2], the block size is1. After match(0,0), reach match(2,1) with right,down,down; finishing adds right. Hint1001 has4 bits. The corridor retains matching0 and2, and the decoder returns[0,2].
Why it works
The bits reconstruct the encoder’s corridor without hidden shared state. Every supplied match and a monotone alignment connecting the matches remain in it. The restricted recurrence considers only valid subsequences and retains one known globally optimal subsequence. Therefore its optimum equals the global optimum; backtracking returns an optimal LCS.
Watch out. Computing sol is not part of genHint: it is provided by the grader. Do not share state between calls. Outside-corridor states are unreachable. Include hint.h without main for judge submission; use -DLOCAL for the documented educational driver. Multiple optimal LCS outputs may exist.
Commented C++17 solution
Grader task: judge builds hint.cpp with hint.h and no main. Compile with -DLOCAL for this standalone educational driver.
#include<algorithm>
#include<cstdint>
#include<iostream>
#include<limits>
#include<vector>
#ifndef LOCAL
#include"hint.h"
#endif
using namespace std;
vector<bool>genHint(const vector<int>&a,const vector<int>&b,const vector<int>&sol){
int n=static_cast<int>(a.size());
int m=static_cast<int>(b.size());
int blockSize=max(1,(n+m+639)/640);
int row=0;
int column=0;
int ai=0;
int bi=0;
vector<bool>hint;
for(int value:sol){
while(a[ai]!=value){
++ai;
}
while(b[bi]!=value){
++bi;
}
// Right before down preserves the diagonal predecessor of each match.
while(column<bi/blockSize){
hint.push_back(true);
++column;
}
while(row<ai/blockSize){
hint.push_back(false);
++row;
}
++ai;
++bi;
}
while(row<(n-1)/blockSize){
hint.push_back(false);
++row;
}
while(column<(m-1)/blockSize){
hint.push_back(true);
++column;
}
return hint;
}
vector<int>solve(const vector<int>&a,const vector<int>&b,const vector<bool>&hint){
int n=static_cast<int>(a.size());
int m=static_cast<int>(b.size());
int blockSize=max(1,(n+m+639)/640);
int rows=(n+blockSize-1)/blockSize;
vector<int>low(rows);
vector<int>high(rows);
int row=0;
int column=0;
for(bool moveRight:hint){
if(moveRight){
++column;
high[row]=column;
}
else{
++row;
low[row]=column;
high[row]=column;
}
}
vector<size_t>offset(rows+1);
for(int r=0;r<rows;++r){
int width=min(m,(high[r]+1)*blockSize)-low[r]*blockSize;
int height=min(blockSize,n-r*blockSize);
offset[r+1]=offset[r]+static_cast<size_t>(width)*height;
}
vector<uint8_t>directions((offset[rows]+3)/4);
vector<int>previous(m+1);
vector<int>current(m+1);
int previousLow=0;
int previousHigh=min(m,(high[0]+1)*blockSize);
const int unreachable=numeric_limits<int>::min()/4;
for(int i=1;i<=n;++i){
int r=(i-1)/blockSize;
int first=low[r]*blockSize;
int last=min(m,(high[r]+1)*blockSize);
auto above=[&](int j){
return j>=previousLow&&j<=previousHigh?previous[j]:unreachable;
};
current[first]=above(first);
size_t index=offset[r]+static_cast<size_t>(i-r*blockSize-1)*(last-first);
for(int j=first+1;j<=last;++j,++index){
int best=above(j);
uint8_t direction=0;
if(current[j-1]>best){
best=current[j-1];
direction=1;
}
if(a[i-1]==b[j-1]&&above(j-1)+1>=best){
best=above(j-1)+1;
direction=2;
}
current[j]=best;
directions[index/4]|=static_cast<uint8_t>(direction<<(2*(index%4)));
}
swap(previous,current);
previousLow=first;
previousHigh=last;
}
vector<int>result;
int i=n;
int j=m;
while(i>0&&j>0){
int r=(i-1)/blockSize;
int first=low[r]*blockSize;
if(j==first){
--i;
continue;
}
int width=min(m,(high[r]+1)*blockSize)-first;
size_t index=offset[r]+static_cast<size_t>(i-r*blockSize-1)*width+j-first-1;
int direction=(directions[index/4]>>(2*(index%4)))&3;
if(direction==2){
result.push_back(a[i-1]);
--i;
--j;
}
else if(direction==1){
--j;
}
else{
--i;
}
}
reverse(result.begin(),result.end());
return result;
}
#ifdef LOCAL
int main(){
int n;
int m;
cin>>n>>m;
vector<int>a(n);
vector<int>b(m);
for(int&value:a){
cin>>value;
}
for(int&value:b){
cin>>value;
}
int k;
cin>>k;
vector<int>optimal(k);
for(int&value:optimal){
cin>>value;
}
vector<bool>hint=genHint(a,b,optimal);
vector<int>answer=solve(a,b,hint);
cout<<hint.size()<<'\n';
cout<<answer.size()<<'\n';
for(int value:answer){
cout<<value<<' ';
}
cout<<'\n';
}
#endif