So the reschedule actually happened this time. For a moment I suspected it might not as my client broke at room assignment time, had to log out and in again. I have been sick for the last 4 days, so I wasn’t looking forward to even more 4am nights if this one had been cancelled as well.
750 to advance… Turned out to be pretty easy looking questions with 750th before challenge phase being 500points, almost 200 people submitted something for all 3 problems, including myself. Been a long time since I submitted a 1000pt problem, although this one did seem pretty easy…
Challenge phase had a few successes, but not a huge number. 750th shifted slightly to ~495 points, and the number of people with all 3 still submitted was almost 140.
System testing took out another chunk, but I survived unscathed. 59th. Even assuming all 250 byes would have beaten me, that is a decent placement… Just over 100 submitted all 3 problems successfully. 750th place dropped down a tiny bit to 484 points.
Ratings took forever due to a glitch with the display of the results (seems the results were not affected much at a basic glance at least…) but I am now 1882 – which is a new personal best.
Q1) Given the ability to sort L characters and discard any characters after those sorted, return the lexicographically smallest result given an input string and any number of uses of this ability.
A1) So, I was a bit slow here, spent too long trying to decide whether the greedy approach was right. Turns out it was. So sorting the last L characters then moving one character forward, repeat until getting to the front, carries as many alphabetically early characters forwards as is possible, and since shorter strings compare earlier, truncating the rest is always a win.
Q2) Given a string S and the ability to permute it such that the index of a character doesn’t move by more than D, determine the lexicographically smallest result possible.
A2) Again greedy, but this time I was more confident. Greedy approach is to take the smallest character, at the earliest index available, to use as the new letter. Exception being if there is a letter that is still unused which is D characters earlier than the current index, in which case it can’t be put off any longer, and must be used now. I used a simple search the 2*D+1 locations for each output index, but I saw one solution which was O(N log D) rather than O(ND) by using a sorted set for the letters under consideration.
Q3) Given a set of lamps controlled by switches, which might also potentially toggle one or both of their neighbours, but always toggle their target lamp, determine the worst case minimum number of lamps that must be on. Lamps are in a line, not circular.
A3) So, the description of this question is a bit awkward, but the examples provided were surprisingly useful. They clearly showed than a sequence of YN(on off) or NY(off on) had a worst case of 1 light on. A sequence of NN or YY had a worst case of 0. So a greedy approach of trying to get as many YN, NY pairings as possible seemed sensible. Except the final example didn’t work.
I took longer to get it than most, but I did get there in the end. The missing case is ‘YYY’, This can be wired up such that at least one of the lights is always on. Seemingly a greedy approach may still work from here if written carefully, but at this point I decided enough was enough with the greedy solutions, so I wrote a basic DP where the best ‘worst case’ for the first n lamps was either that of n-1 lamps, or n-2 lamps + 1 if NY or YN or n-3 lamps + 1 if YYY.
The fact that there are no other scenarios which need considering is not exactly obvious. But I did prove to myself that YYYY worst case is 1 and YYYYY is also worst case of 1, so I was pretty confident.