PROBLEM LINK:
Author: Kanhaiya Mohan
Tester: Shubham Sharma
Editorialists: Akshit Dhoundiyal, Rohan Ray
DIFFICULTY:
EASY-MEDIUM
Tags:
Brute force, Pre-computation, Implementation.
PREREQUISITES:
Logical reasoning
Problem:
For 2 given years, finding the number of special dates between them inclusively.
Explanation:
Looking at the constraints it’s clear that we cannot check all the years corresponding to each query as it is bound to give us a TLE. So, we need to use precomputation here.
Observation 1
The problem says that the initial part of the year contains the date. We know that a date can have either 1 digit (1-9) or 2 digits (10-31). For a particular date, the month should be equal to the latter part of the year divided by the length of the string. We know that a month can have either 1 digit (1-9) or 2 digits (10-12).
For each day (obtained from the first part of the year) maximum 1 month corresponds to them as in each of them the length of the string is constant.
This tells us that we can have a maximum of 2 special dates corresponding to each year.
Observation 2
While performing the above operations we can get the dates which cannot exist, for example, we can get a date 30/2/3014. Here, the first part of the year (30) is equal to the day and the second part of the year (14) is equal to month (2)*length(7), but this date does not exist as the month of Feburary has a maximum of 29 days. To overcome this, we must ensure that the date that we are getting exists.
Implementation
We can utilize the above 2 observations to get special dates corresponding to each year in the constraint and then store them in an array.
Then we can take the prefix sum which will tell us how many special dates exist till the current year.
Our answer for each query would be the no. of special dates that exist till r^{th} year minus the no. of special days that exist till (l - 1)^{th} year.
Time complexity: O( max no. of years + q )
Solution
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
int years[1000001];
int prefix[1000001];
int max_permissible_days(int month , int year)
{
if(month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
return 31;
else if((month == 2) && ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)))
{
return 29;
}
else if(month == 2)
{
return 28;
}
else
return 30;
}
void special_days(){
for(int year = 1; year <= 1e6; year++)
{
string a = to_string(year);
if(a.length()>1)
{
int day = stoi(a.substr(0,1)); //day number
int n = stoi(a.substr(1)); // latter part of the year
int total = 1 + (log10(year) + 1) + 1; // length of entire date
if(n and n % total==0 and n / total < 10) // if a month from 1 to 9 has a possible solution
{
int month = n / total;
if(day <= max_permissible_days(month,year))
years[year]++;
}
total++;
if(n and n % total == 0 and n / total >= 10 and n / total <= 12) // if a month from 10 to 12 has a possible solution
{
int month = n / total;
if(day <= max_permissible_days(month,year))
years[year]++;
}
}
if(a.length() > 2)
{
int n = stoi(a.substr(2));
int day = stoi(a.substr(0,2));
int total = 2 + log10(year) + 1 + 1;
if(n and n % total == 0 and n / total < 10)
{
int month = n / total;
if(day <= max_permissible_days(month,year))
years[year]++;
}
total++;
if(n and n % total==0 and n / total >= 10 and n / total <= 12)
{
int month = n / total;
if(day <= max_permissible_days(month,year))
years[year]++;
}
}
prefix[year] = prefix[year-1] + years[year];
}
}
int l,r;
void solve()
{
cin >> l >> r;
cout << prefix[r] - prefix[l-1];
}
int32_t main()
{
sync;
special_days();
int t = 1;
cin >> t;
while(t--){
solve();
cout << '\n';
}
return 0;
}