Lexicographic Password Reconstruction
National Olympiad — National round (2021 season)
Submission name: crack.cpp
Problem summary
Replace each star in a fixed-length string using the characters from its associated option string. Sort all resulting words lexicographically, retaining duplicates, and output the word at a given 1-based rank.
Input
The template, then K and rank I, then one length-K option string for each star.
Output
The word at rank I, counting duplicate words separately.
Constraints
Template length 1…500; 1…N stars; 1 ≤ K ≤ 26; 1 ≤ I ≤ 10^9, not exceeding the multiset size. Characters are printable ASCII, with star reserved as the placeholder.
Worked example
Input and output for the worked example discussed below.
Input
po*olje*i 3 7 sol znu
Output
posoljeni
Solution analysis
- All words have the same fixed characters, so compare choices at the first star where they differ. At a star, sort the distinct candidate characters and count how many times each occurs in its option string.
- Maintain prefixMultiplicity: how many different earlier choice combinations spell the prefix already selected. For a candidate character with frequency f and r remaining stars, its lexicographic block contains prefixMultiplicity×f×K^r words. Subtract whole blocks from I until the desired block is reached, append its character, and multiply prefixMultiplicity by f.
- Multiplicities matter. For options aa and ab, the sorted multiset is aa,aa,ab,ab. Ordinary base-K indexing of option positions gives aa,ab,aa,ab, which is not sorted. Prefix multiplicity accounts for these repeated paths correctly.
- In the displayed example, first-star blocks l,o,s each have three words. Rank 7 skips six words and selects s, then chooses n at the second star, yielding posoljeni. All counts may be capped at the original rank because larger blocks never need an exact value.
Why it works
At every position the selected prefix describes a consecutive interval of the sorted multiset. Equal next characters form blocks of exactly prefixMultiplicity×frequency×K^remaining completions. Subtracting earlier blocks preserves the rank within the remaining interval. Induction selects the correct full word, including all repeated-choice multiplicities.
Watch out. Do not deduplicate repeated option characters. Do not use plain mixed-radix indexing when repetitions exist. Cap products before overflow, and keep ranks 1-based.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
long long cappedProduct(long long a,long long b,long long cap){
if(a==0||b==0){
return 0;
}
if(a>cap/b){
return cap;
}
return min(cap,a*b);
}
int main(){
string password;
int choices;
long long rank;
cin>>password>>choices>>rank;
long long cap=rank;
int stars=count(password.begin(),password.end(),'*');
vector<string>options(stars);
for(string&option:options){
cin>>option;
}
vector<long long>power(stars+1,1);
for(int i=1;i<=stars;i++){
power[i]=cappedProduct(power[i-1],choices,cap);
}
long long prefixMultiplicity=1;
int index=0;
for(char&character:password){
if(character!='*'){
continue;
}
array<int,127>frequency{};
for(unsigned char candidate:options[index]){
frequency[candidate]++;
}
for(int candidate=33;candidate<=126;candidate++){
if(frequency[candidate]==0){
continue;
}
long long multiplicity=cappedProduct(prefixMultiplicity,frequency[candidate],cap);
long long block=cappedProduct(multiplicity,power[stars-index-1],cap);
if(rank>block){
rank-=block;
}
else{
// Equal prefixes represent repeated words, not a single choice.
character=char(candidate);
prefixMultiplicity=multiplicity;
break;
}
}
index++;
}
cout<<password<<'\n';
}