Kalmakka (kalmakka) wrote in topcoder,

TCO Round 2

A rather more complicated set of problems this time.

A very easy problem. Taking integer powers of a number to a certain moduli is something most TopCoders should be able to do in logarithmic time, but due to constraints the standard linear time algorithm was more than sufficient. There was one somewhat elusive corner case that a lot of people failed on. Apparently 0 is a 1-digit number, and not a minus-infinity-digit number. In addition to that bug, I had a silly </<= bug in my exponentiation function, going something like
if (x>100000) overflow=1;
return x%100000;

Clearly a number theory problem. The final letter in the input tells you whether you'll end up with an odd (2k+1) or even (2k+0) number before you do the final operation. Then, working from right to left you can determine the form for each previous step.
'E': If division by 2 gives you a number on the form ak+b, your number must have been on the form (2a)k+(2b).
'O': 3x+1=ak+b <=> 3x = b-1 (mod a) <=> x=(b-1)/3 (mod a) <=> x=(b-1)*(1/3) (mod a)
Coding up something to quickly find inverses is a bit tedious, but since 3 is such a small number we can do it very easily. Either 1 (well, not very likely :P), 1+a or 1+2a is a multiple of 3, and dividing that number by 3 gives the inverse of 3. Multiply up and make sure you get it on the form you want.

I'll just illustrate the procedure with an example.
Say you want to find the inverse of 21 mod 311
First use the Euclidean GCD algorithm
311 = 21*14+17
21 = 17 + 4
17 = 4*4 + 1
Running this in reverse
1 = 17 - 4*4 = 17 - 4*(21 - 17) = 5*17 - 4*21 = 5*(311-21*14) - 4*21 = 5*311 - 70*21 - 4*21 = 5*311 - 74*21
So, -74 * 21 = 1 (mod 311), and adding 21*311 gives you that the inverse of 21 is 237 mod 311.

Code it up and add to library!

Actually, this one was the most straight-forward of all the problems. Using a 20-bit bitmask to represent the different possible positions you can occupy and looking at how the four different moves you can make affect these positions you reduce it to a a nice shortest-path graph problem.

What I failed to realize (due to a state of tiredness and/or stupidity) was that a BFS generates not only the shortest path but also the lexicographically shortest path (where lexicographically is taken to mean the order in which you try out the different paths out from each node). So, essentially I had a complete solution, but I thought it would create the shortest path whose reverse string was lexicographically first (like one of my programs for the TCCC 04 did) so I didn't submit but instead tried to do some rather random hacking around but didn't end up with anything working. Lesson learned, I hope :)

A good score on the 250, or, more likely, a reasonable score on the 250 and a couple of easy challenges, was required to advance.
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.