Classifying Dice
National Olympiad — National round (2024 season)
Submission name: fair.cpp
Problem summary
Classify dice as fair or unfair from face counts. A die is fair with prior P; otherwise its probabilities are independent uniform [0,1] weights normalized by their sum. False unfair predictions cost X and false fair predictions cost Y. Minimize expected penalty.
Input
N M P X Y, then K, then K rows of N nonnegative counts, each summing to M.
Output
Print one 1 (fair) or 0 (unfair) per die.
Constraints
2 ≤ N ≤ 8; 15 ≤ M ≤ 40; 0.5 ≤ P ≤ 0.8; 0.3 ≤ X,Y ≤ 0.7; X+Y=1; K=100000. Score depends on realized penalty relative to a constant classifier and the author baseline; finite observations do not uniquely determine the labels. Write AP=penalty/K, BAP=min(PX,(1−P)Y), S=max((BAP−AP)/BAP,0), R=S/S_author. The score fraction is 0.3R/0.8 for R<0.8, otherwise 0.3+0.7[1−(1−(R−0.8)/0.2)^0.75], as specified by the official scoring rule.
Worked example
Official example predictions are illustrative, not mandatory. It incurs penalty 1.0 for the hidden labels described by the statement. Tests validate output shape and the independently computed decision rule, rather than forcing these predictions. With the fixed seed, this implementation prints 1,1,0,1.
Input
3 15 0.6 0.35 0.65 4 4 7 4 5 5 5 9 5 1 3 6 6
Output
0 1 0 1
Solution analysis
- Face labels are exchangeable under both models, so sort each count vector and use the entire sorted vector as a key. Six bits per entry suffice because M ≤ 40. This retains all likelihood information while combining symmetric observations.
- For sorted counts c, the fair likelihood is M! N! divided by N^M, the product of c! and the factorials of multiplicities of equal counts. Estimate the unfair likelihood by 500000 independently generated unfair dice and rolls. The fixed seed makes the implementation reproducible; ten pseudo-observations distributed according to the fair model smooth sparse keys.
- Choose fair when P × Lfair × X ≥ (1−P) × Lunfair × Y: these are the losses of saying unfair and fair respectively. For the example the balanced 5,5,5 pattern favors fairness and 9,5,1 favors unfairness. The published labels are illustrative and our statistical rule may differ.
- The exact Bayes rule minimizes expected penalty if its likelihoods are exact. Here the unfair probabilities are sampled, so the rule is an approximation on every allowed input size, not a proof that hidden labels are recovered. More simulations reduce sampling error but cost runtime.
Why it works
Permuting face names preserves both probability models, hence sorting loses no information relevant to the class. Multinomial counting gives the stated fair likelihood, including the number of distinct face permutations. Comparing the two posterior weighted losses yields the decision inequality after their common evidence denominator cancels. Monte Carlo frequencies converge to unfair probabilities; finite simulation and smoothing introduce estimation error, so no deterministic penalty or score guarantee follows.
Watch out. Normalize unfair weights before drawing rolls. Include multiplicities for repeated sorted counts. Apply X to rejecting a fair die and Y to accepting an unfair one. Do not interpret the illustrative output as uniquely correct.
Commented C++17 solution
Standard C++17 program using a fixed Monte Carlo budget. This is an explicitly approximate statistical classifier; realized score is not guaranteed. Runtime depends on the judge hardware.
#include<algorithm>
#include<array>
#include<cmath>
#include<cstdint>
#include<iostream>
#include<random>
#include<unordered_map>
using Counts=std::array<int,8>;
std::uint64_t signature(Counts counts,int n){
std::sort(counts.begin(),counts.begin()+n);
std::uint64_t key=0;
for(int i=0;i<n;++i){
key=(key<<6)|static_cast<unsigned int>(counts[i]);
}
return key;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,rolls,k;
double prior,falseUnfair,falseFair;
std::cin>>n>>rolls>>prior>>falseUnfair>>falseFair>>k;
const int simulations=500000;
std::mt19937 generator(20240309);
std::uniform_real_distribution<double>uniform(0.0,1.0);
std::unordered_map<std::uint64_t,int>frequency;
for(int trial=0;trial<simulations;++trial){
std::array<double,8>cumulative{};
double total=0;
for(int i=0;i<n;++i){
total+=uniform(generator);
cumulative[i]=total;
}
Counts counts{};
for(int roll=0;roll<rolls;++roll){
double sample=uniform(generator)*total;
int side=0;
while(side+1<n&&cumulative[side]<=sample){
++side;
}
++counts[side];
}
++frequency[signature(counts,n)];
}
std::array<double,41>factorial{};
factorial[0]=1;
for(int i=1;i<=40;++i){
factorial[i]=factorial[i-1]*i;
}
for(int die=0;die<k;++die){
Counts counts{};
for(int i=0;i<n;++i){
std::cin>>counts[i];
}
auto key=signature(counts,n);
std::sort(counts.begin(),counts.begin()+n);
double fairLikelihood=factorial[rolls]*factorial[n]/std::pow(n,rolls);
for(int i=0;i<n;++i){
fairLikelihood/=factorial[counts[i]];
}
for(int i=0;i<n;){
int j=i+1;
while(j<n&&counts[j]==counts[i]){
++j;
}
fairLikelihood/=factorial[j-i];
i=j;
}
// A small shrinkage prior prevents zero estimates on unseen patterns.
double unfairLikelihood=(frequency[key]+10*fairLikelihood)/(simulations+10);
bool fair=prior*fairLikelihood*falseUnfair>=(1-prior)*unfairLikelihood*falseFair;
std::cout<<static_cast<int>(fair)<<'\n';
}
}