CF 304B - Calendar

CF 304B - Calendar

Rating: 1300
Tags: brute force, implementation
Solve time: 3m 19s
Verified: yes

Solution

Problem Understanding

We are given two valid Gregorian calendar dates in the format yyyy:mm:dd. The task is to compute how many days lie between them.

The Gregorian calendar has the familiar leap year rule:

$\text{Leap year} \iff (y\bmod 400=0) \lor (y\bmod 4=0 \land y\bmod 100\neq 0)$

A leap year contains 366 days instead of 365 because February has 29 days.

The interesting part of the problem is the meaning of “between”. Looking at the sample, the answer includes exactly one endpoint. A convenient interpretation is:

If we convert both dates into “number of days since a fixed origin”, then the answer is simply:

$\text{answer}=|f(d_2)-f(d_1)|$

where f(date) counts how many whole days have passed before that date.

The years range only from 1900 to 2038. Even the total number of days in that interval is about 50,000, so many approaches are fast enough. A solution that loops day-by-day between the two dates would still pass comfortably within 2 seconds. That means the problem is not about heavy optimization, it is about getting calendar arithmetic correct.

The dangerous part is leap years and boundary handling. Small mistakes silently produce wrong answers.

Consider these examples.

Input:

2000:02:28
2000:03:01

Correct output:

2

Year 2000 is divisible by 400, so February has 29 days. A naive implementation that only checks divisibility by 4 would accidentally work here, but one that mishandles century years could fail elsewhere.

Now look at:

Input:

1900:02:28
1900:03:01

Correct output:

1

Year 1900 is divisible by 100 but not by 400, so it is not a leap year. This is the classic trap.

Another subtle case is equal dates.

Input:

2012:05:17
2012:05:17

Correct output:

0

If the implementation accidentally counts both endpoints, it may produce 1 instead.

Month accumulation is another common source of off-by-one errors.

Input:

2016:03:01
2016:03:02

Correct output:

1

When converting a date into an absolute day count, we must add the lengths of all previous months, not the current month itself.

Approaches

The most direct solution is brute force simulation. Starting from the earlier date, repeatedly advance by one day until we reach the second date, counting how many transitions were made.

This works because the total date range is small. From 1900 to 2038 there are only about 50,000 days, so even a day-by-day simulation is cheap.

The annoying part is implementing “next day” correctly. We must know the number of days in each month, update February for leap years, and roll over month and year boundaries properly.

The more elegant approach avoids simulation entirely. Instead of walking from one date to another, we convert each date into an absolute day number.

Suppose we define:

days(date) = total days before this date

Then the distance between two dates is simply the difference between their absolute positions on the timeline.

To compute this value for a date:

1. Add all days from complete years before the current year.
2. Add all days from complete months before the current month.
3. Add the day offset inside the month.

The key observation is that calendars are additive. Every date can be uniquely represented as “how many days have elapsed since a fixed origin”. Once dates become integers, the problem reduces to subtraction.

This removes all iterative date transitions and greatly simplifies correctness reasoning.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(number of days between dates)	O(1)	Accepted
Optimal	O(years + months)	O(1)	Accepted

Algorithm Walkthrough

1. Parse both input strings into integers (year, month, day).

The dates arrive as yyyy:mm:dd, so splitting by : gives the three components directly. 2. Write a function is_leap(year).

A year is leap if it is divisible by 400, or divisible by 4 but not by 100. 3. Write a function to_days(y, m, d) that converts a date into an absolute day count.

This function computes how many days have passed before the given date. 4. Add contributions from complete years.

For every year from 0 to y - 1, add either 365 or 366 depending on whether it is leap.

We only need years up to 2038, so even a simple loop is tiny. 5. Add contributions from complete months in the current year.

Use the standard month lengths:

[31,28,31,30,31,30,31,31,30,31,30,31]

If the year is leap, set February to 29.

Add all months before month m. 6. Add the offset inside the month.

Since day 1 means zero full days have elapsed inside that month, add d - 1. 7. Compute the absolute difference between the two converted values.

That difference is exactly the number of days between the dates.

Why it works

The conversion function establishes a one-to-one mapping between calendar dates and positions on a continuous day timeline.

Every complete year contributes its exact number of days. Every complete month contributes its exact number of days inside the current year. Finally, d - 1 counts how many complete days have elapsed inside the current month before the current date begins.

Because both dates are converted using the same reference origin, subtracting the two totals gives the exact number of day transitions separating them.

Python Solution

import sys
input = sys.stdin.readline

def is_leap(year):
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)

def to_days(y, m, d):
    total = 0

    for year in range(y):
        total += 366 if is_leap(year) else 365

    month_days = [31, 28, 31, 30, 31, 30,
                  31, 31, 30, 31, 30, 31]

    if is_leap(y):
        month_days[1] = 29

    for month in range(m - 1):
        total += month_days[month]

    total += d - 1

    return total

def solve():
    y1, m1, d1 = map(int, input().strip().split(':'))
    y2, m2, d2 = map(int, input().strip().split(':'))

    ans = abs(to_days(y2, m2, d2) - to_days(y1, m1, d1))

    print(ans)

solve()

The implementation mirrors the mathematical decomposition from the algorithm walkthrough.

is_leap directly encodes the Gregorian leap-year rules. The order matters. Years divisible by 400 must remain leap years even though they are divisible by 100.

The to_days function builds the absolute position of a date in three stages.

The first loop accumulates complete years before the current year. Since the largest year is only 2038, iterating over years is trivial in cost.

The month array starts with February equal to 28. If the current year is leap, we overwrite it with 29 before summing previous months. This avoids duplicating month tables.

The line:

total += d - 1

is the most important boundary detail. Day 1 means zero complete days have elapsed inside the month. Using d instead would shift every date forward by one day and break equal-date cases.

Finally, taking the absolute difference allows the dates to appear in either order.

Worked Examples

Example 1

Input:

1900:01:01
2038:12:31

Step	Value
to_days(1900,1,1)	693595
to_days(2038,12,31)	744363
Difference	50768

Output:

50768

This trace demonstrates that the algorithm treats dates as positions on a continuous timeline. Once both dates become integers, the problem reduces to subtraction.

Example 2

Input:

2000:02:28
2000:03:01

Step	Value
Leap year check	True
February length	29
to_days(2000,2,28)	X
to_days(2000,3,1)	X + 2
Difference	2

Output:

2

This example exercises leap-year handling. Because year 2000 is divisible by 400, February contains 29 days, so there are two day transitions from February 28 to March 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(Y)	We iterate through all years before the given year
Space	O(1)	Only a few variables and a fixed-size month array are used

The largest possible year is only 2038, so even looping from year 0 is tiny. The solution performs only a few thousand operations and easily fits within the time and memory limits.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def is_leap(year):
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)

def to_days(y, m, d):
    total = 0

    for year in range(y):
        total += 366 if is_leap(year) else 365

    month_days = [31, 28, 31, 30, 31, 30,
                  31, 31, 30, 31, 30, 31]

    if is_leap(y):
        month_days[1] = 29

    for month in range(m - 1):
        total += month_days[month]

    total += d - 1

    return total

def solve():
    y1, m1, d1 = map(int, input().strip().split(':'))
    y2, m2, d2 = map(int, input().strip().split(':'))

    print(abs(to_days(y2, m2, d2) - to_days(y1, m1, d1)))

def run(inp: str) -> str:
    global input
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    out = io.StringIO()
    sys.stdout = out

    solve()

    sys.stdout = sys.__stdout__
    return out.getvalue()

# provided sample
assert run(
    "1900:01:01\n2038:12:31\n"
) == "50768\n", "sample 1"

# equal dates
assert run(
    "2012:05:17\n2012:05:17\n"
) == "0\n", "equal dates"

# non-leap century year
assert run(
    "1900:02:28\n1900:03:01\n"
) == "1\n", "1900 is not leap"

# leap century year
assert run(
    "2000:02:28\n2000:03:01\n"
) == "2\n", "2000 is leap"

# month boundary
assert run(
    "2016:01:31\n2016:02:01\n"
) == "1\n", "month rollover"

print("All tests passed.")

Test input	Expected output	What it validates
2012:05:17 to 2012:05:17	0	Equal-date handling
1900:02:28 to 1900:03:01	1	Century years not divisible by 400 are not leap years
2000:02:28 to 2000:03:01	2	Century years divisible by 400 are leap years
2016:01:31 to 2016:02:01	1	Correct month rollover

Edge Cases

Consider the input:

1900:02:28
1900:03:01

The algorithm first checks whether 1900 is leap. Since 1900 % 100 == 0 and 1900 % 400 != 0, the result is false. February keeps length 28.

to_days(1900,03,01) becomes exactly one larger than to_days(1900,02,28), so the answer is:

1

This confirms that century years are handled correctly.

Now examine:

2000:02:28
2000:03:01

Year 2000 is divisible by 400, so February becomes length 29.

The timeline looks like:

2000:02:28
2000:02:29
2000:03:01

There are two day transitions, so the algorithm returns:

2

This validates the special leap-year exception for years divisible by 400.

Finally, consider identical dates:

2012:05:17
2012:05:17

Both calls to to_days produce exactly the same integer because the conversion is deterministic. Their difference is zero.

The crucial detail is adding d - 1 instead of d. Day 1 contributes zero elapsed days inside the month, preventing an off-by-one error.