SRM 627: Did I really code THAT?

Is this just fantasy? I am not sure if this actually happened, backtracking with binary indexed trees? What?

Div1 250: The one with letters

Game starts with a multiset of alphabetic letters. In every step, two distinct letters are taken and removed. Eventually, the multiset will be empty or contain only repeated letters, those letters are called winning letters. Return all the letters that can possibly be winning letters.

My idea, which I am not totally sure is correct. Is to check for each letter `c`, if it is possible that it will win. Then all the moves have to have the intention that the specified letter remains at the end. This means that we should first try to clear as many letters different to `c` as possible. Eventually, a list of equal letters that are distinct to `c` will remain, and we need to get rid of them by using the `c` letters. If these repeated letters are less than `c`, then `c` can win.

The trick then is to always pick pairs of letters distinct to `c` , and pick the two letters that are currently most frequent.

class HappyLetterDiv1:
 def getHappyLetters(self, letters):
    res = ''
    # for each letter ch, can we do it?
    for ch in sorted(set(letters)):
        # get a dict of distinct letters and counts
        other = { x : letters.count(x) for x in letters if x != ch }
        while len(other) > 1:  # at least two different ones
            # sort by frequency
            least = sorted([ (other[x],x) for x in other.keys() ])
            # remove a letter of each of the two most frequent:
            a = least[-1][1]
            b = least[-2][1]
            def dec(y):
                other[y] -= 1
                if other[y] == 0:
                    other.pop(y)
            dec(a)
            dec(b)
        if (len(other) == 0) or (other[other.keys()[0]] < letters.count(ch)) :
            res += ch
    return res

Div1 500: The one with a graph and inversions

You have a graph of at most `1000` vertices. The graph is special in which it is a tree with an extra edge added onto it. (The graph is connected, undirected, lacks loops and has exactly `|V|` edges)

The value of a vertex `x` is `V[x]`.

For a simple path of vertices in the graph, we make a sequence `S` of the values of the vertices in visited order. Now count the number of "inversions" of the graph. This is the number of pairs `(i,j)` such that `(i < j)` and `(S[i] > S[j])`. Return the minimum number of inversions in a sequence of at least `K` elements.

.... So the trick is that the graph is a tree with exactly one extra edge. So there is only one simple cycle in it. So there are at most 2 simple paths connecting each pair of vertices. So there are at most 2000000 paths. 2000000 sequences. With backtracking, we can visit them all. The problem is that you need to calculate the sequence's number of inversions as you build the sequence...

Let's say you have already chosen some of the previous elements in a sequence, and want to add `V[x]` to the sequence, we can count the number of added inversions by calculating the number of elements in the sequence that are higher than `V[x]`. So we "just" need to use a data structure that adds elements, removes elements and counts the number of elements larger than a integer `x` in `O(log(N))`. And we need to update that sequence (add , then remove) as part of the backtracking. Easy... So I implemented a binary indexed tree , called it fenwik for some reason and it seems to work.

// for each pair of edges (x,y), there are at most 2 paths.
// thus there will be at most 2000000 paths.


int fenwick[2048]; //probably wrong name

void fenwick_add(int x, int a = 0, int b = 1024, int node = 0)
{
    if ( a <= x && x < b ) {
        fenwick[node]++;
        if (a < b - 1) {
            int c = (a + b) / 2;
            fenwick_add(x, a,c, node*2 + 1);
            fenwick_add(x, c,b, node*2 + 2);
        }
    }
}
void fenwick_remove(int x, int a = 0, int b = 1024, int node = 0)
{
    if ( a <= x && x < b ) {
        fenwick[node]--;
        if (a < b - 1) {
            int c = (a + b) / 2;
            fenwick_remove(x, a,c, node*2 + 1);
            fenwick_remove(x, c,b, node*2 + 2);
        }
    }
}
int fenwick_counthigher(int x, int a = 0, int b = 1024, int node = 0)
{
    if (a > x) {
        return fenwick[node];
    }
    if ( (a==x) || (b <= x) ) {
        return 0;
    }
    int c = (a + b) / 2;
    int r = fenwick_counthigher(x, a,c, node*2 + 1)
          + fenwick_counthigher(x, c,b, node*2 + 2);
    return r;
}


int getMinimumInversions(vector<int> A, vector<int> B, vector<int> V, int K)
{
    int N = V.size();
    vector<list<int>> g(N);
    for (int i = 0; i < A.size(); i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    const int INF = 20000000;
    int res = INF;
    memset(fenwick, 0, sizeof(fenwick));
    for (int s = 0; s < N; s++) {
        vector<bool> visited(N, false);
        int t = 0;
        int inv = 0;
        
        std::function< void(int) > backtrack = [&](int x) {
            visited[x] = true;
            t++;
            int oinv = inv;
            inv += fenwick_counthigher( V[x] );                
            fenwick_add( V[x] );
            if (t >= K) {
                res = std::min(res, inv);
            }
            for (int y : g[x]) {
                if (! visited[y] ) {
                    backtrack(y);
                }
            }
            fenwick_remove( V[x] );
            inv = oinv;
            t--;
            visited[x] = false;
        };
        backtrack(s);
    }
    
    
    
    return (res >= INF) ? -1: res;
}

Challenge phase

Got lucky, the first place in the room clearly did 500 without the data structure part (Was using a std::multiset, but multiset doesn't help in the counting higher elements part). So I just challenged with a large case.