Postmortem: UVA World finals warmpup II

Contest link

BLeh , why did they have to make today's warmup the 14:00 GMT one instead of last one? I had an exam during the warmup and it seems I didn't have time to solve or even open the interesting parts of the problem set.

The exam
So, at 10:00 AM GMT-4 (exactly the same time as the warm up's start time) I was supposed to solve an exam. This was so lame.

10:40 : Exam begins, professor didn't arrived at 10:30 even though the exam's schedule was 10:00 AM - 12:00 PM...

Lame, only two questions , the first one was very easy using predicate transformer semantics (zero loops, conditional statements or anything.

Second question: Even lamer. So we have to use Hoare-Floyd logic to verify a program which has ... no post-condition. Well I got used to this during the course since it seems that verifying a program also includes making the post-condition up. Anyway... the algorithm was simple, just product using successive sums. The difficulty was that it had a do...while loop, and during the course we were only introduced to while loops. But the professor was kind enough to include the do...while loop's rule ... but THE RULE WAS WRONG. It is just the first time I get into Hoare-Floyd logic, but even I know there is no way in hell that B could be part of the post-condition of (do C while B) since we need B to be false to end the loop... So, I just figured out the correct rule by myself, included an explanation why the given rule was wrong, and a sort of proof that mine works based on the fact that do..while can be converted to a while loop by copying the loop's contents to the section before the loop...

So either I got a good 100% or 50% if somehow we were supposed to use the wrong rule to prove it or 0% knowing my luck.

11:00 : I am finished. I should probably go back home to actually try the warmup II contest... But I don't know if I should go or wait for the official end time... Always confusing.

11:40 : Ok, some people are just giving him their tests and leaving. I better do as well.

12:20 : I am at home and ready to open the problems...

Problem D
So, I look at statistics and problem D is by far the one with the most solutions. Turns out it was excessively easy. I actually double checked the statement just in case there wasn't a cheap difficulty device like having to use bignums or something. Turns out there wasn't. I just solved it. I wonder how would people manage not to have at least 1 problem in this warmup...

Problem J
Apparently the second easiest problem, I first thought that it was another easy one since I thought that if light a can trigger light b the converse is true as well. But then I noticed that it probably isn't the case. I asked for clarification to be sure. But the response to the question never came to my inbox...

So, after inspecting the examples, I finally figured out that the graph is directed, this makes things a little harder. I quickly noticed that all nodes belonging to a cycle could be treated as the same node. So we can do a SCC algorithm and then treat the transformed DAG graph for a solution. Once we can assume the graph is a DAG, things are easy. Just notice that you will have to manually turn a light on if and only if there are no lights that can trigger it. This can be read as "count all the nodes in the DAG that have in-degree equal to 0".

Coding the solution was hard since I noticed I never actually implemented a SCC algorithm before. I had just blurry memories of CLRS' lesson about it, so I went to wikipedia. It recommended tarjan's algorithm and also included pseudo-code for it. I took some time convincing myself that the pseudo-code is actually correct.

1:00 PM : The time I finished coding the problem coincided with lunch time. So I submitted it and checked the result... WA!

Lunch
I spent the whole lunch hour wondering if maybe the algorithm I conceived was wrong or not. I ended up quite convinced that it should work.

Back to problem J - Today's blunder
14:00 PM (ish)- I had no choice but to inspect my solution. I created some test cases and noticed that it was failing many of the new ones. After a lot of manual debugging I finally noticed my mistake... I had something like:

for (int i=0; i<T; i++) {
    cin >> N;
    for (int j=0; j<N; j++) {
         adj[i].clear();
    ...
}

It was supposed to be adj[j].clear() ... So, some ghost edges could remain and ruin everything... I just fixed this issue and got AC.

Problem B
14:40-ish . The next easiest problem was B. I quickly noticed it was just a dp/memoization one. So, I made a recurrence, but it allowed some cycles, so you had to solve the equation inside the recurrence to avoid the cycles (so that dp/memo worked). There is also the other problem of having to get a) the prime divisors of a number and b) The number of primes between 1 and a number. These both are easy using a sieve, I modified Eratosthenes' one so that it would store a number's lowest prime divisor in its array. If no prime divisor was found for a number use this number as the minimum divisor for the multiples that don't have such number yet.

I was having problems at first with the example cases. it turns out my recurrence was wrong. At the end I finally figured out:

f(x) = ( 1 + sum( f(y) for each y such that y is prime and x divides y) ) / ( (number of good y primes ) / (number of primes between 1 and x) )

I actually finished this problem very close to the end of the contest.

Final result: 77-th place . Hmnn, I never do well in world finals warmups...

Conclusion
I think that maybe if it wasn't for the time wasted in problem J due to not knowing enough about SCC and the lame mistake I could have solved another problem or at least have more fun from the contest. I need to practice AND study more theory.

Final thoughts
Why do blogs use HTML? instead of something like BBCode or whatever wikipedia uses? Since they have to be paranoid about XSS attacks, they don't let you use many tags and it can get confused by things like C++ code in which > and < are used... With bbcode, we wouldn't have so many problems...

Making spells in wc3: still torture

I spent a lot of holiday time making spells for the failed hero contest at wc3c.net My spells are somewhere around that page.

My conclusion is that. I have ZINC which makes typing very fast. Let me self indulge by saying it really does help. Of course, it also allows me to code atrocious things like:

        t = CreateTrigger();
        TriggerRegisterAnyUnitEventBJ(t, EVENT_PLAYER_UNIT_SPELL_CAST );
        TriggerAddCondition(t, function()->boolean {
            return BUILD_SPELL_ID == GetSpellAbilityId();
        });
        TriggerAddAction(t, function () {
            onRebuildStart( GetTriggerUnit() );
        });

Yay! anonymous functions... I wonder if people can actually read that code...

Another accomplishment of the year was the discovery of jEdit. It has also been amazing at increasing my efficiency. Thanks to auto complete I don't actually need to browse common.j every 5 minutes...

I have also made a lot of things to my linux command-line based warcraft map build system.

So, in theory I should now be able to make spells and maps quite quickly. Unfortunately that's not true. Just like I thought, the bottleneck was never coding or compiling, it was testing. In fact, I think I could have finished the spells using the vJass from 3 years ago much faster than I did now if map loading time took 1 second instead of 40 seconds. The other major issue is that wc3's engine is full of idiosyncrasies that force you to keep tweaking and testing object editor until you find something that actually works. In fact, making these spells was a fight against the engine. I had to deal with pocket factory and storm, earth and fire, both things required a lot of reverse engineering.

Reality is that regardless of all the work in the last years to make coding easier, and although we succeeded at that. Making spells is still torture. But I also figured that we still lack specialized libraries or at least I do. The spell making process invokes using certain tools and processes over and over and over again. The spells I made all are really just combinations of the same old 'processes' I've been using since 2004. The language has changed. The rules about how to code have changed. But it is still the same. Doing all these things over and over again is very repetitive.

I think some sort of library combination that has all these common processes abstracted in a way that you can just put them together as LEGO bricks would be amazing and seriously improve the speed of these things. I also think that maybe we need a better language. We've been messing with syntax and OOP concepts for ages but maybe we need something that would free us from having to use all that attaching and defensive programming related to it manually.

Postmortem: Topcoder SRM 456

Minus 161 rating points, that cannot ever feel good. Even those guys that claim that rating does not matter would not enjoy it. This was however a fair result and a consequence of me not following my own rules. What rules? I have two rules when solving SRMs.
Rule #1: "Always make sure to have at least 35 minutes to solve the easy problem".
Rule #2: "Do not challenge! No, not even when you are 100% sure the solution is wrong. Do not challenge! If your life depended on it, kill yourself. Challenging is not worth it!"

450 points: CutSticks
At first I didn't get why they made it a 450 points problem the constraints were very large. I was not able to understand it completely well after the first attempt to read the statement, so I bothered the admins with 3 silly questions. Once I finally understood the question I first thought it needed a greedy or math solution so I was discouraged since those things are not my strength.

I eventually noticed that if a math solution was available it is way too hard for a 450 points problem. I also noticed that even if we had some sort of direct greedy solution, the simulation would still run too slow as there may be up to 1000000000 steps. That's when I noticed the output is continuous and not integral - that's the sort of thing that hints for a binary solution. There it is! We can use a binary search and then ask "For a given length X, return whether it is possible for the K-th stick to have a length larger than or equal to x".

Unfortunately, an algorithm that answers that question was still a little tricky for me to implement. At first I was not considering the max cuts constraint which made me fail a single example, and when I added it I started failing all the other examples... I think I just had too many bugs and debugging was taking a good while. That's when I noticed... 25 minutes left! Darn I missed the deadline to open the easy problem. I had 10 minutes less than planned. My only hope was that I could solve 250 fast enough.

250 points problem - SilverDistance
#|@~! Ad hoc shortest distance problem. By the time I noticed that it was one of such problems, I knew I was doomed. I tried to simplify the problem and avoid as many pitfalls as possible. As usual, these problems can be converted to ones in which you start at (0,0) (then subtract x and y from gx and gy). I tried to take a look at what options we have in two moves:

#####
.$$$.
##*##
.$.$.
#.#.#

* is the silver (0,0), $ are the cells accessible by one step and # are the cells accessible by two steps. I noticed that (-2,-2), (0,2), (2,-2), (-2,0), (2,0), (2,-2), (-2,2), (0,2) and (2,2) are all accessible with two steps, so I concluded that if both x and y are even, the solution is as easy as : 2*( x/2 + y/2 - min(x/2,y/2). And if they are not, then we must just move the silver to another square until the parities change.

Blunder: Huge mistake, I assumed that just one move is required to change the parities correctly. I did not notice that it is not possible to exclusively change the x parity without changing the y parity in one step. My solution would just try any of the 5 possible directions when the coordinates are not even (and pick the minimum distance among the ones that make the differences even) This was evident after I failed the example tests.

Only five minutes left and I had to fix the mistake. I assumed that two steps should be enough (and they are), so I changed my brute force loop to consider move costs and then manually generate the 2-step moves that exclusively change x. This was not brilliant as it turned out a little complicated to do those things manually. I only had one minute left when I finished but then I had to fix typos like forgetting to change [5] to [11] ... I swear that the match ended just at the second I finished all those typos! 5 extra seconds and I could have submitted it...

Challenge phase
For some reason, the fact I had 0 points and that my golden rule says "Do not challenge" I still managed to make an unsuccessful challenge. I was sure it would fail because I knew that tantian's solution was going to return 3 for {0,0, 2,1} and it did! - unfortunately, 3 was the right result. Somehow when solving the case manually by hand I thought the correct result was 2.

.W.
..C
*..

What happened is that when I tested in paper I thought (2,1) was at the W cell instead of the C cell...

---
The correct version of my 250 did pass system tests in the practice room. I later noticed that the worst mistake was approaching the problem that way. The real simpler solution was just to notice that the difficulty of the problem lies in the asymmetric "up" step. If it was gone the problem would be very easy, and in fact we can get rid of it! Just brute force for the number of "up" steps to take, then call a function that solves the simpler problem, and pick the minimum result for all the possible "up" counts - due to the constraints, we can try all possibilities from 0 "up"s to 2000010 (the extra 10 is just in case).

--
So, there we go, if I followed rule #2, I would have gotten a good 0.00 and my rating drop would have been lighter. If I didn't fail to follow rule #1, I would have had a positive score like 130 that would probably still lose rating, but perhaps not enough points to fall bellow 2000.

The real issue is the long time it is taking me to actually code a correct solution. In fact, the real time consumer is debugging the solution. I need to practice yet again on being able to get a solution right in the first try. With that skill I could have easily gotten decent scores in both 450 and 250. That will be my focus for practice before the next match.