Three easier questions this round, although I have to say I found the ‘easy’ question the hardest… Advancing cut-off was either of the first 2 problems and the smalls from both the others and a few minutes to spare. Solving the 3rd problem and smalls of the other was worth 1 more point and ~400 places as a result.
Q1) In a game of finding all the locations of a 1xW rectangle in an RxC space, where before each guess the opponent is free to move the 1xW rectangle anywhere that is consistent with the previous answers, determine the minimum number of guesses to guarantee victory assuming the opponent plays to maximize your guesses.
A1) So I spent a while rabbit holing entirely the wrong direction. I seem to have ‘divide and conquer’ on the brain, this is the second time I’ve gotten stuck on a problem this year because I was convinced that dividing the problem in half was optimal.
So in practice this question boils down to forcing the opponent to have no options as fast as possible. This starts by reducing the places the rectangle can be. The fastest way to do this is obviously (in hind sight) to guess W cells away from an edge of where it could be. The opponent will answer no unless it has to, a yes easily reaches a smaller number of guesses. No answer eliminates W spots.
When you are down to one last row with 2*W-1 or less possible spots the strategy changes. W spots you know everything, so just guess every spot left to victory. Between 2*W-1 and W+1 inclusive you know some subset of the middle. Guess immediately next to that, the opponent will answer no (or possibly yes if there is more than one unknown spot left, it makes no difference to them if they are assume we play ideal). Once they answer no, we know everything and can guess all the remaining spots.
In the end this entire problem can be boiled down to C/W*R + W – (C%W==0 ? 1 : 0). Each row other than the last takes C/W guesses to eliminate entirely. The last takes C/W – 1 guesses to get down to the last section, then W+1 guesses to pin everything down. With one exception if C%W == 0, the last section is W spots, so only W guesses are required to pin everything down.
In the end I wonder why the limited the large input to just 20 x 20, I guess it leaves open a DP solution rather than just the greedy.
Q2) Given a list of letters (size N) to choose from at random, a length of output (size S) and a ‘target’ sequence (size T), determine the maximum number of times the target sequence could appear, then determine the difference between that and the expectation value for number of times it appears in the output if generated at random.
A2) So this is a deceptively easy problem. I usually don’t like probability problems, but in this case the details clearly point out that multiple overlapping instances all count. Hence the probabilities are independent and easily calculated. List of letters can be turned into base probabilities by summing 1/N for each letter. The target is then converted into a probability by the product of those base probabilities for each letter in the target. The full expectation value is then that ‘target’ probability times S-T+1, since each possible starting point is fully independent.
The maximum number of times target sequence can appear is determined by the maximal non-complete overlap of the target sequence with itself. Which can be determined with a simple nested for loop. The maximum is then (S – T)/(T-overlap) + 1. One length T, then as many T-overlap sections that will fit.
Q3) Given a list of values that you can have up to c of each of, determine the minimum number of extra values in order to be able to create every possible total between 1 and V.
A3) I found this question easy, but only because I’ve had previous experience with this kind of question before. Its a greedy problem.
Start off with having used none of the provided values. With this you can make 0. Take the smallest unused provided value, if it is what you can currently make + 1, or smaller, add c * that value to what you can currently make. Otherwise add c * (what you can currently make + 1) and increment the extra values you had to have counter. Repeat until you can make V or higher.
One corner case to be careful of for large input. While the target V can never be more than 1 billion, and the provided values are always small, the extra values you have to add can be very closer to 1 billion, so adding c * extra value can overflow a 32 bit integer very easily.