
Match Editorial 
2003 TopCoder Open
Online Round 3Wednesday, October 29, 2003
Summary
The bestofthebest battled for the 50 round 4 slots. Unlike previous rounds, slowyetcautious coding
practices prevailed, with many submissions falling to challenges and systests. Most quickly submitted the
easy problem, but had troubles with the medium. Valiant coders who submitted the medium had even greater
woes ahead. The hard was a devilish problem, whose solution requires a deep understanding of permutations.
When the dust cleared, quick coding Yarin came out on top, with Tomek just behind. snewman, the `newbie'
whose submissions are always colored in `C# blue', extended his perfect submission streak to 6. There is
clearly a permanent top 10 spot with his name on it. Problem descriptions follow, including a detailed
explanation of the solution to the hard.
The Problems
QuadraticRoots
Used as: Division One  Level One:
Value

250

Submission Rate

99 / 100 (99.00%)

Success Rate

83 / 99 (83.84%)

High Score

tjq for 244.76 points (4 mins 10 secs)

Average Score

224.00 (for 83 correct submissions)

In this problem, brute force all possible combinations of the 3 parameters:
for (int aIndex = 0; aIndex < a.length; aIndex++) {
for (int bIndex = 0; bIndex < b.length; bIndex++) {
for (int cIndex = 0; cIndex < c.length; cIndex++) {
//code here
}
}
}
When evaluating the quadratic formula, be careful that you aren't taking the square root of a negative number,
and that the value b^24ac is a perfect square. Once that is checked, it still must be verified that the numerator
is divisble by 2a. The following code checks whether a value x is a perfect square using java:
int rtx = (int)Math.sqrt(x);
if (rtx*rtx == x) { \\proceed
}
WaterPressure
Used as: Division One  Level Two:
Value

500

Submission Rate

71 / 100 (71.00%)

Success Rate

51 / 71 (71.83%)

High Score

NGBronson for 411.98 points (13 mins 45 secs)

Average Score

287.61 (for 51 correct submissions)

The solution described here is something of an optimized breadth first search. Maintain a list of all `digit squares' adjacent to water. This can be thought of as the frontier of the water. Check each element of the frontier, to see if the square can be flooded, and if so, remove it from the frontier, and add its relevant adjacent neighbors. If no frontier element can be flooded, store the minimum water total that will be required to resume flooding. Using this min, we can quickly advance the seconds and water total to a point where flooding can begin again. This process is repeated till the frontier is empty. At that point, if any digits squares remain unflooded return 1. Otherwise, return the time when the last digit was flooded.
ShuffleMethod
Used as: Division One  Level Three:
Value

1000

Submission Rate

33 / 100 (33.00%)

Success Rate

12 / 33 (36.36%)

High Score

reid for 714.07 points (19 mins 43 secs)

Average Score

535.72 (for 12 correct submissions)

It is always interesting when an easy concept like shuffling cards, can lead to a very difficult problem. A complete description of the solution follows.
Introducing the cycle notation
To explain the method I used to solve this, I will first introduce some important concepts about permutations. Let's say you were looking at the shuffling procedure 3,1,2,5,6,4. This takes the deck
1,2,3,4,5,6 to 3,1,2,5,6,4.
For the purpose of this discussion, we will say card 1 is transformed into card 3, card 2 is transformed into card 1, and so forth. Explicitly written out: (a>b meaning a transformed into b)
1>3, 2>1, 3>2, 4>5, 5>6, 6>4
Given any shuffling procedure, hereafter called a permutation, we can look at its cycles. To find a cycle, mark a card, and follow its transformations as we shuffle over and over, noting when a repeat occurs. For example,
1>3 then 3>2 then 2>1 so we have the cycle 1>3>2>1.
We use the notation (1 3 2) to write such a cycle. Verify that the other cycle is (4 5 6). Notice that there are many ways to write a cycle. For example,
(1 3 2) = (2 1 3) = (3 2 1).
It all depends on which card you follow. From this point on, we will always use the version where the minimum number occurs first in the cycle. Using cycles, we have a useful way to describe permutations. The permutation above would be written as (1 3 2)(4 5 6). Basically, just take each cycle and write them next to each other. This can always be done, such that none of the cycles share any elements. Such a description is called `a product of disjoint cycles', since the cycles have no elements in common (also called a disjoint cycle decomposition). What about 1element cycles? If you have a permutation like 2,1,3, you can write it as (1 2)(3) or (1 2). In other words, it's customary to leave out 1element cycles.
Squaring cycles, and seeing what happens
Let's say you had the permutation 2,4,5,3,1. Verify that this can be written as (1 2 4 3 5). This permutation is just a single cycle. What happens if we apply this permutation twice (analogous to shuffling twice)? Observe:
1,2,3,4,5 > Shuffle 1 > 2,4,5,3,1 > Shuffle 2 > 4,3,1,5,2
The permutation 4,3,1,5,2 is called the square of 2,4,5,3,1, since it is formed by performing it twice. Verify that the permutation 4,3,1,5,2 can be written as (1 4 5 2 3). What we have just seen, is that a cycle of length 5, when squared, becomes a cycle of length 5. Let's look at an arbitrary odd length cycle:
(a1 a2 a3 a4 ... ak) where k is odd.
Verify that the square will be a cycle of length k. (Hint: start with a1, skip 2 steps to a3, ...) What about an even length cycle? For example, what is the square of
2,3,5,6,4,1 = (1 2 3 5 4 6).
Verify that the square is
3,5,4,1,6,2 = (1 3 4)(2 5 6).
Furthmore notice for any even length cycle
(a1 a2 ... an) where n is odd
will have square
(a1 a3 a5 ... a[n1])(a2 a4 ... an).
The last key thing to realize, is that squaring doesn't mix cycles. Let's say you had our first example,
3,1,2,5,6,4 = (1 3 2)(4 5 6).
Squaring we get
2,3,1,6,4,5 = (1 2 3)(4 6 5).
Numbers from the first cycle didn't get jumbled with numbers from the second cycle. It is not hard to prove, that disjoint cycles will remain disjoint when you square the permutation. Furthermore, each cycle can be squared individually. (Notice that (1 3 2) squared is (1 2 3) and (4 5 6) squared is (4 6 5). Algebra enthusiasts will realize that this occurs since disjoint cycles commute.)
Finding oneShuffle
Let's say twoShuffle is
2,3,1,5,6,4 = (1 2 3)(4 5 6).
We want to figure out what oneShuffle could be. We ask where (1 2 3) could have came from. In other words, what cycle could have been squared to produce the 3element cycle (1 2 3). From the previous section, we know the only possibilities are: a) a cycle of length 3, or b) a cycle of length 6. Verify that the only cycle of length 3 it could have came from is (1 3 2). (Hint: if 1 > 2 in twoShuffle then 1 must go to 2 in two steps in oneShuffle) Furthermore, verify that the possible 6element cycles are
(1 4 2 5 3 6) and (4 1 5 2 6 3) = (1 5 2 6 3 4) (same hint).
One major concept at play here, is that the square of a 6cycle (6element cycle) is two 3cycles, and the square of a 3cycle is a 3cycle. In this problem, we will have to choose the lexicographically earliest permutation, so here oneShuffle would be
(1 3 2)(4 6 5) = 3,1,2,6,4,5.
When dealing with even cycles in twoShuffle, there are fewer options. For example, if twoShuffle is 2,1,4,3 = (1 2)(3 4), there are no single cycles whose square is a 2cycle. The only option is a squared 4cycle that becomes two 2cycles. So the only options for oneShuffle are
(1 3 2 4) and (3 1 4 2) = (1 4 2 3),
from which we would choose the lexicographically earlier (1 3 2 4). What if twoShuffle is
2,3,4,1,6,5 = (1 2 3 4)(5 6).
The 2cycle (5 6) could only have came from a squared 4cycle in oneShuffle. The problem is, when you square a 4cycle in oneShuffle, it will produce two 2cycles, and we only have 1. This is an example where you would return an empty int[], since there is no permutation whose square is twoShuffle. We now have enough information to form our algorithm.
Algorithm
Decompose twoShuffle into disjoint cycles, and place them in a list called cycleList ordered by minimum element. In other words, (1 3 7) would come before (2 4 5) since 1 is less than 2. Starting with the cycle containing 1, figure out which cycle it could have came from (which cycle squared will produce it). When many choices are available, always take the one that produces the lexicographically earliest permutation. Two examples of choices are shown below:
 cycleList = (1 7),(2 6),(3 4),(5 8). When processing (1 7) pair it with cycle (2 6) so it came from the 4cycle
(1 2 7 6) in oneShuffle. All other pairings produce lexicographically later permutations.
 cycleList = (1 4 5),(2 3 6). When processing (1 4 5) you can either choose to have it come from the 3cycle (1 5 4), or the 6cycles (1 2 4 3 5 6), (2 1 3 4 6 5) = (1 3 4 6 5 2) by pairing with (2 3 6). Choose the first 6cycle, since it is lexicographically earliest.
If you pair cycles together, remove them both from cycleList. If you have an even cycle, and there is no pair in cycleList, return an empty int[]. Since we are processing in order of minimum elements, 1cycles are never paired with other 1cycles. Proceed till all elements of cycleList are exhausted. The formed permutation is the answer.
By
brett1479
TopCoder Member