Member SRM 491 commentary and explanation for the div1 easy problem.

FoxMakingDice
The 250, 600, 900 distribution was threatening this match to repeat the pattern of SRM 490. So I knew I had to be fast in this problem, and tried hard to do it... It didn't work.

Ok... so we always have 6 faces in the dice. We want to count the number of ways to assign the faces such that the sum of all opposite faces is equal and greater than or equal to K and the faces are different numbers from 1 to N.

Err, wait, how are two dices different exactly? The statement said that they are equal if you can rotate one to become the other. Well, that was a little confusing to me. What really helped was to notice that the first example had N=6, K=7 (normal 6 faces dice) and the result was 2.

Why two? Well, there are 3 pairs of numbers that give 7 as result, so there are C(3,3)=1 ways to pick the pairs, then according to word of God, there are two ways to assign these pairs to the dice. I decided to trust the problem setter on this.

So with fixed sum, we can count the number t of available pairs that give such sum, then 2*C(t, 3) is the number of ways to have dice that have opposite faces that sum sum.

Now we can just iterate from sum=K to 2*N (minimum and maximum sum value possible), and add up the totals.

Finding the number of pairs is easy, we can just iterate starting from x=1 , the opposite face must be (sum-x), so (sum-x > x) (because if that was not the case, we already counted this pair) and also (1 <= sum-x <= N). We just need to count the total values of x that follow those runs. This takes O(N) steps. The iteration for the sum value takes another O(N) steps. So the total complexity is O(N*N). The solution is then "simple" , except for calculating C(t, 3) . For some silly reason I used Pascal's triangle. Which introduced a silly bug, I had a [2001][3] array when I needed a [2001][4] array. Lame lame. Instead, it is better to just use t*(t-1)*(t-2) / 6 (that's what you get from manually calculating C(t,3).

    long long theCount(int N, int K)
    {
        long long ways = 0;
        //iterate through all possible face sums:
        for (int s=K; s<=N+N; s++) {
            long long t=0;
            //count the number of face pairs that yield s as sum:
            for (int x=1; (s-x>x) && (x<=N); x++) {
                if(s-x<=N) {
                    t++;
                }
            }
            if(t>=3) {
                // add C(t,3)*2 to the result, it neatly translates to:
                ways += (t*(t-1)*(t-2)) / 3;
            }
        }
        return ways;
    }

PrefixTree
I was wrong, unlike SRM 490, this medium turned out to be approachable without mass implementation issues. It was also in my opinion, beautiful , will elaborate later.
Update: Explanation for div1 600


Hard problem (whatever the name)
I had enough time to open it, but was clueless. During the challenge phase I found out it could have been used with min-cost max flow and binary search, that's crazy.

Challenge phase
This should underline neal_wu 's awesomeness. Before the challenge phase, I noticed there was a 600-pointer submission by a blue coder. So I rushed to open it quickly at the start of the challenge phase, and just as I finished reading the first three lines, it was already challenged by neal_wu. He later said he quickly noticed the guy wasn't picking all the subsets so he just gave it a random large challenge.

Rating and issues
Well, I had a chance to see for a second what my rating would become if this match is rated: 2035 ! That would mean I recovered from the losses of last match. Unfortunately, it appears that it won't be rated due to issues during the challenge phase :(.

Read More

The latest topcoder editorials I've written

Hello all (I wonder if anybody actually reads this blog, I have made a good effort not to post links to it or talk about it in public). I have decided to rebrand this blog. Its name is now Doomed to debugging and its focus will be about programming and computers but will try to use it for just stuff related to me learning programming and try as hard as possible to keep opinions and rants outside. (I cannot give guarantees though).

I could not help but notice that this blog has had no entries since October. As much as I would like to say I was busy, I really wasn't. Though lately and more than usual I have been attempting to write editorials for TopCoder matches. Let us try all that has happened since October.

TCO Semifinals and wild card rounds.
This was fun. In total, I had to write explanations for 7 problems (The explanations for 2 problems were already done). All of which were of semifinal level (The TCO is a world wide tournament). I have started to think that the editorial writer is the one that has to do the dirty work. You know, the problem setter has to think of clever problems. The testers have to find flaws in them and the director has to decide what problem is appropriate and what not. Who's left? The editorial writer! The guy that has to actually make an explanation for the problems that people have to be able to understand...

I'll have to admit, writing the editorial for the semifinals and wild card rounds felt like less work than usual. Usually, when writing the editorial for a SRM, I spend most of the time actually trying to solve the problems, which is not easy at all. It is in fact nigh impossible sometimes. This time, I had quick explanations from the problem writers and also the most helpful bits of text that Petr Mitrichev had in his own blog. Actually, after reading the stuff Petr wrote, I couldn't help but feel like a third wheel. It was not as clear to me as to why was it needed for me to make much longer versions of what Petr said and turn it into three editorials...

Another thing that made it easier than a usual SRM's editorial was that I did not have to write the match summaries - those paragraphs in the top of each editorial that supposedly explain what happened during the match - They are incredibly hard for me to write.

TCO 2010 Semifinal round 1 (Explanation for the easy problem was written by Ivan Metelsky)
TCO 2010 Semifinal round 2 (Explanation for the medium problem was written by Ivan Metelsky)
TCO 2010 wildcard round

Please notes that the editorials I write are subsequently posted to a wiki which every TC member can edit, so anything that reassembles correct English probably came from a helpful editor and not me.

The most difficulty I had while writing those editorials was actually the hard problem in the wildcard round. I was actually unable to make it run in time in Java, and I ran out of time to work on a correct version. But it was supposed to work well in theory and it implements the correct ideas. The second issue I had was with the Semifinal 2 hard problem, until that day I have had little to no experience with range trees.


SRM editorials
SRM 487
SRM 488
SRM 490

I have broken a record and written three SRM editorials in a row! I have to make a clarification, the reason I get to write editorials so frequently is not exactly because of the score they get in the feedback post that usually accompanies editorials when they are posted. The reason is actually that I am usually available to write editorials when other approved editorial writers are not. Of course, the positive feedback does help and I guess it would be possible for me to lose my approved editorial writer position if I get consistently bad feedback. I must confess I am usually shocked by the good feedback my editorials receive :).

Writing editorials for SRMs is very hard, because you must actually understand the solutions for the problems before being able to explain them, and SRM problems have gotten very hard lately. So I spend most of the time actually attempting to solve the problems, else I have to ask the contest director for help or see if there are useful hints at the forums. Some behind the scenes:

SRM 487: I actually reverse engineered the division 1000 hard problem's solution from what the source code of the top placed coders. During the match I tried to solve this problem and was elaborating on many approaches that were wrong. This match was very enjoyable to me both as a coder and as the editorial writer. Specially the graph coloring problem was just great.

SRM 488: This SRM... I must say that I seriously ran out of time when writing this editorial, because the division 2 and 1 hard problems had intended solutions I was not able to understand. At the end things turned out right, I think.

SRM 490: I hated this SRM while I was participating in it. By the time I opened the 250 it was pretty clear to me that it was going to be yet another mathy problem that was going to take ages for me to solve, and I already knew the medium level problem was worth 550 points which probably meant it was out of my league. At the end I ended up getting a very low score in the 250 problem and I had almost no time to solve the 550 problem. I was right on the preliminary solving idea for the 550 but was hours of debugging away from solving it. I lost many rating points thanks to this SRM and I once again failed to maintain a 2000+ rating for more than one match.

Writing the editorial for SRM 489 actually greatly improved my opinion on it. The 250 actually makes sense once you managed to picture how it works and explain it in text. The 550 was a very hard to implement problem but it was the kind of problem that rewarded you for thinking before implementing. But the real savior was the 1000 pointer. I actually did not even open it during the match, that was a mistake. The 1000 pointer was a maze one (I love maze problems) and it was very interesting AND it had something similar to a linear recurrence... It has many elements I love. Though TopCoder's contest system tends to sometimes be excessively punitive of slow submissions.

Oh, and I like this editorial because I managed to finish it even though I had to study and go to a "Group work and mnemonics 5" ... errr I mean "Software engineering" final exam during the first 8 hours of the deadline. At the end things turned out right.

SRM next Saturday
Member SRM 491 is set for next Saturday. Note that a large group of people are entering holiday and vacation periods, plus Saturday matches tend to be very active. I have the feeling this SRM will have many and many contestants, so I hope the problem set is fun and I also hope I recover my 2000+ rating.

That's how this entry ends. I'll return to debugging err... programming some new features for Xye.

Read More

Ubuntu Jaunty to Maverick 'upgrade' : The aftermath

Yesterday I upgraded my Ubuntu 9.04 desktop to 10.10 . Mostly because repo support for Jaunty has ended. What I did was a very irresponsible and risky thing simply because UBUNTU UPGRADES DON'T WORK. Ok, they sorta do, but just the smallest "dependency error" will at best doom you for hours of tweaking and at worst ruin your install forever. That wouldn't be a huge issue if dependency errors didn't happen ALL the time when upgrading from a ubuntu version to another...

And that's just when upgrading between two versions that are 6 months apart. Upgrading from Jaunty to Maverick multiplies the headaches by 9 (no, not by 3) and is very risky.

Why did I do it?

Why did I wait until 10.10 instead of just upgrading every month to the next version? Well, I was very happy with 9.04 and I am also lazy. I didn't need to upgrade until Jaunty Jackalope support ended.

Why didn't I just do a clean install? Well, that's what I am asking myself. The thing is that I can resist some hours of tweaking config and fixing errors, but I have been using this ubuntu install for at least 5 years now (I am quite sure it starting in Breezy Badger times) and thus I have tons, and tons of config and installed packages. If I went with a clean install, I would not have as many trouble getting the computer to work, but I would have to reinstall (read: download) tons of packages, and will also have to reconfigure things to suit me.

If you do not have patience or skills to be locket into ubuntu recovery mode (no UI) for 6 hours trying to fix stuff using command line you should definitely NEVER upgrade and ALWAYS do a clean install to the newer version, you'll live longer.

Anyway, if you are in my same situation, were using Jaunty and now want to upgrade you have two solutions: a) Upgrade to each consecutive version step by step using the update manager. Since those upgrades are supported, they will give you less issues. I didn't do it because I have low bandwidth and thus that process would have taken me three weeks...

Or b) This:
* Edit /etc/apt/sources.list (for example gksu gedit /etc/apt/sources.list)
* Optional/recommended : Get rid of any repository that is not from official ubuntu, just in case. You can add those repositories back later.
* In that file, replace every instance of "jaunty" with "maverick"
* now open a command line and do "sudo apt-get update"
* Then do "sudo apt-get --download-only dist-upgrade"

That will download all the upgrades for your packages.

* To install (and possibly doom yourself) do:
* Then do "sudo apt-get dist-upgrade"

What will happen is that ubuntu will try to update itself, and it will try very hard, but at one moment, it will fail, because a new package will conflict with an old package that was meant to be removed but for some reason wasn't, thus the thing will halt and will tell you there were issues installing one of the packages. You have no choice than to decrypt the terminal text and find the name of the package that is causing the conflict. Then do "sudo apt-get remove packagename" . Chances are that about 20 packages depended on that package... So it will tell you a big deal of dependencies that cannot be met. Your only chance is to do "sudo apt-get remove packagename1 packagename2 .. packagenameN" for ALL the packages, including the one you want to remove and those that required it. Then you will have to do dist-upgrade as well and repeat, and repeat.

Eventually, dist-upgrade will finish. But you have probably removed a big deal of packages... So you better try at least getting the basic stuff:

"sudo apt-get install ubuntu-desktop"

Then cross your fingers.

What happened to me It is not the first time I upgrade ubuntu, it is not the first time I upgrade between two versions separated by more than 6 months either. I was expecting all that dependency mambo. So I eventually reached the end of dist-upgrade. But when 10.10 booted... I have no mouse or keyboard in the graphical interface! ARRRGGG Things like that can happen because when trying to fix all those broken packages your system got horribly disconfigured.

After hours of trying to overcome it doing things like reconfiguring X server, removing nvidia drivers and others. It finally stroke me... Perhaps I just need to use the newer kernel. I was using the old one because I didn't update my grub's menu.lst (as since my setup is very old, updating menu.lst automatically will screw the formatting up and remove the windows XP entry). So I modified it to use the newest kernel.

Then X crashed (darn). But it turns out it was a simple issue, the kernel no longer loads the "nv" driver but the "nouveau" one so I just changed the driver used in xorg.conf.

After all of that my keyboard and mouse worked. I am using 10.10 already, however, there is a horrible, horrible issue, my Desktop's emblems and icon size data is lost! :( I will have to resize them and add emblems again :(


I seriously think that all ubuntu upgrade mechanism should be full of giantic warning signs before letting a user do it. I think there may be users out there finding howtos about how to upgrade to avoid a clean install and following them... No, people, do not upgrade unless you want to suffer. Do NOT upgrade.

Read More

How to turn a vector into a set

It is amazing how large the STL is and how it manages to surprise you every time you find a new trick out.

So, in python it is often useful to do this:

v = [4,5,2,7,5]
s = set(v)
if 4 in v :
    print "YESS!!"

By doing set(v) you create a set from the given list, which you can then use to do 4 in v.

I was practicing topcoder's SRM 426, and once again I got myself into a common theme: You have a vector<int> cardsReceived, does it contain int x?.

The form I would have used until today: (find(cardsReceived.begin(), cardsReceived.end(),x) != cardsReceived.end() ) is excessively ugly . But somehow it occurred to me to just try std::set's constructors:

set<int> rec( cardsReceived.begin(), cardsReceived.end() );
// ...
if( recset.count(x) ) {
     cout<<"YESSS"!"<<endl;
}

That's right, do not underestimate STL's constructors. Since this constructor uses generic iterators, you can use it for arrays as well:

int  A[6] = {2,3,2,2,4,5};
set rec( A, A+6);

Do not forget also that constructors may be used as functions:

int  A[6] = {2,3,2,2,4,5};
if( set( A, A+6).count(4) ) {
    cout<<"YEss!!"<<endl;
}

Off-topic: I once again got into the classical issue with using HTML for simple communication, thanks to HTML it is very difficult to use < and you have to always remember to use &lt;, that is very dumb, I will begin to look forward better wash to write entries for blogger.

Read More

Google code jam qualification rounds.

I've participated in google code jam since the 2008 version. Considering how the 2009 one went and seeing the problems in 2010's qualification round, I can predict with 95% confidence that in the 2012 google code jam:
- There will be 5 advancers to on site finals.
- The world champion will win 100 dollars.
- Rounds will last for four hours.
- Problems will be 350% more about implementation than they are now.
- Problems will be 10% as interesting as they are now.
- Filtering scoreboard by country will still be impossible.


Anyway, the positive thing about this round was that I finally learned my lesson. Nope, python is not the answer when there are bignum problems. Just because the contest organizer's don't feel like you should use C++ to solve a problem does not mean you shouldn't. In fact, after some time in chat I finally saw the light. GMP !.

Instead of spending 30 minutes of the following GCJ rounds trying to remember how to use python's bizare standard i/o (which for some reason is not as simple as cin >> n or n = sys.stdin.readInt()) (I am guessing all GCJ rounds from now on will use bignums). I can just use the GMP library. Because:

- It is free software!.
- It works.
- The c++ binding makes clever use of operator overloading - It is easier to use than Java's bignums...

Anyway, so here is what I learned.

Installing GMP
In ubuntu: sudo apt-get install libgmp3-dev libgmpxx4ldbl

Using GMP in your code jam c++ template

Well, it is easy, after #include "gmpxx.h" , simply use the mpz_class just as you would use a number type... Do not forget to change your compile command to link to this new library (I added -lgmpxx -lgmp to my g++ command inside the script that runs gcj code).

After installing and preparing GMP I gave it a try and coded problem B in c++ using GMP, it was very easy. Granted, I am no fan of large non-sense names as mpz_class so I used a typedef to call it big.

What follows is the elegant resulting c++ code I have fallen in love with:

#include <iostream>
#include "gmpxx.h"
typedef mpz_class big; 

using namespace std;

//=========================================================
// program:
//
int N;
big t[1000];

big gcd(big A , big B) {
    while (B != 0) {
        big C = B;
        B = A%B;
        A = C;
    }
    return A;
}

big solve() {
    big T = t[0] - t[1];
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            T = gcd(T, t[i] - t[j] );
        }
    }
    T = abs(T);
    return (T - t[0] % T) % T;
}


inline void init(){}
//=========================================================
// I/O:
//
int main()
{
    init();
    int C; cin>>C;
    for (int i=1;i<=C;i++)
    {
        cerr<<"["<<i<<" / "<<C<<"]"<<endl;
        cin >> N;
        for (int j=0; j<N; j++){
            cin >> t[j];
        }
        cout<<"Case #"<<i<<": " << solve() << endl; 
    }
    return 0;
}

Read More

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...

Read More

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.

Read More