In 2016 I was quite happy with my performance in GCJ, even though I didn't make it past Round 1. So despite being quite busy, I registered for the 2017 edition as well. The Qualification Round happened yesterday. It lasted for 27 hours, starting at 1AM in my time zone. I looked at the puzzles after breakfast, and as usual found them intriguing. I initially skipped the first one (Oversized Pancake Flipper) because I knew it must be easy but I didn't find an obvious approach right away. The general approach I took was to first read the problem (out loud if a family member would be willing to listen :-), then think about it while scribbling in a notebook, then when I thought I had an efficient (should be "efficient enough") solution code it up in Lisp more or less top-down. For your amusement, I'm sharing the entirety of my this year's notes, including errors and culs-de-sac.
This seemed easy and linear, and I didn't have to do much scribbling. We're looking for the largest Tidy Number that's less than or equal to the input number. We represent the input as a vector of digits. Then we start from the left and look at consecutive pairs of numbers. As long as di≤di+1 we're happy. If di>di+1,
we need to "fix it up". Fixing it up means usually means changing di to di-1 and replacing everything to the right with nines. We cannot run into di=0, because there are no leading zeroes and we have already checked that the prefix of the number up to and including digit i is Tidy, so the digits cannot become lower. The local fixup may result in the overall number not being Tidy anymore, i.e.
we may have made di<di-1. So we need to recurse (or reiterate, but hey we're thinking in Lisp, right?) on the result. We also may have introduced a leading zero that should be removed. So we remove those. The resulting code is in B.lisp. The code is recursive but not purely functional, because it munches the array using (setf (aref ...) ...). That's ugly and might have made debugging harder, but then the code should be easy enough to not need debugging. And probably this (half-) destructive approach saves a few cycles...
This was definitely the one I had the most (and longest) fun with. It took me several hours (mostly unfocused/doing other things) to get to the breakthrough, which would of course have killed me in a "real" time-limited round.
B. Tidy Numbers
C. Bathroom Stalls
At first I drew up some simple/small examples. Starting from initial settings with (N=) 7, 6, 5, or 4 spaces, I added all N respective occupants K in order, to get an intuitive picture of how the game plays out. But I didn't find the general pattern.
Pretty quickly, I had a complete understanding of the case where N=2i-1: The first person (K=1=20) has 2i-1-1 space to the left and to the right, the next two (21) persons each have 2i-2-1 space to the left and right, and so on. But how to generalize this to Ns that do not have this form?
At any "round of the game" (K), there is a set of "extents" of free space. In each round, the largest of the current extents is "split": If the size of this largest extent is odd and larger than one, that is, of the form 2x+1, then it will be split into two extents of size x. That was the "easy" case that covers the problem completely when N=2i-1.
But for other kinds of N, I still had no good idea of the pattern how the overall set of extents develops. In a desperate attempt, I tried to draw this up as a tree for N=6. That looked somewhat promising, but I still couldn't figure out the general pattern. At least it shows the special case of the size-2 extent, which doesn't really get split into two extents but degenerates into a single size-1 extent. Hm, this seems complicated.
In an even more desperate attempt, I decided that I needed to look at a bigger example and started drawing up the tree for N=230. Nothing very particular about that number, except that I wanted to start with an even number because that seems to be the more complicated case.
Now that led to the breakthrough. In this non-trivial example, I saw that each level of the tree only contained (a maximum of) two different values with a difference of one.
So a complete and useful description of a given level of the tree is the distribution between these two different values. This is what I wrote up in the right-hand column: On level 1 (after the first split) we have extents of 1x114 and 1x115, on level 2, 1x56 and 3x57, on level 3, 1x27 and 7x28, on level 4, 9x13 and 7x14, and so on. Generalizing to level 0, we can say that we start with 1x230 (1xN) and 0x231.
But how does one get from level j to level j+1? Well, each odd extent splits into two equal extents, and each even one splits into one that's half the original number and one that's one lower. That leads to the two cases below the large (partially written-out) tree. (I started writing the cases with m and n and then replaced that with a and b, respectively, but didn't do so all the way because I had enough to write the code.) The code is in C.lisp, and I'm quite happy with it. Initially I had switched the even and odd cases, which led to wrong results on the tiny example under the problem description. First I panicked, but by simply running a few examples under (trace minmax-1) I could locate the error. I knew the code was O(log(N)) efficient, so I fed it the small, still-small, and large cases with confidence, and each was processed in less than 10 milliseconds.
At any "round of the game" (K), there is a set of "extents" of free space. In each round, the largest of the current extents is "split": If the size of this largest extent is odd and larger than one, that is, of the form 2x+1, then it will be split into two extents of size x. That was the "easy" case that covers the problem completely when N=2i-1.
Now that led to the breakthrough. In this non-trivial example, I saw that each level of the tree only contained (a maximum of) two different values with a difference of one.
So a complete and useful description of a given level of the tree is the distribution between these two different values. This is what I wrote up in the right-hand column: On level 1 (after the first split) we have extents of 1x114 and 1x115, on level 2, 1x56 and 3x57, on level 3, 1x27 and 7x28, on level 4, 9x13 and 7x14, and so on. Generalizing to level 0, we can say that we start with 1x230 (1xN) and 0x231.
But how does one get from level j to level j+1? Well, each odd extent splits into two equal extents, and each even one splits into one that's half the original number and one that's one lower. That leads to the two cases below the large (partially written-out) tree. (I started writing the cases with m and n and then replaced that with a and b, respectively, but didn't do so all the way because I had enough to write the code.) The code is in C.lisp, and I'm quite happy with it. Initially I had switched the even and odd cases, which led to wrong results on the tiny example under the problem description. First I panicked, but by simply running a few examples under (trace minmax-1) I could locate the error. I knew the code was O(log(N)) efficient, so I fed it the small, still-small, and large cases with confidence, and each was processed in less than 10 milliseconds.
A. Oversized Pancake Flipper
At this point I was fairly certain to have passed the mark with just two problems done, assuming that at least one of my "large" data set solutions were correct. But it nagged me that I hadn't turned in A, which was supposedly the easiest puzzle. I thought about it again and came up with the following reasoning: The basic operator (multi-pancake flip) is commutative—it doesn't matter whether I flip 4–6 and then 3–5, or the other way round. That means we should be able to strictly process the pancakes in some order, e.g. from left to right. The operator is also an inversion... applying it twice returns the original state and, because of the commutative property, never makes sense.
So we can just go to the row of pancakes left-to-right. If the current pancake is –, we turn it and the others to its right. If the current pancake is + we leave it. Then we shift one place to the right and repeat. When we're at the end of the row (which is K places before the end because of the flipper restriction), we're done. The last pancakes must then all be + or we lose.
The code is in A.lisp. Again, this is written recursively but destructively: The flipping is done by modifying elements in the vector (string). Probably the code would be more elegant if rewritten using a list instead of a vector, and constructing a fresh list when flipping.
When reading the initial state of pancakes, I skipped the reverse (or nreverse) step because it really doesn't matter whether we operate on a mirror image.
D. Fashion Show
Wow, that problem sure seemed from a different league. Fewer than 1'000 contestants even got the small solution right, whereas all other problems had at least 13'000 correct solutions. My mental analysis and scribbling didn't get me very far. You cannot have more than one non-+ in the same row or column, not more than one non-x in the same diagonal. If you want to have an o (twice the value of a + or x), then all the other non-empty models in the same row/column need to be +, all on the same diagonal need to be x.
There's also a parallel to the N-queens problem, in that in both cases you cannot have more than one "thing" (where thing means "queen" or "non-+/x") per row/column/diagonal. But where N-queens only has one "thing", the queen, in this case the things are different (non-+/non-x), and what's more we need to maximize some value.
So I couldn't figure out a useful approach, and the fact that some initial models have been placed makes the reasoning even harder. So I gave up before even trying very hard.
Conclusion
The next morning I checked my results for the large data sets and found them all correct. I ranked in the 4'400s, but then I started late. My 65 points would have been sufficient to enter the top 1000 if I had finished everything in 2h15. That would have been somewhat unlikely, even if I had started immediately and had been fully focused. The first sub-round of round 1 will start at 3AM local time, so I'll probably skip it and try 1B a week later, and then probably 1C. Let's see!
I didn't have too much trouble with the SLIME/SBCL combination; for more than 25 years I have mostly been using Allegro and its Emacs interface when programming, and this is still much easier for me, especially when debugging. But for the contest I really wanted to use a Free/Open Source Lisp.
No comments:
Post a Comment