Kalmakka (kalmakka) wrote in topcoder,

TCO 2006 Round 1

First round had some nice problems, imo. Apparently there were some technical difficulties that I didn't really notice. Something about point values. Anybody want to explain?

Basic maximum matching on a graph with 18 vertices. Quite a lot times-out because of forgetting to use DP and just did a recursion. 18 vertices with lots of edges was a nasty input for that. Use a bitmask to represent the communicating vertices and try out any pair of available vertices with an edge in between and see how you can keep on matching.

I really didn't see how to do this. It turns out, it just require a bit of serious thinking before you get started.
Say you want to find a k-digit number whose first digit is a that has the desired property. Such a number is then a*10k+b for some b<10k, and the number you get by rotating it is 10*b+a. Setting this ratio equal to p/q and juggling around a bit, you get that b(10d-p)=pa10k-aq which gives you the unique choice for b, provided it exists.
The programming part was easy, as long as you added enough checks, you just had to do the math first. Very good problem.

Graph theory, number theory... hey, how 'bout some group theory for the last problem!

The order of an element can be determined by taking the least common multiple of all its cycle lengths. Take (1 2 3 4 5) -> (2 3 1 5 4). It contains a 3-cycle (1 2 3) and a 2-cycle (4 5), so it will have order 6. Notice that since you can always make 1-cycles, there is no point in having cycle lengths with two or more different prime factors, since you could get the same order by having several smaller cycles and some 1-cycles. So c(n,p), the number of orders obtainable using n elements and no prime divisors above p, is equal to c(n,q)+c(n-p,q)+c(n-p2,q)+c(n-p3,q)+... until n-pk < 0, where q is the greatest prime < p.

Congrats to all positive-score earners!
  • Post a new comment


    default userpic

    Your IP address will be recorded