Google Code Jam 2016

I completely forgot about the qualification round. This morning I woke up and was planning to have a normal day when I accidentally noticed in my calendar applet that "Qualification Round" was on. What qualification round!? Oh no, the google one...



So I decide to register to the contest and it's 15 hours late. What are even the rules? Is it the same as usual? What's the cut-off? It turns out everything is mostly the same. I need 30 points and just the small inputs are enough to give you 37 points. So it should be easy to qualify.

Perhaps it's too similar to previous editions? I think 1000 t-shirts is pretty low, considering how much the attendance has grown since this number was established. Actually when I look at the past I think I would have never really put as much work on programming contest if, ages ago, when I was getting started, there weren't as many small rewards for simple things as they were. In the past, in codejam or topcoder open, qualifying to the elimination rounds was worth a t-shirt and there were extra little rewards for advancing in other rounds. In fact, the first codejam done using Google's own site had regional semifinals so if you were in the top 500 you'd already win a paid trip to a google office.

Back to the present. Qualifying, even 15 hours late should be pretty easy for a decrepitveteran contest participant such as I. But the real contest is to get a perfect 100/100. So what are my chances there? Looking at the score board it seemed like this qualification round had easier problems than previous editions, as a really considerable amount of competitors already had the perfect score. So I gave it a shot. Note that I am starting to write this before the end of the round, so I don't know if I scored properly.

Problem A (Large)

Problem Statement

This is a straight-forward problem, you just need to simulate the steps until all digits are found. A pressing question is what's up with impossible cases? Well, I actually just coded right away and tested all 1000001 possible inputs from 0 to 1000000, with a maximum number of 1000 steps to find all digits. Even then, the simulation is very fast and the only case that doesn't reach all digits is `N = 0`, which will always be 0 no matter how far you go. So with that knowledge I just submitted an easy code:

    const int MAX_ITERATIONS = 1000;
   
    long solve(long x)
    {
        long y = x;
        set<char> s;
        for (int i = 0; i < MAX_ITERATIONS; i++) {
            ostringstream st;
            st << y;
            for (char ch: st.str()) {
                s.insert(ch);
            }
            if (s.size() == 10) {
                return y;
            }
           
           
            y += x;
        }
        return -1;
        // not pictured: I/O stuff including translating -1 to "impossible"
    }

Problem B (Small and Large)

Problem Statement

Well, the small version can be solved using a Breadth-First Search. Just consider a string of +/- as a vertex in some graph and each possible step is an edge between its initial setup and its resulting setup. Then you want to find the shortest path between the input and +++++...+ .  With `N <= 10`, there are at most `2^10 = 1024` vertices in the graph, so this is quite doable.


But I wanted to solve the hard version. Clueless as I often are, I just did the small version hoping that it would help me think of the hard solution.  I concluded some greedy approach was needed because all permutations of cookies are reachable from any initial setup so cutting the search space wouldn't work (for me).

After coding the small version and being able to see some of the solutions it generates, I noticed a very obvious pattern:

+++-++---+--+
----++---+--+
++++++---+--+
---------+--+
++++++++++--+ 
------------+ 
+++++++++++++  



Basically keep flipping the largest sequence of cookies at the top that have the same sign (+ or -) as the top-most cookie. You will eventually have a bunch of happy cookies. And this is the optimal solution. Because this is the optimal strategy in a different problem where a step consists only about changing the sign of a prefix of a string, and the other options in the real problem are not better.

    int solve(string s)
    {
        int n = s.size();
        int step_count = 0;
        while (s != string(n, '+') ) {
            int t = 1;
            while ( (t < n) && (s[t] == s[t-1]) ) {
                t++;
            }
            for (int i = 0; i < t; i++) {
                if (s[i] == '+') {
                    s[i] = '-';
                } else {
                    s[i] = '+';
                }
            }
            step_count++;
        }
        return step_count;
       
       
    }
   
   
    /* _Used this to think of the real strategy which was pretty obvious in
        hindsight ... */
    int solve_slow(string s)
    {
        int n = s.size();
        map<string, int> dist;
        queue<string> Q;
        dist[s] = 0;
        Q.push(s);
        map<string, string> parent;
        while (! Q.empty()) {
            string s = Q.front();
            Q.pop();
            for (int t = 1; t <= n; t++) {
                string ss = s;
                reverse(ss.begin(), ss.begin() + t);
                for (int i = 1; i <= t; i++) {
                    char & ch = ss[i - 1];
                    ch = ( (ch == '+') ? '-' : '+' );
                }
                if ( dist.count(ss) == 0) {
                    dist[ss] = dist[s] + 1;
                    Q.push(ss);
                    parent[ss] = s;
                }
            }
        }
       
        string w = string(n, '+');
        assert( dist.count(w) == 1 );
       
        {
            stack<string> S;
            string x = w;
            while (true) {
                S.push(x);
                if (parent.count(x) == 1) {
                    x = parent[x];
                } else {
                    break;
                }
            }
            while (! S.empty()) {
                cout << S.top() << endl;
                S.pop();
            }
        }
       
        return dist[w];
    }

Problem C (Small and Large)

Problem Statement

My initial hunch was that a huge majority of the possible binary strings are valid coins. Because really, primes tend to be hard to find and we want strings that aren't primes. Even though they can't be primes in many bases. But I still thought it would take a while to find 500 coins. So I decided to do something with threads. I find threads easier in python so I used python. When I finished coding it and tested, it turned out that the code was very fast, so the threads weren't needed :/, but it's still a cool looking solution:

N = 32
J = 500

NUM_THREADS = 4

EASY_PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

import random
import threading
import sys

mutex = threading.Lock()

seen_coins = dict()

def add_if_new(coin, divisors):
    with mutex:
        if coin not in seen_coins and len(seen_coins) < J:
            seen_coins[coin] = divisors
            sys.stderr.write( str(len(seen_coins)) + ' already!\n' )
            sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
            sys.stderr.flush()
           
           
def work_done():
    with mutex:
        if len(seen_coins) >= J:
            return True
        else:
            return False

def random_coin():
    x = [ random.randint(0,1) for i in range(N) ]
    x[0] = 1
    x[-1] = 1
    return tuple(x)


def is_divisor(coin, b, d):
    m = 0
    p = 1
    for x in reversed(coin):
        if x == 1:
            m = (m + p) % d
        p = (p * b) % d
    if m == 0:
        return True
    else:
        return False

def get_divisors(coin):
    divisors = []
    for b in xrange(2,10 + 1):
        for d in EASY_PRIMES:
            if is_divisor(coin, b, d):
                 divisors.append(d)
                 break
        else:
            return None
    return divisors

attempt_count = [0]

def worker():
    while not work_done():
        coin = random_coin()
        divisors = get_divisors(coin)
        if divisors != None:
            add_if_new(coin, divisors)
        with mutex:
            attempt_count[0] = attempt_count[0] + 1
            #sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
   
threads = [ threading.Thread(name='worker%d'%i, target=worker) for i in range(NUM_THREADS) ]

for t in threads:
    t.start()

for t in threads:
    t.join()

sys.stdout.write( 'Case #1:\n')
for x in seen_coins:
    for y in x:
        sys.stdout.write( str(y) )
    for div in seen_coins[x]:
        sys.stdout.write( ' ' + str(div) )
    sys.stdout.write( '\n')
    sys.stdout.flush()
    



I think one thing that improves the execution is I only test if the coin is a multiple of a small list of primes. Instead of looking for coins that are any composite number , I add the condition that they are a multiple of small primes. Most composite numbers are multiples of small prime numbers, so this shouldn't be an issue in theory, and in practice, it isn't.

Problem D (Small and Large)

Problem Statement

First the small problem is super trivial. Because `S = K`, so you can just test positions 1,2,3,...`S` and it will be enough. Because if there is any G in the initial string, then the final string will definitely have a G in that same position.


The larger solution is more complicated but not that much. Even though it took me a couple of hours to think of it .

If you want to be able to find any case that contains a G, then we should focus on the hardest cases, the ones that have only one G in the input: GLLL, LGLL, LLGL, LLLG. It turns out that if you include a G in position 1, it spreads to many positions in the later iterations. So imagine we had four positions: ABCD in the first string.  We want to find which positions of the second string would be effected by positions A, B, C and D (E.g: If there is a G in position A, then the second position of the second string will contain a G. If there is a G in position B, then the second position of the second string will also contain a G, so position 2 of the second string can be classified as AB. If you repeat this you will find: A, AB, AC, AD, AB, B, BC, BD, AC, BC, C, CD, AD, BD, CD, D. Perhaps it will be easier if you read it as: AA, AB, AC, AD, AB, BB, BC, BD, AC, BC, CC, CD, AD, BD, CD, DD. In fact, with 3 steps we have: AAA, AAB, AAC, AAD, ... DDD. And so and so, it's the same as thinking of numbers in base K. So for C = 3, if we want positions that cover as many initial Gs as possible then we want the positions that have ABC and DAA (or DAB or ADC, anything containing a D). You can get the position index by converting from base k to base 10. This explanation is probably very bad. Sorry, I can't do better without drawings.

    long translate(vector<int> digits, int K)
    {
        long res = 0;
        long p = 1;
        for (int i = 0; i < digits.size(); i++) {
            res += p * digits[i];
            p *= K;
        }
        /*for(auto x: digits) cout << " " << x;
        cout << " -> "<<res<<endl;*/
        assert(res >= 0);
        return res;
    }
    list<long> solve(int K, int C, int S)
    {
        list<long> res;
        int p = 0;
        while (p < K) {
            vector<int> digits;
            for (int i = 0; i < C; i++) {
                if (p < K) {
                    digits.push_back(p);
                    p++;
                } else {
                    digits.push_back(0);
                }
               
            }
            res.push_back( 1 + translate(digits, K) );
        }
       
        if (res.size() > S) {
            //assert(false);
            return {};
        } else {
            return res;
        }
    }

Final results

As I was typing, the round ended, let's check the final results...

All my large solutions were okay. But tons of people had them okay as well. I am barely in position 1246. That's pretty low, but I did start the round 15 hours late... (excuses)

Codejam round 1A, problem B : Hair Cut

Okay, I participated in round 1A and utterly failed. A ton of factors got involved that made me waste time.

• I thought of the solution for problem A, but when I started to code it I figured out I didn't actually set up my codejam test environment. I had a ton of setup to do to make my (worthless) solution multithreading support to work AND for it to work in gcc 4.8.2 with c++11 support.
• I got really confused by problem A, apparently eating 1.5 (or any other fraction) mushrooms per second is valid... but I don't think that was really well explained... Also what's up with "constant ratio" when the ratio is definitely not constant? It becomes 0 at some times? Huh? And how about giving you an input example before describing what the input is?
• I tried to solve B, my first solution was too slow, then I tried to find cycles in the simulation and it worked but I kept failing the small solution. There was a small bug - After doing the cycle stuff I forgot to return 1-indexed results... Overall what happened in problem B is I completely missed there's a very simple (but with caveats) solution until the last 2 minutes of the match, it was too late.
• C small is just bruteforce and convex hull. Thanks to allowing colinear points (artificial difficulty at its finest :/) I actually had to do a ton of fixes to my convex hull algorithm which I haven't really used in years. My code was pretty awful and there were a couple of bugs in that old code that I had to fix.

Anyway, since B-small / B-large are the only problems I solved that are actually interesting. Here is an explanation for problem B large:

The time

I think the most important thing is to notice the problem is much easier when we know the time `t ` at which customer `N` will be served. Imagine we knew this time in advance. Then we would only need a single loop to find all the barbers that finish serving a customer at time `t`. Each barber `i` is a cycle, every `M_i` the barber serves a new customer. So barbers with `M_i` such that: `(t mod M_i = 0)` will serve a new customer at time `t`.

You might be thinking that the solution is the barber that serves a new customer at time `t` and has the smallest index. This is not entirely true. Multiple customers may be served at time `t`, and `N` is not necessarily the first customer to be served at that time. How can we approach this?

Imagine a function `b(t)` that told you how many customers are served with starting time less than or equal than `t`. Then `b(t-1)` will be the amount of customers that were served right until time `t`. And `b(t) - b(t-1)` is the amount of customers that start getting served exactly at time `t`. Now `N - b(t-1) - 1` customers will be served at time `t` before `N`. Which means that we are looking for the barber with the (N - b(t-1))-th smallest index among those barbers with `(t % M_i = 0)`.

The last piece of the puzzle is how to find `t`. It all comes down to `b(t)`, with this function we can do a binary search for the smallest `t` such that `b(t) >= N`, this is the time you want.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the minimum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
    while (lo + 1 < hi) {
        D ha = lo + (hi - lo) / 2;
        if (P(ha)) {
            hi = ha;
        } else {
            lo = ha;
        }
    }
    return hi;
}

struct solver
{
    int N, B;
    vector<int> M;
    
    int solve()
    {
                
        auto begunByTime = [&](long t) -> long {
            if (t < 0) {
                return 0;
            }
            long begun = 0;
            for (int i = 0; i < B; i++) {
                // how many times did it start?
                begun += t / M[i] + 1;
            }
            return begun;
        };
        
        // Is the start time for at least N users <= t ?
        auto enoughBegun = [&](long t) -> bool {
            return (begunByTime(t) >= N);
        };
        
        long t = BinarySearch<long>(-1, 10000000000000LL, enoughBegun);
        long old = begunByTime(t-1);
        long rem = N - old;
        
        
        //cout << "time = "<<t<<endl;
        // find smallest index of a server that starts at time t:
        for (int i = 0; i < B; i++) {
            if (t % M[i] == 0) {
                if (rem == 1) {
                    return i + 1;
                } else {
                    rem--;
                }
            }
        }
        assert(false);
        return -1;
        
    }
    void init() { }
    void read() {
        cin >> B >> N;
        //N = 1000000000;
        //B = 1000;
        M.resize(B);
        for (int & x : M) {
            cin >> x;
            //x = 1 + rand() % 100000;
        }
        
    }

Edit: Fixed bugs, oh and also `b(t)` is just the sum of a bunch of divisions. For each barber, you can find the number of times the barber has started serving customers before or during `t` by just doing a division, because for every `M_i` seconds, the barber tries a new user.

Google Codejam 2015 Qualification Round : Part 4: C small

Part 1: Problem D in Emily

Part 2: Problem A in unnamed language

Part 3: Problem B in Julia

C small

Problem statement

Unlike the other Small problems I didn't really think of a solution of this right away. I had to take a day to do it.

The trick to the problem is that we can find in `O(n)` the product of the `x` first left-most numbers (for all `x`). And the same for the right-most numbers. So imagine if we had a substring `[a,b]`. If left[a-1] is equal to `i` and right[b+1] is `k` then all that we need to learn is if the substring is equal to `j`. If we can answer that question in `O(n^2)`, we have the whole problem solved. And we totally can answer that question! We just need to start with an `a`, then `b = a` and calculate the product for `b = a`, then it is easy to calculate the product when `b = a + 1`, just multiply one more number. And so and so for `b = a + 2`, etc.

The only extra complication is doing the multiplication with `i`, `j`, `k` and the signs... Well, really there are 8 distinct numbers, and we can easily index them and make a table, multiplying this index with this other index yields this other index...

So I tried free pascal. I used to code in Pascal, and I hated it. Now I don't really remember much. So I guess it counts? I had to relearn Pascal a bit. But I reached a solution... which failed. And then it failed again and again... I really thought the problem was in that big hardcoded matrix, and spent hours trying to think of a mistake there. Turns out that free Pascal's Strings are limited to 255 characters (What the hell, free pascal?). You have to use AnsiString for limitless strings.

program C;

function solution(s : AnsiString): String;
const
   CONST_I = 2;
   CONST_J = 4;
   CONST_K = 6;
var
   i, j, n, left, curr : Integer;
   right : Array[0..100000] of Integer;
   t : Array[0..7,0..7] of Integer = (
       (0,1,2,3,4,5,6,7),
       (1,0,3,2,5,4,7,6),
       (2,3,1,0,6,7,5,4),
       (3,2,0,1,7,6,4,5),
       (4,5,7,6,1,0,2,3),
       (5,4,6,7,0,1,3,2),
       (6,7,4,5,3,2,1,0),
       (7,6,5,4,2,3,0,1)
   );
   inputInts: Array[0..99999] of Integer;
   
    function ch2index(ch: Char): Integer;
    begin
        ch2index := CONST_K;
        if ch = 'i' then ch2index := CONST_I;
        if ch = 'j' then ch2index := CONST_J;        
    end;

begin
    
    n := Length(s);
    solution := 'NO';
    for i:=1 to n do begin
        inputInts[i - 1] := ch2index(s[i]);
    end;
    right[n] := 0;
    for i := n - 1 downto 0 do begin
        right[i] := t[inputInts[i]][right[i+1]];
    end;
    left := 0;
    for i := 0 to n-1 do begin
        curr := 0;
        for j := i to n-1 do begin
            curr := t[curr][inputInts[j]];
            if (left = CONST_I) and (curr = CONST_J) and (right[j+1] = CONST_K) then begin
                solution := 'YES';
            end;
        end;
        left := t[left][inputInts[i]];
    end;
end;


var
   X, L : Integer;
   w : AnsiString;
   ww : AnsiString;
   T : Integer;
   i,j : Integer;
begin
    readln(T);
    for i := 1 to T do begin
        Readln(L,X);
        Readln(w);
        ww := '';
        for j := 1 to X do begin
            ww := ww + w;
        end;
        //writeln(ww);
        writeln('Case #',i,': ', solution(ww) );
    end
end.

The end

I qualified! This was a lot more fun and far more stressful than usual.

Google Codejam 2015 Qualification Round : Part 3: B small in Julia

(Part 1: Problem D) (Part 2: Problem A)

After the disaster solving A-large, it became clear that I needed to do more than 2 problems to get an advancing score. But also both B and C seemed likely to be impossible in the languages I wanted. But I still didn't want to use my normal languages. I mean at least B-small seemed quite obvious. A typical problem we can solve with memoization. If we set the state to be equal to an array of 9 elements containing the number of eaters that have 1, 2, ... 9 pancakes. We need to notice that it never makes sense to create a plate that has more pancakes than the original plate from which we took the pancakes. Otherwise each minute just shifts the array...

Anyway, I decided to look for a new language to learn. But something a bit more usable than the other two. I tried Julia. It actually felt like cheating, because it turns out this is a pretty good language. There's a couple of things I don't like, like the 1-indexing. But it was overall a nice experience. Similar to python but with some differences. And apparently benchmarks say it is a bit faster. You can also make it less dynamically typed if needed. Anyway:

function solve(P)
    mem = Dict()

    function f(seq)
        if haskey(mem, seq)
            return mem[seq]
        end
        #println(seq)
        res = 1000000000
        if count(x -> (x != 0), seq) == 0
            # all zeros, base case
            res = 0
        else
            # let one minute go:
            a = [ seq[i] for i = [2:9] ]
            push!(a, 0)
            res = 1 + f(a)
            
            # move something:
            for i = [2:9]
                if seq[i] > 0
                    for j = [1:i-1]
                        #if j != div(i , 2)
                        #    continue
                        #end
                        for k = [1 : i - j - 1]
                            if seq[k] > 0
                                b = [x for x = seq]
                                b[k] -= 1
                                b[k + j] += 1
                                b[i] -= 1
                                b[i - j] += 1
                                res = min(res, 1 + f(b) )
                            end
                        end
                        # move to empty plate
                        if i - j < i
                            b = [x for x = seq]
                            b[j] += 1
                            b[i - j] += 1
                            b[i] -= 1
                            res = min(res, 1 + f(b) )
                        end
                    end
                end
            end
        end
        mem[seq] = res
        #print (seq)
        #print (" = ")
        #println(res)
        return res
    end
    
    seq = [ count(x -> x==i, P) for i = [1:9] ]
    
    return f(seq)
end

s = int(readline(STDIN))
for i = [1: s]
    n = int(readline(STDIN))
    q = split(readline(STDIN), " " )
    P = map( x -> int(x) , q)
    @printf "Case #%d: %d\n" i solve(P)
end

Coding this was easy except for googling how to do things. The logic I learned when learning python really helped.

Google Codejam 2015 Qualification Round : Part 2: A small/large

[Part 1]

My compiler

The other language I initially intended to use in codejam was an old compiler thing I coded in 2013. It was a school assignment that took me a couple of days to implement. It's just a C clone that doesn't even have arrays. But hey, at least it has integers. And can actually read. Although it can only read one integer, and write one integer. It doesn't have division either. But it compiles to 64 bits asm code which can be compiled to binary, so speed isn't a big issue.

Problem A - The one with shyness - Standing Ovation

I had to pick a good problem for this. But all seemed unsuitable. My first idea for problem A - Standing OvationWas to just bruteforce for the number of additional members. There's no reason to bring audience members who are shy, so their shyness should be 0. The maximum result is equal to Smax. For each candidate number of additional members, we can just simulate the process and check if everyone claps. So we can do this in an `O(S_(max) N)` loop quite easily.

For the large version, and also to solve using a language that has no arrays. We can use an on-line algorithm. We initially have `x` audience members with 0 shyness. We know those will be clapping. So we should worry about the rest. We encounter that there are `s_1` audience members with shyness 1. If `1 > x`, we need to invite one more audience member: `1 - x`. In fact, we can repeat this, now we know there are `max(1,x) + s_1` audience members that are clapping. We find that there are `s_2` members with shyness 2. And so and so.

The problem was that I needed to have a way to turn the neat input file into something my language can read. Then turn the language's output into something that looks like "Case #1: xxx". DISASTER, I actually learned that my asm code only does syscalls for reading bytes and then converts to integer and is not quite the same as a scanf or cin>>x... In fact, the whole thing really fails at reading files. Even ignored the format issues. I had to learn how to automatize having a terminal send keystrokes to my program for it to work. Apparently this is usually a thing that people need as there is a family of programs called expect that do this. Fortunately, after learning how to use expect I found that python has a pexpect module. This allowed me to create this nifty glue python program:

import pexpect
import sys

# call the solver program, return the result
def call_solver(smax, shy):
    try:
        child = pexpect.spawn ('./A')
        child.sendline('%d' % smax)
        child.expect( '.*' )
        for ch in shy:
            child.sendline ('%s' % ch)
            child.expect( '.*' )
        child.expect(pexpect.EOF)
        return int(child.before.split('\r\n')[-2])
    except:
        print "ERROR"
        return -1


T = int(raw_input() )
for i in range(1, T+1):
    s = raw_input()
    (smax, shy) = s.split(' ')
    smax = int(smax)
    print "Case #%d: %d" % (i, call_solver(smax, shy) )  
    sys.stdout.flush()

So now I am free to make my program using my language...

program Codejam2015A
{
    int n, a, s, i, cost;

    read n;
    read s;
    
    i = 1;
    cost = 0;
    //initial clappers (shyness = 0)
    while (i <= n) {
        read a;
        if (a >= 1) {
            if (i > s) {
                // must invite i - s
                cost = cost + (i - s);
                s = i;
            }
        }
        s += a;
        i = i + 1;
    }
    print cost;
    
    
}

Anyway, you can find the complete source code in the codejam score boards...

I submitted A-small, had a failure because it was slower than I thought, I tried to check if there was something wrong. It seems expect is slow in sending things.

I should have known that the reason it was slow would only get worse in A-Large, in fact, when I tried A.large, it turned out that it could barely solve one case per minute, even tho the program was, the glue stuff using expect was very slow, specially when there are 100000 line enters to send to the fake terminal... Failed A-large because of a time out.

Google Codejam 2015 Qualification Round : Part 1: D small in Emily

It's another google codejam qualification round and honestly, these rounds are getting old. We are supposed to spend a whole day solving problems, between the too easy Small inputs and the impossible Large inputs. And what for? Once you get enough points for the cut-off it's not worth it. Unless you planned to be connected at 19:00 and try to solve the problems as fast as possible, then your rank might actually mean something...

One time I had position 29 at a qualification round. Impressive! Except it's all fake. I didn't even qualify to the third round that year.

I actually might have some rants to make about the formats used in our competitions. Did you know that google found winning programming competitions is correlated with bad work performance? It's SCIENCE. (Supposedly). Although us fans of these contests might like to think there is some sort of mistake in this result of Google's data mining. We cannot just really say it's not true, without doing any actual analysis of the data used and how the conclusion was made.

Anyway, so I want to qualify to round 1, but I was bored of qualifications rounds. So I decided to make them interesting by doing something different to my routine of using c++ and trying to get a perfect score. Instead, I wanted to make special language choices. Use only languages that I designed myself or that I didn't actually learn before the day of the round.

Emily

Once I decided to use special languages. I knew that one of the languages to use today was Emily. It's a relatively new languages, so that's a bonus. Also because o> f luck I've been seeing many previews of its development and finding them interesting. Honestly tho I kind of made this decision without thinking a lot...

The day of the round I noticed I should start learning this language. I figured out a couple of issues. Emily doesn't seem to have a way to read input. Fortunately, it does have the ability to write things. Unfortunately, only strings that you cannot process or floats. For some reason, Emily in its 0.1 version only has floating point numbers. That was going to be a bit of a problem.

My initial plan was to only use Emily and the language I will mention next; and hope to advance using only them. *After* getting an advancing score, I could actually try to use other languages just for fun. When I opened the problems, this seemed difficult. All problems seemed to need arrays, or actual string manipulation or 2D arrays, which are worse to do in Emily. Eventually I noticed Problem D.

Problem D: Ominus Omino - (The one with n-ominos)

statement

When I read this problem, it seemed that the small input can be solved with a bunch of conditionals. And the results are just one of two strings. Conditionals are good news because at least they can be implemented in Emily. And we can print fixed strings. I would only need to use my text editor's regexes to turn input files into code that calls my Emily solution.

To solve this problem (The small version) you can just try all variations of R and C, and just try by yourself, is it possible to pick an n-omino that stops the other player from winning?

This is how my notebook looked after this:

The rest was just implementing everything on Emily. It was HARD. So many conditions. The interesting thing about Emily is everything is an unary function. And I mean EVERYTHING. This includes objects and numbers. Unfortunately, I couldn't think of a good way to think advantage of this in this problem.

\version 0.1

# Hi, I am using a language called Emily, it is in version 0.1 :/
# https://bitbucket.org/runhello/emily/wiki/Home


ALWAYSAWAY = "GABRIEL"
CANMAKELOSE  = "RICHARD"

min = ^a ^b (
    (a < b) ? a : b
)
max = ^a ^b (
    (a > b) ? a : b
)

case4 = ^R ^C (
    ( (max R C) == 4 && ( (min R C) >= 3 ) ) ? ALWAYSAWAY : CANMAKELOSE
)

case3 = ^R ^C (
    a = max R C
    b = min R C
    
    maxIs4 = ( (b == 3) ? ALWAYSAWAY : CANMAKELOSE )
    maxIs3 = ( ((b == 3) || (b == 2) ) ? ALWAYSAWAY : CANMAKELOSE )
    
    (a == 4) ? maxIs4 : (  (a == 3) ? maxIs3 : CANMAKELOSE )
    
)

even = ^X (
    ( (X == 0) || (X == 2) || (X == 4) )
)

case2 = ^R ^C (
    ( (even R) || (even C) ) ? ALWAYSAWAY : CANMAKELOSE
)

# woops, here was my mistake
case1 = ^R ^C (
    ALWAYSAWAY
)


mode = ^X(
   ( X==1? case1: X==2? case2: X==3? case3: X==4? case4: null ) 
]

solution = ^X ^R ^C (
    ( mode(X) ) R C
)


# Examples
println: solution 2 2 2
println: solution 2 1 3
println: solution 4 4 1
println: solution 3 2 3

I couldn't help but get carried away with the functional programming here. Case4 is a function that solves the case for tetraominoes, Case3 for tetraominoes, etc. mode is a function that picks which function to use according to X. I wanted this to just be an array, but apparently that's currently a bit difficult to do.

Out of google codejam 2013

That was a very bad day. At least I redeemed myself during the last few minutes and managed to submit something. Not good enough. If I was faster I could have at least gotten a t-shirt.

I was feeling a bit slow-minded today. So I was nervous about this match, the first hour was all about me trying not to get distracted and focus. I wasted minutes formalizing the cost formula based on a single number of stations. I am not sure why.

One hour later, I gave up and decided to read the other problems. Problem B seemed interesting.

Problem statement

So I got clever, and thought that the second result can be calculated if you find the minimum index of a player that will ALWAYS lose. The second result is equal to that index minus 1. Always win and always lose are very similar problems. So similar, that Always-lose can be seen as the complete reverse of always-win and we can find a relation-ship between an always-lose function and an always-win one...

...That's what I thought at least. But I was having issues, because when I did the example cases in paper, the trick was not consistent.

Things didn't make sense and time was flying. Decided to open the other problems. At first I thought C-small could be done with meet-in-the-middle (and maybe it can), but this problem is probably a bit too theorical for me. D-small seemed like a heavy implementation problem, I didn't even read it.

Less than 40 minutes left, I was about to just call it a day and get out of the codejam site. But then I decide not to give up. B is the one problem that seemed the most solvable, so I decided to finally face it!

It turns out that in my first analysis, I thought that P was the worst rank of the competitor that gets a prize. Whereas it actually is the number of competitors... I am fairly sure I would have solved this problem 1 hour earlier if it wasn't for this stupid mistake.

After correctly reading the statement, there is still the little issue of actually solving the problem (index that is guaranteed to win)... I assumed that it involved some recursion and binary representation, but I didn't know exactly what to do.

I decided to write a bruteforce solution for N=3, (8 players). I wanted to make sure that the larger P, the larger the result. For some reason I had doubts... I made a solution that showed, for each P, all the indexes that win and all that lose. Good news, so my first assumption is true.

In a flash of very lucky intuition, I noticed a pattern. These are the results of my bruteforce:

P = 0 : LLLLLLLL
P = 1 : WLLLLLLL
P = 2 : WLLLLLLL
P = 3 : WLLLLLLL
P = 4 : WLLLLLLL
P = 5 : WWWLLLLL
P = 6 : WWWLLLLL
P = 7 : WWWWWWWL
P = 8 : WWWWWWWW

If the i-th string is W, the i-th player is guaranteed to win.

So note how the first 4 indexes (after 0) have only one W, the next 2 indexes have 3, and the next 1 index has 7...

Time was running short, and I had this strong suspicion that I could use this logic to fill everything. For example, for N=4 (16 players), indexes 1-8 have one W, 9-12 three Ws, 13-14 seven Ws and index 15 has 15 Ws. I tested my fate, and this silly , out of nowhere logic works for B-small, the better news were that it is easy to optimize it for N=50, and I could solve B-large too...

There were 7 minutes left for the match. I tried to open A again, maybe if I could somehow solve A-small I could at least ensure a place in the top 1000. But it wasn't possible. Even if I thought of a solution, coding it would have taken far more than 7 minutes. I spent the last 5 minutes looking at how my rank became worse and worse and further from the top 1000. When the match ended, I was in position 1120-th. The large solutions were evaluated and I was 1057-th. So that's it. Maybe if google penalizes 57 solutions, I can get a t-shirt. Although to be honest, all codejam t-shirts throughout the years look the same. Maybe they changed the design this year.

-------------------

Rant: Too much emphasis in long problems. Most people would have nothing to do. I blame the 30 minutes extension in the coding time. The good thing about the codejam format was that it allowed to have approachable problems as small inputs. But lately the small inputs are tough anyway. Are B and C-small really much easier than the large ones?

Regarding the smug opposition to programming contests

It is an inevitable fact of life. A news bit will appear. Maybe it will be news about how the Chinese or Russian team won the ICPC, which forces Americans to come up with excuses. Or maybe it is news about someone winning the Hacker Cup, which forces programmers to come up with explanations as to why they didn't win it. The inevitable thing is that someone will start the discussion about how programming contests are not worth it. They don't teach you "real world" programming skills and they are bad metric for hiring.

There are times at which it just gets ridiculous. It could be an article about how Petr Mitrichev is such a high profile competitor and champion and ... Google hired him to improve their search engine and you will still find comments of the sort.

You know, I have spent my past life (A 7 years period is a life) in programming contests. I have plenty of things to say.

Real world programming

What I do at work consists primarily of X. Therefore, real world programming consists of X. Programming contests do not consist of X. Therefore, they are useless for the real world.

This is the part about these arguments that can really annoy me. It is an arbitrary separation between different parts of programming. A dismissive one. Because of course is some programming is not part of the real world, then it is most likely a game, or an illusion, or something like that.

In my case, I make my money from these contests so it is very difficult not to feel that they are very real things. But I know that I am an exception so let us ignore that little detail. It is true that most jobs in computer programming are different than the things you'd do in most programming contests. However, unless you are doing an internship, it is unlikely that a single activity will prepare you with the exact complete set of skills that will required for your job. You are not going to learn people skills from programming contests. But that doesn't mean that participating in these contests will make you unable to learn people skills. You can probably learn somehow. I am socially inept myself, but I know that plenty people that are into programming contests (and are better than I) are perfectly socially adapted people. I am pretty sure I am the odd case. Specially out of the samples I took from actual tournament finals I attended.

Programming contests won't teach you all the skills. So what? Spending your time in programming contests is not so different to spending it in the demo scene. Or in game modding. Personal projects. Hacking open source projects. Etc. You will not create a complete career of programming from this. But why is it that you think that you HAVE to? Some activities are just fun to do and that is good enough. Some activities are just entry points for something else. Some activities might allow you to learn a couple of things, but you will most likely need to do more than just spend time in those activities to have a complete learning process.

Anecdotally. I can tell you that you WILL learn some very real things. You will learn a lot about the programming language you pick. I learned 99% of my C++ knowledge from contests alone. You will learn about how to get an effective programming environment that suits for your needs. You will get used to coding and to enter into Code mode. You will keep your mathy brain hemisphere active and healthy. You will be able to quickly estimate if a piece of code will run in the time that you want given technical specs of a computer and other factors. You will be able to calculate big O easily. You will learn of your weaknesses and how to find and debug the most stupid bugs you could make. You will learn to make sure that something is actually correct before jumping to implement it. These are all very practical technical skills.

No one needs speed

There is a time component in contests. Therefore, only the fastest programmers win. Being a fast programmer is not good. We need code that is maintainable , not quick to write

I think this argument originates from having little/superfluous exposure to the programming contests world. It is true that most contests use speed as some sort of tie breaker when people solve a similar amount/quality of problems during a contest. There is a speed factor in the scoring. But I think that the outsider's eye might be getting the impression that this speed factor is far more important than it actually is.

It is very easy to fall into this trap when you are just getting started with programming contests. You assume that you are doing badly because you are not taking enough shortcuts when writing your code. Maybe because some of the top solutions are very bad role models, you get into doing awful things like abusing #defines, you mess up your code style and you begin to constantly rush when coding a solution. The thing is that after this transition to a speed freak, you begin to notice something strange: You are not improving that much. Maybe your score has improved, but you are still pretty much in the same tier as you were before. Worse, lately you are spending more time debugging your rushed solutions and taking a bit more time to solve the problems.

After all speed is merely a tie breaker. If you learn to solve the easy problems faster, you will still find yourself unable to solve problems that the better coders can solve. The amount of code needed during a contest tends not to be humongous, so the time it takes you to type it is not that important. If you jump quickly into typing a solution and the solution turns out to be wrong, you are going to take MORE time and you will like still get 0 points anyway. If you type something too fast or if you are careless with your code, you will also score a flat zero. You will find yourself reading your code more often than you write it.

Debugging is a vital part of programming contests. One that tends to be implicit and has a role that is hidden from the outsider eye. While you rush to type your code, you have to be careful to make it also easy to modify. You get used to things that are deemed good practices. Not because you like to follow the rules, but because you learned the hard way that you can get screwed by not following them. Programmers that finish a solution faster do it mainly because they have less bugs and they know how to debug themselves out. This is something that is evident from watching Petr's screencasts.

I used to be a programmer that rushed. With time I learned to still calm down. I discovered the hard way that coding solutions right away without making sure that they will work and rushing to type a solution very fast are ways to fail more often than not. I ended up learning a set of rules that I shouldn't break while coding. For example, I learned to avoid having multiple return values in a function because of the many times I had hard-to-catch bugs with memoization after breaking this rule. I learned that speed was not as important as theory and having a process to be able to convert new problems into problems I already solved. Contests do not only have a focus on speed, they have a far more extreme focus on correctness. In most of these contests, just a single wrong case will make your whole solution wrong. You learn to be careful of things that cause bugs. I developed an irrational phobia against floating point arithmetic.

I guess that there is a chance that those are just anecdotes and most people just code badly when participating in programming contests. There is still something important to say. If I started to type code twice as fast as I do. If I started to think of solutions twice as fast as I do now. I would still not be able to get better positions than the very top coders. I am talking about people that can solve in 20 minutes what I cannot solve in a week even with help. We are talking about a set of skills that is not as trivial as being "fast". We are talking about being fast when coming up to solutions to very tough problems. There is more than raw speed involved in this.

Concurrency is like super important, man!

The format is very limited so you never get to see parallel algorithms. (Or randomized algorithms, or approximate algorithms, etc.). There are technical parts of programming that are not dealt with, like caching. There are no interactive algorithms. Plenty of algorithms do not show up. Etc.

My problem with this is that it really overstates the importance of some subset of algorithms. I think that the algorithms you find in programming contests are varied enough. I also think that it should not be a matter of quantity. A good programming contest shouldn't be about how many algorithms you have learned. There is always time outside of algorithm contests to find/learn Voronoi diagrams in a library and they will be implemented much better than yours. They should be avoid solving problems. There is a standard set of tools that you will most likely use during a contest: Dynamic programming, Greedy, Binary search, BFS, DFS, Dijkstra, Max Flow should cover 99% of what you need. This is a good thing because it evens the grounds - Time you spent sitting in a classroom is not so important - . Theory is nice, but contests shouldn't be exams about how many algorithms you know. They should be more about the process of solving a problem. Reducing a problem to a combination of those 5 only tools is more interesting than having 1000 tools and knowing by memory what to use every time.

There is more to say about that argument:

I have never seen X in a programming contest. Therefore, they don't have it

Some of the criticism I read seem to deal with only a very partial view of programming contests and ignores that there are programming contests of all flavors and sizes. Most of the criticism seems to be really directed at the ICPC. The ICPC is, frankly, a terrible tournament*. Only universities are allowed. Only groups of three are allowed. Very ridiculous scoring rules (Probably what contributes to the perception that speed is all that matters). Weak example cases. Arbitrary rules for advancing teams that differ between regions. Even more arbitrariness in what allows a team to reach the regionals. Boring problems. Run all the test cases of a problem in a single program instance stuck to a gigantic queue. A lot of your usual criticisms of programming contests tend to apply mostly to the ICPC and similar. For example:

Language and technical limitations, Lack of multi threading, no concern about caching or external memory/ etc

Contests like the google Codejam or the IPSC don't have these limitations. Because your objective is to produce an output file rather than send source code to run. The IPSC is even better, because your algorithms are not limited to run only a few seconds per case. Although most people go standard in the Codejam, they don't have to. I don't have to. I have taken (limited) advantage of multi threading a couple of times. I think it should be possible for someone more experienced in concurrency to make paralel algorithms to solve certain problems. Since you run your code in your machine, you can go crazy and bother with far more technical aspects than usual. If you want to run each test case in one of the 120 computers you own, you can do it.

And those are only the contests that I have first-hand experience in. There were AMD sponsored contests in TopCoder that focused on multi threading and taking advantage of it. I never participated in them, but they existed.

Approximations, randomized algorithms, heuristics, interactive algorithms

Even online judges have this sort of problem every once in a while. But most importantly, the TopCoder Marathons and similar contests exist. A TopCoder Marathon is a contest that is very different to ICPC contests. There is not a correct answer. The author most likely will not have as strong of an answer as the best competitor. You need to keep improving your algorithms. The best algorithm wins.

(Because the best algorithm wins, there are many situations in which worrying about very low level speed matters. I remember having to deal with memory caching at least once. I know that the top level competitors in this setting go really low levels).

In addition, you do not only need to solve the problem. You need to know how to test your solution. I had to learn a lot about benchmarks and threading to be able to test solutions. I needed to be able to compare algorithms. This is usually how participating in a Marathon looks like.

Topcoder Marathons are certainly not the only contest that allows this. The IPSC has very interesting and nice problems that do not necessarily stick to the ICPC format. The codejam seems to be starting to try some problems like this. There are also plenty of similar contests that I do not have experience with.

Being able to read somebody else's code and find bugs.

Like really. Both TopCoder and Codeforces have this as part of their format. You can win extra points by quickly finding mistakes and the reason someone else's piece of code fails.

More professionally, though. TopCoder has invented a category of contests called Mod Dash. In this, programmers are paid to identify the source of an anomaly in a piece of software.

Actual software design and development

There are competitions in which you deal with having to design long lasting software. Development competitions in which making the objective is to develop the most maintainable code. Architecture contests... I feel like they are most likely very boring, but they exist.

To sum up

Programming contests are a fun activity. There is no shortage of opportunities to learn important lessons about programming. There are various kinds of programming contests for different tastes and interests. A programming contest may not open you the doors to the professional world, but they don't have to.

I am not saying that you should/must participate. If you don't like them. If you would rather do something else, go and do whatever you like. I think that in the programming world, the best you can do is something that you like. If you do it well, the opportunities will come by themselves.

_______________________________________________________________________________________

* I mean, we all owe the ICPC a lot for being a precursor to the programming contest paradise we are living in, and a lot of our competitors wouldn't have been part of programming contests if it wasn't for the ICPC. But it has really aged terribly.

Google codejam round 1A: Nice

That was nice, rank 29-th is most likely my best rank ever in a GCJ round that is not the qualification one.

Preparation

I improved my multithreaded template. It now has much less overhead and uses proper Unix threads.

Problem A - The one with math

Link to statement

It must be a miracle that one ml of paint is good enough to paint exactly π cm². This makes it so, the amount of paint needed to paint a black ring of larger radius R and smaller radius r is exactly: R² - r².

This problem is a constructive one. Do it step by step.

We want to find the maximum value of x such that: t >= costToPaint(x). Where costToPaint(x) is the cost to paint x black rings. The value of x can be very large, but it does not matter, because we can use binary search.

So the new problem is to find a quick way to calculate costToPaint(x), in order to solve the large input, we need o(x) time (Note that this is small-o notation, not big O). Let us look for a O(1) one...

The first black ring needs ( r + 1 )^2 - r^2, the second one needs ( r + 3 )^2 - (r + 2)^2, the third one (r + 5)^2 - (r + 4)^2 and so and so. We need to find the sum for 1 <= i <= x of :

( r + 2*i - 1 )^2  - ( r + 2*i - 2 )^2

Sounds difficult? Not really. Let us get clever and...

(r + 2*i - 1)^2  - ( (r + 2*i - 1) - 1 )^2

Then...

 = (r + 2*i - 1)^2  - (r + 2*i - 1)^2 + 2*(r + 2*i - 1) - 1
 = 2*r + 4*i - 3
 = (2*r - 3) + 4*i
...

sum(1 <= i <= x, (2*r - 3) + 4*i ) = (2*r - 3)*x + 4*x*(x+1) / 2

So we just need to find (2*r - 3)*x + 2*x*(x+1)

Be careful with overflow... I actually took most of those 40+ minutes being perhaps too careful about it...

long r, t;
// we only need to know if the result of f(x) is greater than t,
// so if we surpass INF, we can just stay there...

long mul(long a, long b)
{
    if (a >= INF / b) {
        return INF;
    }
    return a*b;
}
long add(long a, long b)
{
    if (a >= INF - b) {
        return INF;
    }
    return a + b;
}
long f(long x)
{
    // sum 1 <= i <= x : 2*r + 4*i - 3
    // = (2*r - 3)*x + 4*x*(x+1) / 2
    // = (2*r - 3)*x + 2*x*(x+1)
    // = x * (2*r - 3 + 2*x + 2)
    // = x * (2*r - 1 + 2*x)   // 2*r is at least 2
    return mul(x, add(2*r - 1, 2*x) );
}

long solve()
{
    // max x: t >= f(x)
    long hi = t + 1, lo = 0;
    
    while (lo + 1 < hi) {
        long ha = hi - (hi - lo) / 2;
        if ( f(ha) <= t) {
            lo = ha;
        } else {
            hi = ha;
        }
    }
    
    return lo;
}

Problem C-small the one with guessing

Link to statement

Is GCJ jumping the shark? They seem to be trying unusual stuff too much lately. Ok, it is fun though. It reminds me of IPSC, and IPSC is just the best yearly contest ever.

My approach was to find every possible combination of cards (order does not matter), and find the probability that such setting happens. Then, for each list of products, try each combination of cards and calculate the probability that IF the card combination was picked, the products are those. After doing all that, pick the combination of cards that has the best total probability (Probability to get the combination) * (Probability to get the product). This got correct in the first try.

Problem B - the one with the schedule and energy

Link to statement

I estimated that as long as I solved B-small I would likely advance, so I focused on the easy problem instead of spending time in the large one.

At any point, you have between 0 and E energy, so you can never spend more than E energy in any activity. In the small input, E is at most 5, and the number of activities is at most 10, so brute force for the amount of energy you spend in each activity is good enough. 5¹⁰ choices in the worst case.

int E, R, N;
int v[10];

int solve()
{
    vector<int> spend(N, 0);
    int best = 0;
    while (true) {
        //cout<<"="; for (int i=0; i<N; i++) cout << spend[i]; cout<<endl;
        // simulate
        int e = E;
        int gain = 0;
        for (int i = 0; i < N; i++) {
            int s = std::min(e, spend[i]);
            gain += s * v[i];
            // I had min(e, e - s + R) instead of min(E, e - s + R) :(
            e = std::min(E, e - s + R);
        }
        best = std::max(best, gain);
        
        // next choice
        int j = N - 1;
        while (j>=0) {
            spend[j]++;
            if (spend[j] > E) {
                spend[j] = 0;
                j--;
            } else {
                break;
            }
        } 
        if (j < 0) {
            break;
        }
    }
    return best;
    
}

C small 2

After solving that B-small, I wanted to solve more. I could spend my remaining 40+ minutes in B-large, or the harder C-small. C-small-2 has many advantages, it gives more points, and since it is a small input, you will be able to know for sure if you when you got it correct. I also had a sudden idea for C...

It turns out that:

a) My generation of combinations was slow, it is possible to generate the combinations (sorted) directly and then calculate their probabilities.

b) Plenty of combinations are unlikely, you can consider the X combinations with the largest probabilities such that the sum of their probabilities is something large. At first I tried 0.5, but apparently it wasn't large enough. At the end I tried 0.99, ignoring the improbable combinations that add up to 0.01 probability is actually a significant optimization. And this omission will reduce your success rate only by 1%. The success rate has to be about 1/8 in C-small-2.

My first attempt was a time out. It turns out that my approach was not fast enough. I found a way to precalculate the product probabilities for each combination, so that I only needed an O(K) loop per combination per list of products. Second attempt was wrong (0.5 is apparently not good enough). Third attempt: I noticed that 0.99 is good and fast. Correct!

Incidentally, I needed 1.5 minutes to run the final solution. If not for multi threading, I may have needed 5 minutes or more...

int cardProduct[7];

string curr;
double fact[13];
double TOTAL;

set< pair< double, string> > possibility;
set< pair< double, string> > probable;

map<string, map<int, double> > probableProduct;

void rec(int x, char ch)
{
    if (x == N) {
        // calculate the probability
        double p = fact[N];
        int i = 0; 
        while (i < N) {
            int j = i;
            while ( (j < N) && (curr[j] == curr[i] ) ) {
                j++;
            }
            p /= fact[j - i];
            i = j;
        }
        p /= TOTAL;
        possibility.insert( make_pair(p, curr) );
    } else {
        for (char b = ch; b <= '0' + M; b++) {
            curr[x] = b;
            rec(x + 1, b);
        }
    }
}

void init()
{
    TOTAL = 1;
    for (int i=0; i<N; i++) {
        TOTAL *= M - 1;
    }
    fact[0] = 1;
    for (int i=1; i <= 12; i++) {
        fact[i] = i * fact[i-1];
    }
    curr = string(N, '?');
    rec(0, '2');
    double P = 0.001;
    for_each(q, possibility) {
        P -= q->first;
        if (P < 0) {
            probable.insert( make_pair(q->first, q->second));
            string x = q->second;
            map<int, double> product;
            for (int i=0; i<(1<<N); i++) {
                int p = 1;
                for (int j=0; j<N; j++) {
                    if (i & (1<<j)) {
                        p *= x[j] - '0';
                    }
                }
                product[p] += p / (double)(1<<N);
            }
            probableProduct[x] = product;
        }
    }
    
}

string solve()
{
    pair<double, string> best = make_pair(-1.0, string(N,'2') );
    for_each( q, probable) {
        string x = q->second; //a combination of cards
        double p = q->first; //probability to get those cards
        //calculate the probability to get each product
        map<int, double> & product = probableProduct[x];
        // probability to get all K products
        for (int i=0; i<K; i++) {
            if ( product.count(cardProduct[i])) {
                p *= product[ cardProduct[i] ];
            } else {
                p = 0;
            }
            
        }
        best = std::max( best, make_pair(p, x) );

    }
    
    return best.second;
}
    void read() {