Easy problems this week, in fact in what is a rare turn of events I made submissions for every question.
Before systests I was 147th, but I already knew that was going to change, as I had proven one of my solutions wrong already. However the systests did not agree?!? ‘Final’ placing 101st. Even if they were to rerun with a more comprehensive systest I would still be about 140th apparently.
So finally, a round easy enough for me to do at 2am.
Q1) Given a set of guesses where you know exactly one character in the guess is wrong in each case, determine how many possible answers remain. (Up to 50 characters, each in the range ‘0’ to ‘9’. Up to 50 guesses.)
A1) This is a simple question which tried to trick you by making the return value a 64bit integer type. The worst case is actually where you have the same guess made 50 times, and there is 50 characters.
For a single guess you can enumerate all possibilities by substituting each character with the other 9 possibilities. Then the answer is just the size of the intersection of the output for enumerating for each guess. Use a dictionary to count how many times you see each generated possibility, and count how many times the count equals the size of the input – done. Even if you have 50 different guesses at 50 digits each, there is only ~20k entries in your dictionary. Or just perform Set intersections, each set has a maximum of 450 entries, so you could even do it using lists and contains and still not run slow…(not that I recommend getting into that practice!)
I however, made a fatal mistake. I didn’t realise that a 50 digit number can’t be converted to a long until the break before challenge phase… I was converting my generated values into numbers and using them as my dictionary keys rather than creating strings. Its not like the code was any easier my way, I just had less string concat calls, which I have developed a natural aversion too it seems. Despite this fatal mistake I somehow passed system tests!?!
Q2) Given a grid where you can move from grid intersection to intersection at a variable cost, but you can only move right or down, determine the minimum cost to get from top left to bottom right if you change the costs such that every path has the same total cost, but the only change you can make is to increase the cost of an edge. (Grid is 40×40)
A2) Well, this one looks easy at first. Although I can’t fully explain my justification any more… The idea is that the minimum cost path has at least one edge which is not part of any maximum cost path – unless the minimum and maximum are the same. Presuming this possibly unjustified leap of logic, it then simply becomes obvious that if you can work out the maximum path cost at the beginning, that is the same as the maximum path cost at the end. Maximum cost is easy, for each vertex determine the maximum of cost from above or left, where the maximum cost for those locations is already calculated and cached.
Q3) Given a sequence of letters where no letter appears more than 2 times, and there are at most 50 letters, determine the minimum number of swaps to turn it into a palindrome.
A3) So I submitted an answer to this, but I certainly didn’t have any form of proof to go with it. First, determine if the answer can be a palindrome, if there is more than 1 letter which appears only once, it cannot be, otherwise it can (due to the restriction of maximum appearance of a given letter being 2). If the length is odd and the single appearance letter is not in the middle, swap it there from wherever it is and add 1 to running total count.
Then walk from front to back, at each point if its the first time you’ve seen that character, store its position. If it isn’t switch the character with the position inferred from the first location you saw the character (if it isn’t already in the right spot) and add 1 to running total count. If a switch occurs, you need to remember to check the same spot again, since the newly placed character may or may not be in the right spot.
Very unusual for a greedy approach like this to be the solution for the 1000pt question, but it passes. Then again, given my incorrect solution to the first problem which ALSO passed systests, maybe I am giving system tests too much credit 😛