Working with Dates

Overview of How to Work with Dates (GregorianCalendar and Date Classes in Java)

For the average competitive programmer, this topic will be too narrow for you as there are typically only one or two problems in a competition that require knowledge of dates and how to manipulate them. However, this falls into the category of specialized topics. At least one person on your team should be familiar with how to work with dates.

The goal of this lesson is for you to learn how to:

1. Tell if one date comes after another date.

2. How to add days (or months, or years) to a given date to arrive at a new date.

Overview of the GregorianCalendar Class

In addition to the video below, here is a link to an excellent tutorial on the GregorianCalendar class in java. The older Date and Calendar classes are still sometimes used for simple conversions, etc. But most of our work will be done using the more modern GregorianCalendar class.

Using GregorianCalendar to Solve Competition Problems

We will teach you how to work with dates by working through the Reschedule It problem from the 2021 Lockheed Martin Packet. This is a 65 point problem (that is a lot of points!) which can be solved using only AP CSA knowledge combined with your soon-to-be developed expertise on GregorianCalander class. The problem is complicated. You need to read through the problem description (PDF file) thoroughly before doing the rest of this coding assignment.

Before we attempt to solve the RescheduleIt problem, we first have to understand some basic features of the GregorianCalendar class and how to make some basic date calculations.

How to Calculate the Number of Days Between Two GregorianCalendar Dates

It is surprisingly difficult to use the built-in methods in the newest (and older) Java library classes to calculate the number of days between two dates. For this reason, Java developers often import a third-party library called Joda-Time to solve these problems. However, we can calculate the number of days between two GregorianCalendar dates by writing a small amount of code. If d1 and d2 are both GregorianCalendar dates and we know that d1 is an earlier date than d2, we can calculate how many days apart the two dates are with this simple method:

public static int getDiff(GregorianCalendar d1, GregorianCalendar d2) {
int count = 0;
while ( d1.before(d2) ) {
d1.add(Calendar.DAY_OF_YEAR, 1);
++count;
}
return count;
}

We will need this method to help solve the RescheduleIt problem.

Converting From Date to GregorianCalendar

The getTime() method of Java Date class returns the number of milliseconds since January 1, 1970, 00:00:00 GTM which is represented by Date object.

Syntax: public long getTime()

We can take the number of miliseconds from the getTime method of the Date class and feed it to a GregorianCalendar object, to convert from Date to GregorianCalendar.

Date d1 = new Date();
...
GregorianCalendar c = new GregorianCalendar();
c.setTimeInMillis( d1.getTime() );

Step 1: Understanding the Input File Structure for RescheduleIt

Here is a copy of the sample input file for the RescheduleIt problem:

3 <-- tells us the total number of test cases in this file
2 3 <-- for the first test case, there will be two production units and 3 orders
2020-06-15 5 <-- production
2020-06-25 4 <-- production
2020-06-16 3 <-- order
2020-06-26 3 <-- order
2020-07-02 3 <-- order
3 2 <-- here is the beginning of the second test case
2020-06-15 2
2020-06-24 2
2020-06-25 2
2020-06-26 3
2020-07-25 3
2 2
2020-06-15 2
2020-06-24 3
2020-06-25 2

2020-06-26 2

Step 2: Defining Some Constants

The requirements in the problem description for RescheduleIt say that:

1. Aircraft must sit for at least one day after they are finished being built before they can be sold.

2. Aircraft are not allowed to sit for more than 28 days in inventory after being built.

3. The dates in the input file are of the format yyyy-MM-dd. It will be convenient to create a String with this format to help read in the dates.

We will define constants for the above needs in our code to get started:

public class RescheduleIt {

private static final int MIN_DIFF = 1;

private static final int MAX_DIFF = 28;

private static final SimpleDateFormat FORMAT = new SimpleDateFormat("yyyy-MM-dd");

...

}

Step 3: Reading the Input

As is common for most competition problems, you need to read in the data from the input file using a Scanner object. Reading in the input for this problem is especially complicated. This is because the Scanner calls are going to be mixed with Date and Calendar operations. Here is code to read the input for this problem:

public static void main(String[] args) throws Exception {

try (Scanner input = new Scanner(System.in)) {

int testCases = Integer.parseInt(input.nextLine()); // first in in input file tells us how many test cases there will be

for (int testcase = 0; testcase < testCases; testcase++) { // for each test case
// read in counts
int production = input.nextInt(); // first line in a test case tells us how many production units
int orders = input.nextInt(); // second line tells us how many orders
input.nextLine();

// read production schedule
List<GregorianCalendar> productionDates = new ArrayList<>(); // we will store the production dates in an ArrayList

for (int i = 0; i < production; i++) {
String[] info = input.nextLine().split(" ");
// convert string to a Calendar to allow date math
Date date = FORMAT.parse(info[0]);
GregorianCalendar cal = new GregorianCalendar();
cal.setTimeInMillis(date.getTime());
int count = Integer.parseInt(info[1]);

// add one copy of the date for each plane produced
// make copies so we don't accidentally modify more than one date
for (int j = 0; j < count; j++) {
productionDates.add((GregorianCalendar) cal.clone()); // not sure cloning is needed here
}
}

...

Practice with Dates

With all the hints and code supplied above, you are now in a position to try to solve the RescheduleIt problem that is linked below.

1. Do the Reschedule It problem from the 2021 Lockheed Martin packet. (This is a 65 pt problem).

2. Do the Daily Grind problem from the 2022 Lockheed Martin packet. (This is a challenging 110 pt problem which may be outside the scope of most high school students).