Sunday, March 22, 2009

TCO R1, R2 and R3 screencasts

This is another interesting-only-for-TopCoder-players post.

I've uploaded the screencasts of TopCoder Open 2009 Elimination Rounds 1 (Streaming, AVI, MOV, AVI from narod.ru), 2 (Streaming, AVI, MOV, AVI from narod.ru) and 3 (Streaming, AVI, MOV, AVI from narod.ru). The R1 screencast is quite usual, with a resubmit because of a slightly too slow solution; the R2 screencast features my frustration as I'm unable to fix my solution for the medium (I knew that it was wrong because it has failed a stress test with a dumb solution) as the time is running out, and the R3 screencast features a new challenging strategy I've discovered: look at other challenged solutions (from other rooms) to see possible mistakes to look for in the solutions of your room. This sounds obvious, but I've never used that successfully before yesterday.

I've liked the hard problem from R3 a lot. I think it is an excellent example of how dynamic programming problems can be very non-standard (and the medium problem from the same round provides an example of how they can be very standard :)) and beautiful. The regular appearance of such problems makes me sure that we'll never run out of ideas in algorithm competitions. Although I'm biased for sure.

7 comments:

  1. Its all Russian .....I am not able to follow the instructions...

    ReplyDelete
  2. You should solve the CAPTCHA to the top of the green button, and then press the green button. If there's a checkbox around (this is browser-dependent), uncheck it - it is about installation of their toolbar.

    ReplyDelete
  3. Petr do you know a tutorial of Dynamic Programming diferent of TopCoder's tutorial? i want to learn it but i can't find a complete tutorial.

    ReplyDelete
  4. nw this is a kind of vid that can inspire beginners like m2 :)..ty Pter..Any other uploads will be highly appreciated

    ReplyDelete
  5. I am interset in your 250
    solution for last srm(437).
    I understand the idea but:
    why your function for hashing work?,how you choose 3137*n+k?why didnt let dictionary choose hash functioin?
    I imitate your code,and submit my own in practice room and of cource let dictionary choose hashcode,but It time out in somecases.
    can you give a breif explanation of your code?
    I should say that maybe one reason that i dont understand your sloution enough is that i dont know C# and hashing enough.
    anyway if you have time,pls explain your code:)

    thanks in advance

    hadi

    ReplyDelete
  6. The idea of a hash table is quite simple: first, we choose the number N of buckets. Second, when we add a new object X to the hashtable, we choose bucket (X.GetHashCode() % N) and put this object to that bucket. When there are several objects in the bucket, they are compared using the Equals() method to check if the newly added object is already present.

    Dictionary doesn't choose hash function by itself; by default, the hash function depends on the address of the object in the heap, and thus is most probably different for any two different objects. Thus, if you don't specify the hash function, all your objects tend to go into differnt buckets. In other words, after adding a new State(1,2) to the dictionary, ContainsKey(new State(1,2)) would return false, since these two State objects are different. This makes the solution evaluate the same case mutiple times and thus time out.

    So, if it's possible for your objects to be equal, you should override both Equals() and GetHashCode() with the latter returning the same value for equal objects. On the other hand, it's better for it to return different values for different objects, so that the number of objects in any one bucket is not too big. 3137*n+k makes is not very likely for different objects to have the same hash code.

    ReplyDelete
  7. want to see more of your screencasts~

    ReplyDelete