CodeChef October Lunchtime 2016

CodeChef is so slow to access.

A The Largest Bouquet

Pick tree leaves that are either the same colour or on the same tree. Find the maximum value.

Find the maximum within the same matrix row and column.

B FastFood Combos

Every shop item has a unit price and various promotions: pay $P_i$ for $Q_i$ products. Find the minimum cost to purchase all $N$ products.

This still needs enumeration, but the key is how to enumerate.

First, $dp1[x]$ represents buying through a single channel, either individual prices or promotions. Enumerate $2^n$ promotion subsets to obtain the minimum promotion cost for every case.

rep(i, 0, n)
    {
        scanf("%lld", &val[i]);
        dp1[1 << i] = val[i];
    }
    dp1[0] = dp2[0] = 0;
    repp(i, 1, m)
    {
        ll mask = 0;
        ll p, q;
        scanf("%lld%lld", &p, &q);
        rep(j, 0, q)
        {
            int x; scanf("%d", &x);
            x--;
            mask |= (1 << x);
        }
        dp1[mask] = min(dp1[mask], (ll)p);
    }
    for (int i = (1 << n) - 1; i >= 0; i--)
    {
        for (int k = 0; k < n; k++)
        {
            if ((i >> k) & 1)
            {
                dp1[i ^ (1 << k)] = min(dp1[i ^ (1 << k)], dp1[i]);
            }
        }
    }

$dp2[x]$ represents the minimum when mixing the two methods. I learned a new subset-enumeration trick here.

for (int mask = 0; mask < (1 << n); mask++)
{
    int submask = (mask - 1)&mask;
    dp2[mask] = dp1[mask];
    do
    {
        dp2[mask] = min(dp2[mask], dp2[submask] + dp1[mask^submask]);
        submask = (submask - 1)&mask;
    }while (submask > 0);
}

The final answer is $dp2[(1 << n) - 1]$.

C Restore the Permutation

A permutation from $1$ through $N$ has two query types:

1 X Y D: whether $|A_x-A_y|$ is divisible by $D$.

2 X Y: whether $X$ is less than $Y$.

You may issue at most $N * 13$ type-1 queries and $N-1$ type-2 queries to reconstruct the sequence.

This is difficult. With $13 * N$ queries and $N$ around $10^4$, a logarithmic strategy is clearly needed—but how should it divide and conquer?

Use divide and conquer: first split all values by % 2, then split the % 2 == 0 group again by % 4. This lets you compare the minimum of every sequence and reconstruct the values by multiplying by 2.

D The Counties

Given a tree whose vertices belong to countries, answer $Q$ queries: how far is the nearest city of country $C$ from vertex $V$?

For constraints around $10^5$, CF 342E offers a block-decomposition approach.

Solve offline with tree divide and conquer. At each step, find the centroid and run DFS. For vertices in different subtrees, the minimum is the sum of country $C$’s minimum depth and the city’s minimum depth; for the same subtree, recurse.