PROBLEM LINK:
Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi
PREREQUISITES:
NONE
PROBLEM:
An especial calendar and two dates are given. You are asked to calculate the number of days between the first day and the second day. It’s guaranteed that the first date is not after the second.
EXPLANATION:
There are many ways to approach this task. Some have better complexity than the others. Since the constraints are not too strict, we’re free to choose whichever that is fast enough.
First, let’s define two variables; ans as the answer to the problem and sm as the number of days of a non-leap year. Now, Let’s calculate which day of the year each given date is. We can do this for each date by iterating over the months that come before the month of that date and adding the number of days of the month to some variable like res. finally, we add the day of that date to res. A pseudo-code of a function that does the same is here:
int calc(Date date){
int res = 0;
for (each month m that comes before date.month)
res += m.days;
res += date.day;
return res;
}
This part takes O(N) complexity.
Now that we know what day of the year our dates are, let’s make sure that none of them are the last days of a leap year. It’s not necessary, but it makes the implementation a bit easier. It’s easy to do so with two if conditions. Something like this:
if (day1 == sm + 1) day1--, ans--;
if (day2 == sm + 1) day2--, ans++;
Note that we also alter ans because we’re changing the dates. Hence, the answer to the new dates will not be the same as the answer to the old ones.
Now, let’s move day1 forward so it becomes the same as day2. Meanwhile, we modify ans because it changes as we change the dates. It can be done like this:
if (day1 <= day2)
ans += day2-day1;
else{
if (year1 % 4 != 0)
ans += sm - (day1 - day2);
else
ans += sm+1 - (day1 - day2);
year1++;
}
day1 = day2;
Finally, let’s move year1 forward until it reaches year2. While doing so, we don’t change the month and the day of the dates. Subsequently, our dates will be the same once their years match. Here’s a code that does this:
while (year1 < year2){
ans += year1%4? sm: sm+1;
year1++;
}
This part takes O(yt). Hence, our solution for each test runs in O(yt + N). Refer to the editorialist’s code for the complete implementation.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here
Editorialist’s solution can be found here.