Get Time
statistics_w  Match Editorial
SRM 163
Monday, September 8, 2003

Match summary

Division 1 saw a feeding frenzy as most contestants completed a paint-by-numbers Level One problem and a mildly tricky Level Two with ample time to spare. In the early running, tomek and SnapDragon led the pack by slim margins. The tempo grew less hectic as coders plodded through a Level Three specification torn from the pages of a bureaucratic standard for week numbering. jpo and Smiley=) found, at length, that a Java utility class could be tweaked to satisfy the shifted calendar, but bladerunner pieced together an iterative solution that propelled him ahead of the usual suspects and onto the winner's podium. Hot on bladerunner's heels was tomek, whose rating converged closer yet with that of SnapDragon, the latter's elegant Level Three effort having succumbed to an initialization bug.

The stalwart coders of Division 2 did well on a Level Three problem cloned from the upper division's Level Two. Few stumbled on the Level One, and many contended happily with their Level Two calendar problem, a less than daunting affair leavened by the spirit of Elvis. Although bokbok blazed with a fury through the first two problems, it was carambola5 who eked out a win over a clutch of other seasoned competitors.

The Problems

Inchworm discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 199 / 207 (96.14%)
Success Rate 165 / 199 (82.91%)
High Score bokbok for 248.34 points (2 mins 19 secs)
Average Score 218.72 (for 165 correct submissions)

Ready for some nifty arithmetic? Begin by noting that the inchworm's point of departure coincides with the first leaf on the branch. Subsequently, a meal ensues at every distance that is divisible by the inchworm's travel increment and by the leaves' growth interval. In other words, we are looking for common multiples of rest and leaf. In last week's match summary, schveiguy taught us that the lowest common multiple can be calculated by

    def lcm(rest, leaf):
        return rest / gcd(rest, leaf) * leaf

where the greatest common denominator gcd is given, for example, by the following recursive function.

    def gcd(rest, leaf):
        if (leaf == 0):
            return rest
        return gcd(leaf, rest%leaf)

Then we determine how many times the lowest common multiple fits into the branch length, adding 1 to account for the initial leaf, so that the total number of leaves eaten is calculated as follows.

    def eaten(branch, rest, leaf):
        return branch / lcm(rest, leaf) + 1

Those who are not so keen on factoring can forge ahead with a brute-force approach. Since the longest branch is only a million inches long, it won't take long to carry out a simulation. The following pseudocode shows how we can advance the inchworm's position by rest until she falls off the branch, all the while keeping track of how many distances are divisible by leaf.

    def eaten_sim(branch, rest, leaf):
        meals = 0
        pos = 0
        while (pos <= branch):
            if (pos%leaf == 0):
                meals = meals+1
            pos = pos+rest
        return meals
CalendarRecycle discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 134 / 207 (64.73%)
Success Rate 85 / 134 (63.43%)
High Score bokbok for 456.07 points (8 mins 59 secs)
Average Score 313.26 (for 85 correct submissions)

If two years start on the same day of the week, do they share a calendar? It depends. If one is a leap year and the other is not, then the weekdays fall out of sync at the end of February. But if both years start on the same day of the week, and neither is a leap year or both are leap years, then the weekdays march in lockstep from January 1 through December 31.

The funny thing is that if we want to find the nearest future year that shares a calendar with a given year, it isn't necessary to know what weekday the given year starts on. Let us say, for the sake of argument, that January 1 of this year is a Sunday. Now, what day of the week is January 1 of the next year? If this is not a leap year, then 365 days later, the weekday will have shifted by 365%7 = 1 day to Monday. But if it is a leap year, the weekday shifts by 366%7 = 2 days to Tuesday. We can apply the same reasoning year after year until we find one that begins on a Sunday and has the same leap-year status as the original year.

We reach the same result regardless of whether we begin by assuming that the given year starts on a Sunday or a Wednesday or anything else! Even the choice of January 1 is arbitrary. We might just as well proceed on the basis of, say, September 8.

We also use modulo arithmetic to identify leap years. In the following pseudocode, weekday is initially 0 to indicate that some fixed day in the initial year is a Monday.

    def elvis(year):
        weekday = 0
        leap = 0
        if ((year%400 == 0) or ((year%100 != 0) and (year%4 == 0))):
            leap = 1
        yy = year
        ww = weekday
        while (1):
            yy = yy+1
            ww = (ww+1)%7
            ll = 0
            if ((yy%400 == 0) or ((yy%100 != 0) and (yy%4 == 0))):
                ll = 1
            if ll:
                ww = (ww+1)%7
            if ((ll == leap) and (ww == weekday)):
        return yy

By sheer coincidence, this pseudocode will run on a Python interpreter.

Pool discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 56 / 207 (27.05%)
Success Rate 40 / 56 (71.43%)
High Score jnwood for 882.85 points (10 mins 38 secs)
Average Score 582.77 (for 40 correct submissions)
Used as: Division One - Level Two:
Value 500
Submission Rate 127 / 150 (84.67%)
Success Rate 110 / 127 (86.61%)
High Score bigg_nate for 471.95 points (7 mins 0 secs)
Average Score 337.50 (for 110 correct submissions)

An effective but brutal solution is to swap balls blindly, exploring the state space via memoized breadth-first search to discover the shortest path to a desired configuration.

A more genteel approach proceeds from the observation that productive swaps can be made independently of one another. Any swap that exchanges two improperly placed balls is just as helpful in restoring order as any other swap of two misplaced balls.

Suppose we want to form the first type of rack, where position 0 is occupied by a stripe. If the eight-ball is not at position 4, we begin by swapping it with whatever ball is usurping its rightful place. This pretender ball may again end up in an improper location, but the effort of swapping it later is equivalent to the effort it would have taken to swap it before moving the eight-ball.

Once the eight-ball is in place, we need merely swap misplaced stripes with misplaced solids. Since there are 14 stripes and solids altogether, at most 14/2 = 7 swaps are made at this stage. If it requires k swaps such that k >= 4, we see that we were working toward the wrong configuration, since the other kind of rack, where stripes are exactly exchanged for solids, would have required 7-k < 4 swaps.

So we decide to make k or 7-k swaps, whichever is less, and add 1 if the eight-ball was out of place. In sum, no more than 4 swaps are required to rack any triangle.

Rochambo discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 149 / 150 (99.33%)
Success Rate 148 / 149 (99.33%)
High Score tomek for 246.47 points (3 mins 24 secs)
Average Score 211.76 (for 148 correct submissions)

The most clearheaded way to interpret the opponent's history is that you win each time he makes the move you expect him to make. There's no need to figure out what move you should make in response. (For the first two moves, it's enough to know that you're expecting the opponent to play Scissors.)

If you insist on calculating the ideal move at every turn, find the character immediately following that of the opponent's move in the string "PSR", where R wraps around to P.

That's all, folks. No wonder the submission success rate was better than 99%.

CalendarISO discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 40 / 150 (26.67%)
Success Rate 20 / 40 (50.00%)
High Score bladerunner for 742.24 points (18 mins 6 secs)
Average Score 568.67 (for 20 correct submissions)

The concept of the calendar week forms a small part of ISO 8601, a standard for representing terrestrial dates and times. Sharp-eyed readers will have noted that ISO is not a strict abbreviation of "International Organization for Standardization", in the same way that UTC matches neither the English "Universal Coordinated Time" nor the French "Temps Universel Coordonne". Such is the ISO.

When calculating ISO week numbers by hand, the chief difficulty is that although most years have 52 calendar weeks, some have 53. It helps to observe that such a "long year" can only be one that begins or ends on a Thursday, since a leap year has 366=52*7+2 days and a non-leap year has 365=52*7+1. Consider that in a non-leap year, if January 1 is a Thursday, then exactly 52 weeks later comes another Thursday, hence the start of a 53rd week.

Under the Gregorian calendar, ISO week numbers can be calculated by closed-form functions such as the following.

    def week(y, m, d):
        a = (14-m)/12
        y = y+4800-a
        m = m+12*a-3
        j = d + (153*m+2)/5 + 365*y + y/4 - y/100 + y/400 - 32045
        d4 = ((((j+31741-(j % 7)) % 146097) % 36524) % 1461)
        L = d4/1460
        d1 = ((d4 - L) % 365) + L
        return d1/7 + 1

If, as in our problem statement, the calendar is shifted by three days, it's not obvious how such a magic formula can be adapted to meet the new circumstances, nor how a ready-made class such as java.util.GregorianCalendar can be employed. The motive for the three-day shift was precisely to throw a wrench into the works.

As it was, two coders managed to harness GregorianCalendar by a simple expedient. They set the minimal number of days in a week to four, as required by ISO, but set the first day of the week to Friday, three days ahead of the standard Monday. It is also possible to use GregorianCalendar less directly, relying on it to calculate a weekday-independent value, such as the day of the year, from which the ISO week number may be calculated with relative ease.

The elementary solution is to start from a known calendar week and proceed by first principles to deduce the ISO numbers of surrounding weeks. A slightly more sophisticated approach is to manually calculate an ISO week number in the sufficiently far past, so that one need only iterate forward to the target. Let us, however, consider iteration in both directions.

We learn from a test case that December 26, 1642 is the first day of ISO week 52 under the new regime. If the desired date is no earlier than this, we can creep forward a day at a time, updating the year, month, day, week number, and weekday as though they were wheels turning over in an odometer. Weekdays are indexed from 1 to 7 in the pseudocode below. We use a two-dimensional array to look up the days in a month according to leap-year status. Notice, furthermore, that the week number rolls over to 1 only on a Monday that falls between December 29 and January 4, inclusive.

    months = [[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31],
              [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]]

    def week_forward(year, month, day):
        y = 1642; m = 12; d = 26; wd = 1; wn = 52; leap = 0
        while (1):
            if ((y == year) and (m == month) and (d == day)):
                return wn
            d = d+1 if (d > months[leap][m-1]):
                d = 1
                m = m+1
                if (m > 12):
                    m = 1
                    y = y+1
                    leap = 0
                    if ((y%400 == 0) or ((y%100 != 0) and (y%4 == 0))):
                        leap = 1
            wd = wd+1
            if (wd > 7):
                wd = 1
                wn = wn+1
                if (((m == 12) and (d >= 29)) or ((m == 1) and (d <= 4))):
                    wn = 1

When creeping backward to a point earlier than the reference date, the year-month-day odometer rolls backward. The most delicate question is again that of updating the week number. It follows from the earlier inference about long years that an ISO week 53 can end only on January 3, or, in leap years, on January 2.

    def week_backward(year, month, day):
        y = 1642; m = 12; d = 26; wd = 1; wn = 52; leap = 0
        while (1):
            if ((y == year) and (m == month) and (d == day)):
                return wn
            d = d-1
            if (d < 1):
                m = m-1
                if (m < 1):
                    m = 12
                    y = y-1
                    leap = 0
                    if ((y%400 == 0) or ((y%100 != 0) and (y%4 == 0))):
                        leap = 1
                d = months[leap][m-1]
            wd = wd-1
            if (wd < 1):
                wd = 7
                wn = wn-1
                if (wn < 1):
                    wn = 52
                    if ((d == 3) or ((d == 2) and ((y%4 == 1) and ((y%400 == 1) or (y%100 != 1))))):
                        wn = 53

Even those who don't relish the intricacies of the ISO specification might appreciate the underlying simplicity of our superficially quirky calendar.

By Eeyore
TopCoder Member