Algorithm track round 1B

What an intense round. Also, what an interesting turn out for the problem writer guessing contest I just organized. This time I tried to make a log of what I go into when attempting to solve this contest. Let us see if it was interesting. This post also includes the partial results for the problem writer guessing contest.

9:00 AM I register for the match. I always try to register very quickly, but the registration form does rob me of some time. I am able to confirm I was one of the four coders to register first.
First 4 coders to register

9:23-9:27 Something is wrong with the arena – the window freezes. I hope nothing strange happens during the round.

9:51 I finished working up the first rules idea for the problem setter guessing contest. These rules were very improvised and I ended up changing a lot about them…

Besides announcing the contest every once in a while and getting complaints about poorly-thought rules and getting convinced to change them, nothing happens until 12:01.

12:01 Rooms are set. I got the second best rating in the room. Ooh the pressure.

Apparently the anthropomorphic manifestation of the whole tournament, the Topcoder Open 2012 is in my room! I am not sure whether to be scared or not. I wonder if tco12 is going to be a rival during this match.

My room has a couple of interesting names. jhtan is also from my university and we got assigned the same room. This will have repercussions later.

12:06: As the start of the round approaches, I begin to wonder if I should open the hard problem first. Or the medium problem first. Or use the normal strategy. I was not able to decide for a while.

12:09 After reading a blog post from fushar. I decide to spam him saying that I must be better than the admins since I solved SRM 532 so easily. I hope the admins read that whisper.

12:10 I ended up opening the 250-points problem first, for no good reason.

This looked like an … ehem… easy problem. As k can be at most 50 (It is not possible to have more rows than pencils), we can just iterate through all values from 50 to 1 until we find a correct one. What is left to do is to answer the question “Is it possible to have a given value of k?”.

First of all, let us keep a variable allowed, the number of valid rows we are allowed to make (For a k to be valid, allowed >= k). All pencils of equal to k are allowed. Also, all pairs of different pencils such that their sum is k-1. I found that the test cases seemed strong, I made some mistakes like using the same pencil twice (possible when k is odd). Thankfully the examples caught the mistake.

12:16 I have a lot of doubts about my 250, because there might be more mistakes that I made and did not get caught by the examples. Eventually, I switch to the 500 points problem. This match did not seem friendly towards the risk of opening 1000 first.

What an evil problem! Was my first reaction. I had some issues modeling this problem. At the end though, it works like this:

If there are N tasks, you will need to split N-1 times. This will make a tree of Foxes. At some point, you have to assign a task to a fox instead of splitting it. There are many tree shapes you can do. For example, look at the following two trees when there are 4 tasks:

   a              a
  / \            / \
 a   b          a   b
/ \ / \        / \
a d b c       a  c
             / \
            a   d

After performing all the splits required for a tree shape, all the foxes make their single task. One of the trees is the solution for example 2) the other is not, but could be a solution to another case with N=4. It all depends. On what? Eventually I noticed that the maximum time needed is quite small, so you can just do a search for this time limit until you find a time that is valid.

Is a time valid? This time limit will help you limit the shape of the tree. Whenever splitting your current group of nodes would make you unable to later process one of the tasks under the time limit, that is a good moment to take some of the nodes and assign that task to them. This reduces your number of nodes available to split and assign.

12:54 I think my solution for 500 is correct, but the simulation was a little tricky to code so I got doubts. I continued anyway and began solving the 1000-pointer.

Won’t go into a lot of details, besides of saying that it is important to see that swapping two front seats is equivalent to swapping the equivalent back seats and vice versa, so you only need to swap the seats in one of the rows. After that, you can make a dynamic programming solution that needs exponential time.

13:18 I also got doubts about 1000. Great.

13:26 : Intermission is that period of time in which you are supposed to rest, but it is impossible not to get anxious about the possibility of failing all of the problems.

13:30 : Challenge phase. I am currently third in my room. Props to DanteW for showing that rating determines nothing. Like I mentioned in the past. These early rounds show that it is quite possible for a gray coder to give battle against two yellow ones for the first place in a room, this was a good way to show it.

13:4?: I got lucky. As I was boringly reading at code, I notice something about a submission to the 250-points problem. It seems that the examples were not as strong as I thought and it was possible to pass them by making (allowed = k) instead of (allowed >= k) I think of a sample case {5,5,5,5,5,5} to challenge this bug. I feel confident and I decide to open more submissions to find the same bug. I challenge another and… just noticed it was jhtan… ouch. As the end of the challenge phase I looked for another victim, but I mistakenly make a wrong challenge against a code that seemed to have that bug.

13:45 Challenge phase ends.

I found that the admins were very curious about the problem setter guessing contest. I also found that I only received three submissions. Thanks to mystic_tc, we decided that it was possible to extend the deadline for 10 more minutes and broadcast a link to the contest!

This was fun. However, there were some technical issues in the site that was making it hard to share the information. We still managed to receive 37 submissions to the contest. I spent a lot of time organizing the emails I received. Here are some stats about the options posted. The writers today were: cgy4ever (Easy, medium) and ir5 (hard). Nobody actually expected cgy4ever but there were some correct guesses about ir5 and the hard problem. Congratulations to: cjoa2 , roypalacios, aquamongoose, bohuss, Tavo92, Rajat_Mathur90 and ortschun for scoring one point in the problem guessing game. For those who were not lucky today, don't worry, we still got plenty of matches with 3 problems each and plenty of opportunities to earn points.

In case you are wondering, here is a relation of the amounts of time each problem setter appeared in a guess. (Easy – Medium – Hard):

And here is a spreadsheet with the submissions (first row is the coder making the guesses, second the Easy guess, third the medium and fourth the hard).

This entry was posted by vexorian on Saturday, April 7th, 2012 at 9:46 pm.

2 thoughts on “Algorithm track round 1B

  1. Alexander Georgiev says:

    Vasyl without 4 and 7, me without Elly and vexorian while he’s competing. That seems like random guesses 🙂

  2. Hamzawy says:

    This solution for the medium problem was just awesome He modeled the problem to be like Huffman encoding. Very simple and very clear.

Leave a Reply