Numbers on Cubes
Autumn Tournament (2020)
Submission name: kub.cpp
Problem summary
Each cube has six digit-labelled faces, possibly repeated. Choose and arrange distinct available cubes to display a positive integer without leading zeroes. Find the smallest positive integer that cannot be displayed. A cube can contribute at most one digit.
Source clarification. The wording initially mentions an n-digit display, but the original samples require shorter numbers (for example 6 from five cubes). The intended problem therefore permits using a subset of the cubes.
Input
n, followed by n strings of six digits.
Output
The smallest positive integer that cannot be formed.
Constraints
1 ≤ n ≤ 100000; each face is a digit from 0 to 9.
Worked example
Original statement sample.
Input
3 123456 789012 345678
Output
90
Solution analysis
- Represent each cube by a 10-bit mask of its distinct digits. To display a number, assign every digit occurrence to a different compatible cube. Hall’s matching condition says this is possible exactly when, for every subset S of the ten digit types, the number of required occurrences from S is at most the number capacity(S) of cubes containing at least one digit in S. This reduces matching to just 1023 subsets.
- Count masks, then use subset-sum dynamic programming: sub[mask] counts cubes whose masks are contained in mask. Thus capacity(S) = n − sub[allDigits XOR S], because only cubes entirely outside S are unusable for S. If a number is impossible, some S contributes at least capacity(S)+1 occurrences.
- For each S construct the smallest positive integer violating that condition. If S contains a nonzero digit, use its smallest nonzero digit first, then capacity(S) copies of its smallest digit. If S={0}, use a leading 1 followed by capacity(S)+1 zeroes. Compare candidates first by length, then lexicographically. This also covers numbers needing more than n cubes.
- In the sample only cube 789012 can show 9 or 0, so capacity({0,9})=1. The number 90 needs two occurrences from that subset but only one eligible cube. The candidate is 90; all smaller numbers satisfy every subset condition. Store the answer as a string: its length can grow with n.
Why it works
Hall’s theorem gives a violating digit-type subset for every impossible number (occurrences of equal digits have identical neighbours). The candidate for that subset has the fewest digits and lexicographically smallest arrangement that can violate it, accounting for leading zeroes. Every generated candidate violates its subset condition and is impossible. Therefore the smallest generated candidate is exactly the smallest impossible positive integer.
Watch out. Repeated faces on one cube do not create extra capacity. Do not treat digit frequencies alone as sufficient: several digits can compete for the same cubes. The zero-only subset needs a nonzero leading digit.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
const int full=(1<<10)-1;
vector<int>subset(1<<10,0);
for(int i=0;i<n;i++){
string faces;
cin>>faces;
int mask=0;
for(char digit:faces){
mask|=1<<(digit-'0');
}
subset[mask]++;
}
// After this transform, subset[S] counts cube masks contained in S.
for(int bit=0;bit<10;bit++){
for(int mask=0;mask<=full;mask++){
if(mask&(1<<bit)){
subset[mask]+=subset[mask^(1<<bit)];
}
}
}
string answer;
for(int mask=1;mask<=full;mask++){
int capacity=n-subset[full^mask];
int smallest=0;
while((mask&(1<<smallest))==0){
smallest++;
}
int first=1;
while(first<10&&(mask&(1<<first))==0){
first++;
}
int length=capacity+1;
if(first==10){
length++;
}
if(!answer.empty()&&length>static_cast<int>(answer.size())){
continue;
}
string candidate;
if(first==10){
candidate="1"+string(capacity+1,'0');
}
else{
candidate=string(1,char('0'+first))+string(capacity,char('0'+smallest));
}
if(answer.empty()||candidate.size()<answer.size()||
(candidate.size()==answer.size()&&candidate<answer)){
answer=candidate;
}
}
cout<<answer<<'\n';
}