Tuesday, April 21, 2009

Competition, quick recap

We just have a few minutes break, so I'll try to recap quickly.
Our team went for a high-risk high-reward strategy. We looked at 4 problems, and tried to solve them all.
The problem with high risk strategies is that risk is a real issue (here's the actuary in me!). Sometimes risk is fine, sometimes it doesn't go so well.
That's what happened to us today. We submitted responses to 3 problems, and had a 4th one in the works. Unfortunately, we didn't get the right answer for any of them.
Two of them we ran out of time (i.e. our program took too long to compute the answer), and the third one had the wrong answers. If you have access to the problem set, here's how it went:
A -- many teams were getting this. I didn't think it was terribly easy, but I switched gears and tried to solve it. I got stuck and put it aside. Later, John tried his hand and couldn't get it.
B -- I spent most of my time on this one. I was matching the sample output, and there didn't seem to be any special cases for this one. However, I couldn't get a correct response.
? -- (The one with surrounding the trees by a fence.) Curt worked on this one. He had most of it worked out, but we ran out of typing-up time.
K -- John spent most of his time on this one. He had a good algorithm, but not many teams got this one correct at all. There was likely some really nasty judge data for this one.
We are trying to remain upbeat. It has been a good time, and we gave it our best efforts. If anyone wants to discuss these problems online (or in person), we would love to do so. Many of the other problems we had some idea on (I would have loved to try my hand at the house of cards game problem), but they didn't look as easy and we obviously struggled at the easier ones.
Thank you to everyone back home who stayed up to watch the broadcast. We really appreciate your support and are looking forward to seeing you soon!

8 comments:

  1. WE just want to say GREAT JOB!! Even though you didn't get the results you wanted, you certainly gave it your all. May God be glorified!!!! Don't forget that just qualifying for the finals is a fantastic achievement!!!

    ReplyDelete
  2. Hey Ben and Raider teammates. Congrats on making it to the "big dance" (using NCAA language). I will be interested in hearing the details of the problems when you return even if they didn't go as planned. Glad you "went for it". It is better than safely answering one question and wondering "what if".

    ReplyDelete
  3. Even though you guys didn't get any correct solutions we're all still proud of you! I've been telling a lot of people I know that NWC sent a team to the ICPC World Finals!
    For those interested, here's a link to the problem set: http://icpcdmt.csc.kth.se/2009Problems.pdf.

    A looks interesting, but after thinking about it some, I think it might be a little harder than it first appears.
    B must be easier than it appears to me, I don't think I would have tried it, but it was the second most popular question behind A.
    C doesn't sound fun.
    D sounds doable to me and seems somewhat similar the the overlapping rectangles practice question. Except here you're minimizing space without overlapping instead of just determining if there is overlapping.
    E also sounded doable until I read there could be up to 50,000 roads/intersections - that'll throw a wrench into the "no two tolls" requirement real fast.
    F is the fences/trees one, and sounds doable, too bad you guys ran out of time.
    G does sound interesting Ben, but by no means easy.
    H doesn't sound fun to me either, but a fair number of teams got it right.
    I sounds doable after reading through it just once. I think once you could figure out how to do just one window inside another you could just recursive apply this for however deep the hierarchy of windows goes?
    J must be harder than it appears to me, since only one team attempted it and they got it wrong.
    K must have had some tricky test data. It doesn't appear that it should've been too hard, but only 3 correct entries out of 51 attempts indicates otherwise.

    ReplyDelete
  4. To some of the brightest and the best, or smart risk-takers who are going to make the world a better place - Congrats, guys! It's good to read about your strategy...you weren't just twiddling your thumbs, feeling overwhelmed. Well, maybe a bit of the latter, eh? Did you even think about the St. Petersburg guys next to you? You were too busy, eh?
    You got honorable mention - Whooo! Hey, the Capital-Democrat already got a pix from IBM of you three and Prof Wallinga walking down the stairs at opening ceremonies. Nice.
    -janine

    ReplyDelete
  5. Kurt,
    Great job getting to this point! We're so proud of you. We're keeping a close eye on your car, and your grandma hasn't been joy riding in it!
    See you soon,
    Shelley Wiersma and family

    ReplyDelete
  6. Hi Ben, already arrived? :D
    Problem A is a binary search (the minimum gap value, we try to maximize this value) + validating that there is at least one order can be formed with the value (brute force with permutation)

    Problem B I got WA
    Problem E got WA too, but i think it's just about handling "No Solution" case

    ReplyDelete
  7. Other teams are saying that is the solution as well.
    So what do we run the binary search off of? From my experiences with binary search one needs:
    1. A sorted array
    2. A value to find
    I guess I am still a bit confused as to what either 1 or 2 are.
    (Also, is this some "classical problem" from somewhere? The algorithm to solve obviously is not looking me in the face, but many teams got this rather quickly.)
    For B, I'm not sure if there is some special case or simply a bug in my program. Either were fairly likely, though I was pulling my hair out in unsuccessful attempts to find either.

    ReplyDelete
  8. You try to guess the answer ben, if it is possible to make plane order with minimum gap x, then you try to make x larger, you don't need to check for all value < x, this is the binary search. Because the number of plane, just do permutation to get all possible order, and check it.

    ReplyDelete