Recovering Two Scrambled Dates
National Olympiad — National round (2013 season)
Submission name: dates.cpp
Problem summary
Two eight-digit strings encode dates in arbitrary permutations of DD, MM and YYYY. Recover the unique same-year pair whose inclusive interval has the supplied length.
Input
Two eight-digit strings, then the inclusive number of days.
Output
Earlier and later dates on separate lines in DD-MM-YYYY format.
Constraints
Years 1000…2012; interval length 1…350; exactly one valid solution exists.
Worked example
Input and output for the worked example discussed below.
Input
03292011 20111205 45
Output
29-03-2011 12-05-2011
Solution analysis
- Enumerate all six field orders for each string, consuming widths 2,2,4 according to each permutation. Reject impossible years, months, or day numbers using Gregorian leap-year rules.
- Compare every surviving pair with matching years. Convert each date to its day-of-year ordinal and require |ordinal1−ordinal2|+1 to equal the supplied inclusive interval length.
- The sample starts on 29 March 2011. Interpreting the second string as 12 May gives 45 inclusive days; interpreting it as 5 December instead gives 252. The length resolves the field-order ambiguity.
Why it works
The six permutations exhaust every allowed interpretation. Calendar checks retain exactly valid dates, and pair checks enforce both remaining conditions. The promised unique solution is therefore found and sorted chronologically for output.
Watch out. Read strings to preserve zeros. Century years are leap only when divisible by 400. Include both endpoint dates.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Date{
int day;
int month;
int year;
int ordinal;
};
vector<Date>candidates(const string&text){
vector<Date>result;
array<int,3>order{0,1,2};
do{
int fields[3]={};
int offset=0;
for(int field:order){
int length=field==2?4:2;
fields[field]=stoi(text.substr(offset,length));
offset+=length;
}
int day=fields[0];
int month=fields[1];
int year=fields[2];
if(year<1000||year>2012||month<1||month>12){
continue;
}
int days[12]={31,28,31,30,31,30,31,31,30,31,30,31};
// Gregorian century exceptions matter for this historical year interval.
if(year%400==0||(year%4==0&&year%100!=0)){
days[1]=29;
}
if(day<1||day>days[month-1]){
continue;
}
int ordinal=day;
for(int m=1;m<month;m++){
ordinal+=days[m-1];
}
result.push_back({day,month,year,ordinal});
}
while(next_permutation(order.begin(),order.end()));
return result;
}
void print(Date date){
cout<<setfill('0')<<setw(2)<<date.day<<'-'<<setw(2)<<date.month<<'-'<<setw(4)<<date.year
<<'\n';
}
int main(){
string first;
string second;
int length;
cin>>first>>second>>length;
for(Date a:candidates(first)){
for(Date b:candidates(second)){
if(a.year==b.year&&abs(a.ordinal-b.ordinal)+1==length){
if(a.ordinal>b.ordinal){
swap(a,b);
}
print(a);
print(b);
return 0;
}
}
}
}