AGECAL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

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.

2

Problem link

First solve for your planet

Lets assume that there is no leap year.

consider birth date and current date as y1/m1/d1 and y2/m2/d2 respectively,
total numbers of days between these two dates can be given as:
days = (total no of days in a year)*(y2 - y1) + (total no of days upto (m2 - 1) - total no of days upto (m1-1) ) + ( d2 - d1 + 1)
Notice that , here sum of second and third term is the total no of days between two dates of the same year.

for ex. lets take 30/january/2017 & 4/feb/2018
no of days = (1*365) + (31 - 0) + (4 - 30 + 1) = 365 + 31 - 25 = 371

for leap year :
what if we have december of 32 days instead of february of 29 for a leap year , then this will not affect the above method , so what we have to do is to just add number of leap years between two dates excluding the current year.

Now move to other planet
Iterate from 1 to n and store total no of days upto ith month (1 <= i <= n) , 1 based indexing
Apply the same approach to calculate no of days.

time complexity o(max(n , y2 - y1))

code link

3

Video Tutorial : https://youtu.be/0MEVqlRWPZg

4

Can anyone post the test case for subtask 2 used in submission?