NPSC 2011

Still at the tip of the influence of the latest rounds of steroids, I got up at 7:30. The morning was spent doing a little bit of homework and a lot of talking with Eliza.

(For rankk, of course.)

Anyway, I reached our school labs at 9:30 and everybody started setting up the submission system. Spock showed up. The printer worked. Excellent. Boring expository of background ends here because it’s terrible blog material.

Ten o’clock spun around and we started reading the problems.

A quick skim. I decided to start on problem C, a simple massive Morse-like prefix code on the alphabet. I made the extremely weird decision to construct an if-then decision tree out of the 26 codes. The longest code was nine or ten levels deep, so finishing and testing took me an hour. Really, putting everything in an array of strings and writing a function to carefully scan for equality, watching out for nulls and spaces, was obviously the best way. The decision tree was endlessly hassling with indentation and copy-pasting.

Dawn was working on B, a basically pure-math problem concerning sizes of bent-tromino packings. We never finished it, probably because we didn’t come up with the right math. The problem had hidden subtlety.

I looked at the other problems. A skim told me that problem A was testing for graph isomorphism. I assumed there was a nice algorithm for it that I didn’t know of, and skipped ahead (a mistake T_T). E concerned a grid with “organs” and “bruises”; no solution jumped out at me. F looked like a pathfinding problem, but a little thinking told me the essence of it was really greatest-increasing-subsequence, and I started writing.

Pizza came around somewhere here. It was cheese pizza with no toppings. I don’t like cheese but it was better than I expected.

Back to the coding. My first try was TLE. I looked the problem up online (hooray for internet) and discovered there was an O(n log n) solution with binary search in the right places. My brain wasn’t in perfect algorithm shape, though, so putting the pseudocode into C++ took a while.

Anyway, apparently the organizers screwed up with the test data and they reevaluated everything at 12:30. Or started, anyway. Submissions started clogging up randomly. This was why they extended the thing at the end by 45 minutes, which gave us two extra problems. Now it’s a controversial decision, of course.

Okay, so basically this turned all my submissions into WA. I gave up and moved along.

The scoreboard showed that the easiest problems were C and A, which was a little surprising to me. Was graph isomorphism so easy? I looked it up online and learned that it was NP-complete.

I read the problem spec again.

8 vertices or less.

Zark.

Of course now it was only a matter of getting through all the 40320 permutations. The kludgy bit, pounded out randomly, went like this.

bool check(){ // dfs perm
    bool testFlag = true;
    for (int i = 0; i < vertices; i++){
        if (pp[i] == -1){
            testFlag = false;
            pp[i] = nextP;
            nextP++;
            if (check()) return true;
            nextP--;
            pp[i] = -1;
        }
    }
    // testing code went here

    return false;
}

(blech formatting is a pain)

Aaaaand AC on the first try again!

Time extension had me work on E, and again looking at the restrictions it seems the search place could be reduced to C(10,5) max, which is perfectly feasible. Heck, 10 factorial is pretty feasible. And I got it in before the new deadline. I made a few stupid bugs here because the number of organs was called K and I kept using it instead of the variables of iteration.

Lessons:

  1. Bounds can change the problem dramatically.
  2. Do not keep the one-letter names the problem says, even though everybody else does it.
  3. Pizza is okay.
  4. I really need to practice more.

Oh well, not that bad. Now to see if they let us into the finals.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s