TCO 2015 Round 1A

I guess I advanced? Unless there is an implementation bug in my algorithms, which is quite possible. I know they are theoretically correct.

While solving the first two problems I kept having the feeling I was doing things the overcomplicated way.

250 points: The one with digits

You are given `1 <= L < R <= 100000`, find a pair `L <= a < b <= R` such that `a` and `b` have as many digits in common (ignore repeated digits).

So for a 250 in an "easy" round, this is not like the div2 easies. Can't just try all pairs `(a,b)`. In fact, the solution I used is quite complex (not hard, complex) and sounds like a division 2 hard thing?

The numbers will have at most 5 digits. So each number `L <= i <= R` will have at most `2^5 = 32` subsets of digits. The idea is to try them all and check if any number in the past had that subset of digits. Hey, it works.

// extract digits from x, call f(d) for each digit d we find.
void forEachDigit(int x, std::function<void(int)> f)
{
    while (x > 0) {
        f(x % 10);
        x /= 10;
    }
}

int maxsim(int L, int R)
{
    vector<bool> exists(1024, false);
    int best = 0;
    for (int i = L; i <= R; i++) {
        // create a bit mask of the digits in i:
        int mask = 0;
        forEachDigit(i, [&](int d) {
                mask |= (1 << d);
        });
        // for each subset of i's digits:
        for (int smask = mask; smask != 0; smask = (smask - 1) & mask) {
            // did we see this subset before?
            if (exists[smask]) {
                // if so, consider for maximum
                best = std::max(best, __builtin_popcount(smask) );
            }
            exists[smask] = true;  //whoops
        }
    }
    return best;
}

I did a wrong thing in my first submission, instead of marking exists[smask] = true for each subset I was marking exists[mask] = true for just the set...

500: The one with simulation

There is a graph in which all vertices have exactly one out-edge. You initially place tokens, at most one per vertex. In each step of the game, the tokens move to the vertex pointed by their out-edge. If at any time there are two tokens in the same vertex, you lose. Count the number of ways to place tokens without losing. The steps are repeated `K`<= 100000000` times.

So once two tokens end up in the same vertex, they will never separate again. So for example we can try simulating with a graph that has a token each. At the end of the simulation, some vertices will have multiple tokens. The trick is to notice that each of these tokens represent an initial vertex. If there are 4 tokens in a single vertex, it means there are 4 vertices that must all contain at most one token in total initially. So for each of the vertices at the end of the game, multiply (Number of tokens in vertex + 1).

The problem is that `K` can be pretty large. I used something similar to matrix exponentiation to simulate. But I think maybe it is possible to prove that you don't need to do too many simulations?

const int MOD = 1000000007;


// merge two simulation vectors
vector<long> merge(const vector<long> &A, const vector<long> &B)
{
    int N = A.size();
    vector<long> R(N);
    
    for (int i = 0; i < N; i++) {
        R[i] = 0;
        for (int j = 0; j < N; j++) {
            if ( (1LL << j) & B[i] ) {
                R[i] |= A[j];
            }
        }
    }
    
    return R;
}

int wayscnt(vector<int> a, int K)
{
    int N = a.size();
    // The "identity" vector each token in its initial vertex
    vector<long> I(N);
    for (int i = 0; i < N; i++) {
        I[i] = (1LL << i);
    }
    // B represents what happens after a single step:
    vector<long> B(N);
    for (int i = 0; i < N; i++) {
        B[i] = 0;
        for (int j = 0; j < N; j++) {
            if (a[j] - 1 == i) {
                B[i] |= (1LL << j);
            }
        }
    }
    // P[0] is what happens after one step
    // P[1] is what happens after two steps
    // P[2] is what happens after four steps
    //...
    // P[i] is what happens after 2^i steps 
    const int MAX = 30;
    vector<vector<long>> P(MAX, vector<long>(N) );
    P[0] = B;
    for (int i = 1; i < MAX; i++) {
        P[i] = merge(P[i-1], P[i-1]);
    }
    // with that in mind, we can find what happens after any number of steps
    vector<long> x = I;
    for (int j = 0; j < MAX; j++) {
        if ( (1<<j) & K ) {
            x = merge(x, P[j]);
        }
    }
    
    long res = 1;
    for (long y: x) {
        res = (res * (__builtin_popcountll(y) + 1 ) ) % MOD;
    }
    
    return (int)(res % MOD);
}

1000: The one with bipartite matching

Find the minimum total weight of edges to remove from a bipartite graph so that there is no perfect bipartite matching. o_O.

According to this: ItayGonshorovitzThesis.pdf, if we reduce the bipartite matching problem with flow and try to find the minimum cost to reduce the flow, that is NP-hard. Although with such a low constraint for `n`, maybe non-polynomial IS intended. I think that paper has interesting reductions for the problem so maybe it helps?