Only 1362 out of 2001 qualifiers turned up for this round. (Well above the 1% existence failure that Otinn uses for his odds calculations. So maybe I have >1% chance of getting a t-shirt after all…)
374th before system tests, I was just hoping to get a non-zero score this round. The first question had potential for problematic test cases and lots of successful challenges (the number of red ranked coders on 0 points or lower was pretty scary…), and the rest were too difficult for me to even consider at this late hour. (Although I swear the second question was familiar…)
Waiting on systests … and the announcement comes through that because the challenge phase was broken for the last 3 minutes, the round *might* be cancelled. Which would mean another 2am night back-to-back.
Systests finished, so if this round actually counts I’ll be in 285th. Which in any other year would be a t-shirt placement, but given the fact that round 2 has 3 parts and splitting of t-shirts over the best 350 ranks of all it won’t be good enough. (Unless subsequent rounds are even harder and hence not enough people get past the minimum 0 points requirement…). Only 461 people got a positive score this round (2/5 Aussies, including myself got a positive score).
Q1) Given a list of sets of states for light switches and corresponding states for lamps, but with no knowledge of which light switch actually corresponds to which lamp – determine the minimum number of extra state sets required to correctly identify each lamp. Each switch and its light are in sync, it is a simple wiring. Each individual state on its own will be valid, but there may be no solution which satisfies all states, in which case the answer is -1.
This problem looks like it needs brute force, but with bounds of up to 50 lights and up to 50 state sets, that certainly seems implausible. So I created a 2 dimensional array of whether switch i could be lamp j. If a single state set says a switch i is on and a lamp j is off, obviously switch i cannot connect to lamp j and vice-versa. If two state sets have the same switch state then those switches cannot be in the set of lamps with different lamp states and similarly for switches in different states. The question then becomes, is this enough? And since I passed system tests, the answer might be yes… (I fully expected it to be no though…)
Finally count up how many switches each light could be. Then take the ceiling of the base 2 log of the highest of those counts, since each count corresponds to a set of switches which we know nothing about, and that set of switches can be solved in base 2 log tests, and each of the groups of switches can independently be solved at the same time.
Post Sleep Update 2: A better approach is to consider the pattern of each switch and each lamp. Presuming that there is a solution any given pattern must appear the same number of times amongst switches and lamps. The pattern with the highest count is the same as the switch with the largest count in my version, and from there the code is identical. This approach is quite obviously correct, so is it possible to define a test case which breaks my approach?
The answer is yes. Using an a quick written app to compare the output of the 2 approaches for random inputs I found the following test case (and many others…)
switches = YNYNNNYNNYYNY, YNNNYYNYNYNNY, NYYNYYYYNNYNN
lamps = NYYYNNYYNNYNN, NNYYYNNYYYNNN, YNNNYNYYYNYNY
My code incorrectly believes such test cases to be possible, but the pattern NYN only appears in the lamps not the switches.
This is twice in a row that I have managed to get past the system tests with incorrect code!
Q2) Given a list of items to visit in order on a 1-dimensional line, and the ability to add up to K instant teleports, what is the minimum travel distance to visit the items in the order specified?
A2) No real clue yet… but it isn’t the semi greedy approach of choosing the best location for the first 2 teleport locations, then the best location of each subsequent one… (I wrote that during the comp and it failed one of the samples.)
Looking at one solution the approach appears to be to calculate the minimum distance to travel in the n left most items with up to K teleports, but I’m going to need some sleep before I make sense of it.
Post Sleep Update 1: So the approach is indeed the minimum distance to travel for the n left most items with up to k teleports. More specifically it is the minimum distance travelled in the area to the left of the n left most items where the kth teleport is at the same location as the nth item. In order to solve the question the component required is to be able to answer the question ‘what is the distance spent travelling in the segment a,b if a and b are both teleports. Then you can treat the initial state as having teleports at -infinity and +infinity and add teleports left to right, adding the cost of the segment previous teleport location to new teleport location.
The cost of a segment bounded by teleports only needs to consider the items which are inside that segment. Obviously the path for every item outside that teleport either does not attempt to enter the segment, or skips the segment to get to another item outside the segment, or jumps to whichever end is closest to its target inside the segment. So for each item inside the segment, we need to consider the item before and after it in the sequence. For each of these if the other element is outside the sequence we simply add the distance to closest end of the segment. If the other element is inside the sequence, we ignore the before and only consider the after to avoid double counting. The cost here is either the sum of the costs to the closest endpoints or the direct distance in between the 2 elements, whichever is smaller.
During the competition I had thought that something along these lines would be needed, but only at about 7 minutes left on the clock and I thought the cost for a segment would be much more difficult to calculate.
Q3) Given n rooms connected by a set of 1 direction tunnels which do not form any loops, and the knowledge that some rooms are clear and some rooms might be obstructed and if so could not be entered, determine how many scenarios there are where the number of paths from room 0 to room 1 is even. Up to 50 rooms, and at least all but 32 of those will be listed as clear. (Also: at most 500 tunnels)
A3) Only 2 correct solutions for this during the competition, obviously brute force is too slow, but at first glance the question seems plausible… I’ll take a closer look after some sleep.