Online Judge Reference:

http://ybt.ssoier.cn:8088/problem_show.php?pid=1974

Core Concepts

The problem requires identifying dates that are both valid calendar dates and palindromes. A naive approach iterates through every 8-digit number between the start and end dates, resulting in a complexity of O(10^8). While this might pass, it is computationally expensive.

A string is a palindrome if it reads the same forwards and backwards. The simplest check in C++ involves comparing the string to its reversed version:

str == string(str.rbegin(), str.rend())

However, creating a reversed string object adds overhead. An alternative is to manually reverse the string or compare characters directly.

Solution 1: Brute Force with String Reversal

This method iterates through every number in the range [start, end]. It validates the date first, then checks if the string representation is a palindrome.

#include <bits/stdc++.h>
using namespace std;

int startRange, endRange, counter = 0;
int daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int yr) {
    return (yr % 4 == 0 && yr % 100 != 0) || (yr % 400 == 0);
}

bool isValidDate(int fullDate) {
    int yr = fullDate / 10000;
    int mon = (fullDate % 10000) / 100;
    int dy = fullDate % 100;

    if (mon == 0 || mon > 12 || dy == 0) return false;

    if (mon == 2) {
        if (isLeapYear(yr)) return dy <= 29;
        else return dy <= 28;
    }
    
    return dy <= daysInMonth[mon];
}

void inspectDate(int num) {
    if (!isValidDate(num)) return;

    string numStr = to_string(num);
    string revStr = numStr;
    reverse(revStr.begin(), revStr.end());

    if (numStr == revStr) {
        counter++;
    }
}

int main() {
    cin >> startRange >> endRange;
    for (int i = startRange; i <= endRange; i++) {
        inspectDate(i);
    }
    cout << counter << endl;
    return 0;
}

Solution 2: Direct Character Comparison

Instead of constructing a new reversed string, we can extract the digits into an array and compare symmetric positions (index 1 vs 8, 2 vs 7, etc.).

#include <bits/stdc++.h>
using namespace std;

int startRange, endRange, counter = 0;
int daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int year, month, day;

bool isLeapYear(int yr) {
    return (yr % 4 == 0 && yr % 100 != 0) || (yr % 400 == 0);
}

bool isValidDate() {
    if (month == 0 || month > 12 || day == 0) return false;

    if (month == 2) {
        if (isLeapYear(year)) return day <= 29;
        else return day <= 28;
    }
    
    return day <= daysInMonth[month];
}

void inspectDate(int num) {
    year = num / 10000;
    month = (num % 10000) / 100;
    day = num % 100;

    if (!isValidDate()) return;

    int digits[9];
    digits[1] = year / 1000;
    digits[2] = (year % 1000) / 100;
    digits[3] = (year % 100) / 10;
    digits[4] = year % 10;
    digits[5] = month / 10;
    digits[6] = month % 10;
    digits[7] = day / 10;
    digits[8] = day % 10;

    for (int i = 1; i <= 4; i++) {
        if (digits[i] != digits[9 - i]) return;
    }
    counter++;
}

int main() {
    cin >> startRange >> endRange;
    for (int i = startRange; i <= endRange; i++) {
        inspectDate(i);
    }
    cout << counter << endl;
    return 0;
}

Solution 3: Constructing Palindromes (Optimized)

The most efficietn method recognizes that an 8-digit palindrome is defined entirely by its first 4 digits (the year). We iterate through possible years (e.g., 2000 to 9999), construct the full 8-digit palindrome (e.g., 2001 -> 20011002), and then check if that constructed date is valid and falls within the input range.

#include <bits/stdc++.h>
using namespace std;

int startRange, endRange, counter = 0;
int daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int yr) {
    return (yr % 4 == 0 && yr % 100 != 0) || (yr % 400 == 0);
}

void checkValidity(int fullDate) {
    int yr = fullDate / 10000;
    int mon = (fullDate / 100) % 100;
    int dy = fullDate % 100;

    if (mon == 0 || mon > 12 || dy == 0) return;

    if (mon == 2) {
        if (isLeapYear(yr) && dy > 29) return;
        if (!isLeapYear(yr) && dy > 28) return;
    } else if (dy > daysInMonth[mon]) {
        return;
    }
    
    counter++;
}

int main() {
    cin >> startRange >> endRange;
    
    // Iterate through possible years
    for (int yr = startRange / 10000; yr <= 9999; yr++) {
        // Extract digits of the year
        int d1 = yr / 1000;
        int d2 = (yr / 100) % 10;
        int d3 = (yr / 10) % 10;
        int d4 = yr % 10;

        // Build the palindrome: YYYY + MMDD (where MM = d4d3, DD = d2d1)
        int constructedDate = yr * 10000 + d4 * 1000 + d3 * 100 + d2 * 10 + d1;

        if (constructedDate >= startRange && constructedDate <= endRange) {
            checkValidity(constructedDate);
        }
    }

    cout << counter << endl;
    return 0;
}

Key Takeaways

When facing time limits in competitive programming, consider if enumerating the result space (constructing the answer) is faster than filtering the input space. In this case, constructing the 10^4 possible palindromes is significantly faster than checking 10^8 potential dates.