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.