2019 TCO Algorithm Round 2B Editorial

By in Community Stories June 13, 2019

MedianFaking

Statement

You have πΉ sets of π‘€ measurements each. You have to change result of some measurements in such a way that median of the whole set of measurements becomes exactly π‘”π‘œπ‘Žπ‘™. Among all such changes you have to find the one having minimum possible amount of changed sets π‘‹ and among such changes you have to find the one having minimum total amount of changed measurements π‘Œ. Note that for even-sized arrays median is the smaller of two middle elements.

Solution

Let 𝑁=𝐹⋅𝑀 to be the total number of measurements. To begin with, calculate for each set 𝑙𝑒𝑠𝑖 which is amount of measurements within the set having result lower thanΒ π‘”π‘œπ‘Žπ‘™Β andΒ π‘”π‘Ÿπ‘’π‘–Β which is the number of measurements having result greater thanΒ π‘”π‘œπ‘Žπ‘™. LetΒ total_lesΒ andΒ total_greΒ be the sum of 𝑙𝑒𝑠𝑖 andΒ π‘”π‘Ÿπ‘’π‘–Β over all 𝑖correspondingly. To makeΒ π‘”π‘œπ‘Žπ‘™Β the median we should change some elements counted in eitherΒ total_lesΒ orΒ total_greΒ intoΒ π‘”π‘œπ‘Žπ‘™. First of all, we should decide on how much elements we should change. ForΒ π‘”π‘œπ‘Žπ‘™Β to be median it must hold that:

Thus we may define dif_le and gif_ge being equal to the minimum possible number of elements counted in total_les and total_gre respectively which must be changed to π‘”π‘œπ‘Žπ‘™ in order to make π‘”π‘œπ‘Žπ‘™ the median. Note that since total_les+total_gre≀𝑁 eitler dif_le or dif_ge will be equal to 0. Obviously, in optimal solution there’s no need to change anything from the set having dif=0 into goal as it will only increase total number of changed elements. Now that we know which type of measurements we should change and how many of them should be changed, we simply sort all sets via π‘™π‘’𝑠𝑖 or π‘”π‘Ÿπ‘’π‘– (whichever of dif_le or dif_geis non-zero) in descending order and keep taking them until we fulfil corresponding dif number. Please look into the code for further understanding.

Code:
vector <int> minimize(int F, int M, vector <int> data, int goal) {
  int N = F * M;
  vector<int> les(F), gre(F);
  for(int i = 0; i < F; i++) {
    int le = 0, ge = 0;
    for(int j = 0; j < M; j++) {
      le += data[i * M + j] < goal;
      ge += data[i * M + j] > goal;
    }
    les[i] = le;
    gre[i] = ge;
  }
  int total_les = accumulate(begin(les), end(les), 0);
  int total_gre = accumulate(begin(gre), end(gre), 0);
  int dif_le = max(0, total_les - (N - 1) / 2);
  int dif_ge = max(0, total_gre - N / 2);
  if(dif_le < dif_ge) {
    swap(dif_le, dif_ge);
    swap(total_les, total_gre);
    swap(les, gre);
  }
  sort(begin(les), end(les), greater<int>());
  int cnt = 0, ans = dif_le;
  for(auto it: les) {
    if(dif_le <= 0) {
      break;
    }
    cnt++;
    dif_le -= it;
  }
  return {cnt, ans};
}

DivisorSequences

Statement

You’re given integer π‘. You have to find the length of longest possible sequence π‘Ž1,…,π‘ŽπΎ such that:

  • π‘Ž1+β‹―+π‘ŽπΎ=𝑁,
  • π‘Žπ‘–<π‘Žπ‘–+1 for all valid π‘–,
  • π‘Žπ‘– divides π‘Žπ‘–+1 for all valid π‘–.

Solution

Let 𝐹(𝑁)Β be the maximum length of such sequence that doesn’t start withΒ 1. Then the answer would be equal to the maximum of 𝐹(𝑁)Β and 𝐹(π‘βˆ’1)+1. But for this function it is easy to come up with recurrent formula:

Here 𝐷 passes through all divisors of 𝑁 except for 𝑁 itself. Explanation here as follows: since allΒ π‘Žπ‘–Β are divisible byΒ π‘Ž1Β we may say that 𝑁 is divisible byΒ π‘Ž1Β as well. If we try all possibleΒ π‘Ž1Β among divisors of 𝑁, we will see that after we usedΒ π‘Ž1Β we have to split the numberΒ π‘βˆ’π‘Ž1Β into similar sequence but having all elements divisible byΒ π‘Ž1. The length of such sequence would be equal to:

Thus if we consider all values of π·=π‘π‘Ž1 except for π·=𝑁 which goes from π‘Ž1=1, we’ll obtain the formula mentioned above.

It is pretty hard to make proper estimation of time complexity for solutions using this formula as they turn out to be extremely fast even if you don’t even store already computed values and simply compute them from scratch. For solution with memorization of already computed values estimation might be an π‘‚(𝑁2/3) as number π‘ generally has at most π‘β€Ύβ€Ύβˆš3 distinct divisors and you look on each pair {𝐷|𝑁} of nested divisors at most once. But actual running time is greatly less.

Code:
const int maxn = 4e5;

int prec[maxn];
unordered_map<int, int> gg;

int get_ans(int n) {
    if(n <= 1) {
        return 0;
    } else if((n < maxn ? prec[n] : gg[n])) {
        return (n < maxn ? prec[n] : gg[n]);
    } else {
        int res = 1;
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                res = max({res, 1 + get_ans(n / i - 1), 1 + get_ans(i - 1)});
            }
        }
        return (n < maxn ? prec[n] : gg[n]) = res;
    }
}

int longest(int N) {
  for(int i = 1; i < maxn; i++) {
    get_ans(i);
  }
  return max(get_ans(N), 1 + get_ans(N - 1));
}

DivisorSequences

Statement

Two players are playing a game. Each choose a positive integer (let them be π΄ and π΅), after that:

  • If π΄=𝐡, then the game is a draw and there’s no payment,
  • If |π΄βˆ’π΅|≀𝐷 then player with bigger number gets π‘ dollars from the other one,
  • If |π΄βˆ’π΅|>𝐷 then player with smaller number gets πΉβ‰₯𝑁 dollars from the other one.

Strategy of a player may be described by the sequence π‘1,𝑝2,… of probabilities to choose each number.

Consider the lexicographically largest strategy which maintains Nash equilibrium. Given number π‘˜, you have to output π‘π‘˜.

Solution

Let the strategies of both players be 𝑝1,𝑝2,… and assume that they’re in Nash equilibrium. Expected profit may be written as:

WhereΒ πΈπ‘˜Β is expected value of profit after player choseΒ π‘˜. It can be expressed with the following formula:

Where π‘ƒπ‘˜,𝑖 is profit we get if we play π‘˜ and opponent plays π‘–. Now note that if πΈπ‘–>𝐸𝑗 and π‘π‘—β‰ 0 then we may get better expected value if we turn π‘π‘— to 0 and raise π‘π‘– by the initial value of π‘π‘—. Thus if π‘π‘–β‰ 0 and π‘π‘—β‰ 0 then πΈπ‘–=𝐸𝑗. Also say if π‘π‘—=0 and π‘π‘–β‰ 0 then πΈπ‘–β‰₯𝐸𝑗, so expected profit for values π‘˜ with π‘π‘˜β‰ 0 will all have the same πΈπ‘˜ which is at least as large as any πΈπ‘– for π‘π‘–=0.

It’s still not enough to find the strategy uniquely. Next thing to note now is that πΈπ‘˜β‰€πΈ1 for π‘˜>2𝐷+1 because π‘ƒπ‘˜,𝑖≀𝑃1,𝑖 for all π‘– and all π‘˜>2𝐷+1. Thus if we consider arbitrary strategy π‘1,𝑝2,… we will get a strategy with at least same expected value of profit if we turn all π‘π‘˜ to 0 for π‘˜>2𝐷+1 and increase π‘1instead. New strategy would also be lexicographically larger then initial one.

In this way we’re only interested in strategies with π‘π‘˜=0 for π‘˜>2𝐷+1 and 𝐸𝑖=𝐸𝑗 for 𝑖,𝑗≀2𝐷+1. We may find it uniquely if we solve the system of 2𝐷+1 equations, first one being and all the others being 𝐸1=πΈπ‘˜Β forΒ π‘˜Β fromΒ 2Β toΒ 2𝐷+1.

Code:
public double getProbability(int D, int N, int F, int query) {
    if (query > 2*D+1) return 0.;
    double[][] P = new double[2*D+1][2*D+1];

    for (int a=0; a<=2*D; ++a) for (int b=0; b<=2*D; ++b) {
        if (a == b) P[a][b] = 0.;
        if (1 <= a-b &amp;&amp; a-b <= D) P[a][b] = N;
        if (D < a-b) P[a][b] = -F;
        if (1 <= b-a &amp;&amp; b-a <= D) P[a][b] = -N;
        if (D < b-a) P[a][b] = F;
    }

    double[][] E = new double[2*D+1][2*D+2];
    for (int d=0; d<=2*D+1; ++d) E[0][d] = 1.;
    for (int r=1; r<=2*D; ++r) for (int d=0; d<=2*D; ++d) E[r][d] = P[r][d] - P[0][d];

    // gauss
    for (int r=0; r<=2*D; ++r) {
        int biggest = r;
        for (int r2=r; r2<=2*D; ++r2) if (Math.abs(E[r2][r]) > Math.abs(E[biggest][r])) biggest = r2;
        for (int c=0; c<=2*D+1; ++c) { double t = E[r]; E[r] = E[biggest]; E[biggest] = t; } // swap rows
        for (int r2=r+1; r2<=2*D; ++r2) {
            double mul = E[r2][r] / E[r][r];
            for (int c=r; c<=2*D+1; ++c) E[r2] -= mul*E[r];
        }
    }
    double[] ans = new double[2*D+1];
    for (int r=2*D; r>=0; --r) {
        double rhs = E[r][2*D+1];
        for (int c=r+1; c<=2*D; ++c) rhs -= E[r] * ans;
        ans[r] = rhs / E[r][r];
    }
    return ans[query-1];
}