This Round 1A was crazy. I was barely awake when it started, and I spent about two hours on the first problem — which is probably going to be the hardest problem one in historical first rounds!
Anyway, it turned out to be OK for me as the other problems were easy and I was good enough to enter the next round.
Problem 1 Pylons
Our Battlestarcraft Algorithmica ship is being chased through space by persistent robots called Pylons! We have just teleported to a new galaxy to try to shake them off of our tail, and we want to stay here for as long as possible so we can buy time to plan our next move… but we do not want to get caught!
This galaxy is a flat grid of R rows and C columns; the rows are numbered from 1 to R from top to bottom, and the columns are numbered from 1 to C from left to right. We can choose which cell to start in, and we must continue to jump between cells until we have visited each cell in the galaxy exactly once. That is, we can never revisit a cell, including our starting cell.
We do not want to make it too easy for the Pylons to guess where we will go next. Each time we jump from our current cell, we must choose a destination cell that does not share a row, column, or diagonal with that current cell. Let (i, j) denote the cell in the i-th row and j-th column; then a jump from a current cell (r, c) to a destination cell (r’, c’) is invalid if and only if any of these is true:
- r = r’
- c = c’
- r – c = r’ – c’
- r + c = r’ + c’
Can you help us find an order in which to visit each of the R × C cells, such that the move between any pair of consecutive cells in the sequence is valid? Or is it impossible for us to escape from the Pylons?
Basically, you are asked to provide a way to traverse a board of given shape under the constraint that each step consist of two grids that queens on them cannot attack each other.
It’s quick to come up with a few random constructions like repeating variants of knight moves. This kind of naïve construction actually works very well for large M and N’s. Actually, they are guaranteed to work if you consider two variants and both M and N are large enough:
- variant 1: keep using (1, 2) knight move, wrapping around the border using modulo. Once you reach the last line, you start in the first line but to one grid to the right.
- variant 2: keep using (1, 2) knight move, wrapping around the border using modulo. Once you reach the last line, you start in the first line but to one grid to the left.
However, the construction starts to fall apart for small M and N’s! I made the mistake of not having calculated how many special cases I needed, and it cost me lots of debugging time. It turned out the above-mentioned construction needs three special cases:
- M = N = 4
- M = 3, N = 5
- M = 5, N = 3
Even taking symmetry into consideration, figuring out how the construction would fail for M = 3, N = 5 was not easy. Hence, a hybrid approach of construction and brute force search could have fared better in another poor day.
Problem 2 Golf Gophers
Last year, a bunch of pesky gophers took up residence in our orchard. We tried to change our line of work by opening up a miniature golf course, but it looks like the gophers have followed us here! Once again, we need to figure out how many gophers there are, but we cannot observe them directly because they are secretive and nocturnal, whereas we like to sleep at night. We do know there are between 1 and M gophers, inclusive.
Our mini golf course is famous for having a small electronic windmill on each of its 18 holes. The i-th windmill has 2 ≤ Bi ≤ 18 blades, which are numbered from 0 to Bi-1, clockwise. Each night, before going to sleep, we turn off the windmills and set each one such that blade 0 is pointing downward, which is important so that the windmills can charge up properly for the next day. However, we have noticed that when we wake up, the windmills have been disturbed. Since our mini golf course is in a windless area, we think the mischievous gophers must be responsible!
We know that every night, all of the gophers emerge, one by one; each of them chooses one of the windmills independently and uniformly at random and rotates it counterclockwise by one blade. So, for example, for a windmill with 3 blades for which 0 is pointing downward, the first gopher to interact with it turns it so that 1 is pointing downward, and then the next gophers to interact with that windmill make the downward-pointing blade have number 2, then 0, then 1, and so on.
We have devised a plan. We designed our windmills so that we can easily change the number of blades (to modulate the difficulty of our course), and we will now take advantage of this! Each night, before going to sleep, we can choose the number of blades on each of the 18 windmills, within the given limits; we do not have to use the same number of blades on each windmill, or make the same choices every night. In the morning, we will observe the number on each windmill’s downward-pointing blade.
We have N nights in which to figure out G, the number of gophers. Can you help us?
Google, we need more gopher problems!
Anyway, it becomes apparent that using wheels of different numbers of blades on the same day is asking for trouble: you quickly lose the ability to infer any information. And fortunately we do not need to do that either: just by setting the numbers of blades to a list of preset numbers we can easily solve the problem via the Chinese remainder theorem.
The only caveat here is that the Chinese remainder theorem works when the divisors are pairwise co-prime. Some people might forgot that and try using only prime numbers, which will not be good enough to solve the problem. I picked ${7, 8, 11, 13, 15, 17}$ intuitively, and it was probably also the optimal array, in the sense of producing the largest product (2042040) under the given constraints.
Problem 3 Alien Rhyme
During some extraterrestrial exploration, you found evidence of alien poetry! Your team of linguists has determined that each word in the alien language has an accent on exactly one position (letter) in the word; the part of the word starting from the accented letter is called the accent-suffix. Two words are said to rhyme if both of their accent-suffixes are equal. For example, the words
PROLandTARPOLrhyme if the accented letter in both is theOor theL, but they do not rhyme if the accented letters are theRs, or theRinPROLand thePinTARPOL, or theOinPROLand theLinTARPOL.You have recovered a list of N words that may be part of an alien poem. Unfortunately, you do not know which is the accented letter for each word. You believe that you can discard zero or more of these words, assign accented letters to the remaining words, and then arrange those words into pairs such that each word rhymes only with the other word in its pair, and with none of the words in other pairs.
You want to know the largest number of words that can be arranged into pairs in this way.
Since we are dealing with suffixes, it is obvious that re-organizing the input data to a trie will help. Traditional tries deal with prefixes but it should be obvious to you that you want to do it backwards and store by suffixes instead.
Once we have that trie, a simple greedy algorithm can be run on the trie to produce the answer. Each node on the trie can produce at most one “rhyme-pair”, and any word in its subtree qualify for such a pair. Furthermore, it is always desirable (meaning it will not make things worse) to create “rhyme-pairs” at the deepest subtrees as possible. Hence, greedy algorithm works, and a simple recursive function defined on the trie will give the answer.