4 minute read

Went to Bloomberg’s headquarters in New York for a coding contest a few days ago. It looks more like a recruiting event than an actual contest, as the problems were fairly not difficult comparing to ACM contests, and it was only 2 hours.

Getting into the contest

There are like around 2^7 contestants in this contest, 3 from each invited university. Couple months before the actual contest on January 27, a local contest was held within USC to select representatives. 8 problems in 2 hours, each problem holds a different weighting, correlated with the difficulty.

After qualifying, Bloomberg schedules the flights, hotels and transport, so we the contestants just have to ditch the Friday classes and head to the airport. Of course, they pay for everything: round trip flights, stay at Fitzpatrick Grand Central over the weekend, cars between hotel and airport, etc. For free stuff, there’s a Bloomberg hoodie, beanie, $100 gift card, 2 $5.5 Metro cards, and a random nanoblock thing.

When we got there, they had a little tour around their pretty nice building. They didn’t walk us through a lot of it though; we went to the top floor to see the Manhattan view, grab free food, look at the UX lab and some random fish tanks and that’s it. The other contestants didn’t seem to give a * about the tour, I bet most of them came for the free stuff.

Rules

Basically the CodeCon was the same as local contest: 8 problems in 2 hours, open Internet open book and everything. Technically we could’ve joined the contest without all the flying since it was online anyways. I think there was also a synchronous event in London, and colleges like ICL and Oxford were there too.

Top three guys can actually win a prize. They gave out a laptop, a PSVR and something else I forgot. Given the slim chances I didn’t try very hard, since the marginal benefit is basically 0.

The contest started to everybody’s surprise since they “instead of pushing back the contest by 10 minutes, accidentally pushed it early by 10 minutes.” Well… alright, let’s get into coding then.

Problems

Honestly I don’t like this problem set too much. Even the local USC contest was more interesting; it had a little math thing like GCD, BFS maze search and DP. A few problems in the finals, however, are purely brute-force problems. The input sizes would be like around 2^4, and you just have to enumerate all the possibilities and do some stuff. Here are a few examples.

The sorting problem

Given an integer array of size at most 5 with unique elements, print the minimum number of pair swaps to make it sorted. The correct/most efficient way was to pick the minimum and move it in the front, something like this:

int sorting(vector<int>& v) {
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int mn = i;
        for (int j = i+1; j < v.size(); j++)
            if (v[j] < v[mn])
                mn = j;
        if (mn != i) {
            swap(v[mn], v[i]);
            ans++;
        }
    }
    return ans;
}

But here’s what I did:

bool check(vector<int>& v) {
    for (int i = 1; i < v.size(); i++)
        if (v[i-1] > v[i])
            return false;
    return true;
}

int sorting(vector<int>& v) {
    vector<pair<int, vector<int> > > bfs;
    bfs.insert(make_pair(0, v));
    for (int i = 0; i < bfs.size(); i++) {
        if (check(bfs[i].second))
            return bfs[i].first;
        vector<int> copy = bfs[i].second;
        for (int j = 0; j < v.size(); j++)
            for (int k = j+1; k < v.size(); k++) {
                swap(copy[j], copy[k]);
                bfs.push_back(make_pair(bfs[i].first+1, copy));
                swap(copy[j], copy[k]);
            }
    }
    return 0; // not reached
}

I was a little rushed and didn’t want to think through the correctness of picking the smallest every time, so I just enumerated all the possible swapping without any optimization. Each level multiplies the number of elements in the BFS vector by 10, and the number of levels is bounded by 4, so it was definitely fast enough.

The Pokemon problem

Two trainers are battling N Pokemons of their own. Each trainer has an order of battling the Pokemons, and they battle 1vs1 until their health goes to zero, then the next Pokemon in the queue take up the space. Damage is a function of parameters of the attacking and defending Pokemons. The problem is to maximize the number of Pokemons standing from trainer A at the end of the war using any permutations of the queue, given the order of trainer B’s Pokemons. The solution is also quite trivial, simply implement the battles and use next_permutation() to enumerate through all possible permutations. However I got stuck here and couldn’t debug because I was using the names of the Pokemons in the comparator of my Pokemon struct, but those names are not unique, so I’m missing some permutations. It was such a stupid bug.

And so on…

And then there are 2 more problems of exactly the same type: literally enumerate all possible configurations. I used the same recursive call structure, so the two solutions looked alike. After solving 4 and getting stuck on Pokemons, there weren’t too much time left, so I kind of just gave up at that point.

Results

4 problems and ranked 48th; my ICPC teammate Yuehui Wang also from USC got 7th. As you can tell, he carried my ICPC contests. It was more or less a speed contest, since I think only the last problem actually requires some algorithms (it was like a 2D matrix connectivity thing). I like the ones with a little more difficulty instead of “enumerate and take max”. Anyway, I need to get better and faster for next year’s ICPC SoCal regional.

Categories:

Updated: