Recover a Password Followed by Its Truncated Code
National Olympiad — Municipal round (2025 season)
Submission name: password.cpp
Problem summary
A password is followed by its sorted code, retaining at most i copies of alphabet letter i. Recover the original password in its original order.
Input
The combined length and lowercase string.
Output
The original password.
Constraints
Combined length≤500000; the input is valid.
Worked example
Input and output for the worked example discussed below.
Input
19 abbracadabraabbcdrr
Output
abbracadabra
Solution analysis
- For letter index i, with a=1, let c be its original frequency. Its combined frequency is t=c+min(c,i). This strictly increasing function is invertible.
- If t≤2i then c=t/2. Otherwise c=t−i. Sum all recovered original frequencies to obtain the password length; the password is exactly that prefix of the input.
- For ten d letters, i=4 and t=10>8, so the password has 10−4=6 d letters. The longer sample similarly recovers a 12-character prefix, abbracadabra.
Why it works
The two formulas exactly invert the two possible branches of c+min(c,i). Their sum recovers the original total length. The encoding places the original password first, so extracting that prefix restores it without reordering.
Watch out. Do not sort the recovered password. Alphabet indices start at 1, and each cap applies separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
int length;
string text;
cin>>length>>text;
array<int,26>counts{};
for(char letter:text){
counts[letter-'a']++;
}
int originalLength=0;
for(int letter=0;letter<26;letter++){
int cap=letter+1;
// Invert total = original + min(original, cap).
originalLength+=counts[letter]<=2*cap?counts[letter]/2:counts[letter]-cap;
}
cout<<text.substr(0,originalLength)<<'\n';
}