Contest analysis is already posted – 27170 positive scores and 1710 perfect scores. Not mentioned was the cut-off, 22154 people are currently eligible for competing in Round 1.
The success rates for large were quite high for both of the first two problems, but quite a bit lower for the third and fourth. I expected a low pass rate for the large input on the fourth as I’ll discuss later, but the third is less obvious.
Q1) Consider multiples of N, what is the end of the sequence which contains every digit in base 10 at least once at some point during the sequence.
A1) As mentioned in the contest analysis, it can be proved that other than 0 the maximum sequence length has an upper bound of 90, and the specific case of 125 gets close at 72. Therefore the largest number to consider will be less than 90 million, so there is no risk of overflow. So this problem boils down to can you correctly break a number down into its base 10 digits. This is a pretty common operation in coding competitions for some reason or another, but one which is missing from TMD.Algo – I think I’ll fix that.
Q2) Given a sequence of – and + characters, determine the minimum number of operations to turn them all into +, if the only operation you can perform is to reverse the first k characters and also invert them all so – becomes + and vice versa.
A2) The key to this problem is that a change between – and + in the sequence will always remain a change during any operation unless the operation only includes one of those characters and the first element of the sequence is equal to the kth element of the sequence. Therefore the number of changes, plus potentially one more because you end up with all -, is a trivial lower bound. And simply repeatedly fixing the first change in the sequence is the solution because the prefix is always all the same character. My preferred solution is to append a + on the end then just count where character not equal its next.
Q3) Generate a set of sequences of 1’s and 0’s that start and end with 1 and have a specific length, and when interpreted in each base 2 through 10, are always non-prime.
A3) This was an unusual problem in that the entire test set was in the problem statement, there was nothing unexpected. And despite that the large input only had a 70% pass rate. This suggests a lot of people tried to be tricky like the contest analysis proposed, rather than just brute forcing with an arbitrary precision type. Or didn’t realize that a 32 digit base 10 number is too large for 64 bit integers – I hope there wasn’t too many in that group, given to pass the small they would have already realized a 16 digit base 10 number is too large for 32 bit.
Anyway I just brute forced this problem using BigInteger and checking for trivial composites with factors less than 9. Interestingly I found that just checking for composites using just 3 and 7 or 5 and 7 was effective, but not using just 3 and 5 or 2 and 7. I’m not clear on why this is the case though, the contest analysis talks about a 3,2,7 being very popular so I guess 3,7 works for a significant fraction of those?? Really I’ve not done enough investigation to be sure.
Like the first problem, this problem involved digits, specifically for the brute force, interpreting them as values in different bases. This is a pretty simple piece of code to write, but also one that shows up in programming competitions a bit, so it feels a bit of a deficit in TMD.Algo which I should fix.
Q4) Assuming that a K^C element sequence of L and G is generated by repeatedly applying a rule that starting with a length K (but otherwise unknown) base pattern of L and G a derived pattern is created by replacing each L with the original base pattern and G with an equal length sequence of G’s, determine S locations to check which will prove whether the are any G’s in the full sequence.
A4) So this problem had a very trivial small input. Regardless of the base pattern the first K characters are either base pattern, or all G. If any of them are G then obviously the pattern contains a G. If not then the base pattern is all L’s, which obviously means the entire sequence is L. So when S = K you just return the numbers 1 through K.
The problem is that this approach tells you nothing about the large input. Unless you actually understand the problem fully, you could come up with ways to do better than S = K, which will pass the small input, but then you’ll fail the large. I think a second small input set where S could be anything, but K^C was limited to a much smaller number could have caught the first order failure to fully understand the problem without clearly giving away the full depth.
Anyway, I like this problem because of the subtle connection back to problem 1 and 3. This is actually a problem about digits. Given a zero-based trial location the zero-based positions in the original base sequence which could affect the trial locations value are the same as the digits of the trial location when written in base K. More specifically, if any of those locations are G then the trial will return G. So the ideal search is a set of C digit base K numbers where there is no unnecessarily repeated digits. If any of the base pattern contains G, one of the search locations will be a G, otherwise the entire sequence is L’s since the base pattern is all L’s. Once I have some nice digit sequence logic in TMD.Algo, I think the implementation for this solution will only be a couple of lines.