October 20, 2018 Single Round Match 740 Editorials

SRM 740 was held on Oct 20th at 12:00 UTC-4. The problems for the round were written and prepared by misof.  the tested by monsoon. Thanks to monsoon for editorials too.

SRM 740 Editorial

Author: Tomasz Idziaszek (monsoon)

GetAccepted

Since every negation (no matter where it appears in the sentence) changes the meaning of the question to the opposite one, we only need to count the number of negations in the sentence. The odd number of negations results in the answer “True.”, and the even number of negations — in the answer “False.”
We can do it by splitting the sentence into words and count how many words “not” we get. See the following Python program:

class GetAccepted:
  def answer(self, question):
    number_of_nots = question.split().count("not")
    if number_of_nots % 2 == 1: return "False."
    else: return "True."

We get even simpler solution, by observing that every negation increases the length of the question by 4. Thus we can base our answer on the parity of the length of the question divided by 4. See a sample Java program:

public class GetAccepted {
  public String answer(String question) {
    int number_of_nots = ( question.length() - "Do you want to get accepted?".length() ) / 4;
    if (number_of_nots % 2 == 1) return "False."; else return "True.";
  }
};

LongJumpCompetition

In this problem it is enough to simulate the process described in the statement. We maintain an ordered collection of contestants, and update the order after each round.

struct Contestant {
  vector<int> jumps;
  int bib;
  bool operator<(const Contestant& other) const {
    // Vectors are compared lexicographically
    if (jumps != other.jumps) return jumps > other.jumps;
    return bib < other.bib;
  }
  void add_jump(int len) {
    jumps.push_back(len);
    // After adding a jump, sort jumps from the longest to the shortest
    sort(jumps.begin(), jumps.end(), greater<int>());
  }
};
struct LongJumpCompetition {
vector<int> recoverStandings(vector<int> jumpLengths) {
  int n = jumpLengths.size() / 3;
  vector<Contestant> person(n);
  // Initialize an array of contestants with no jumps
  for (int i=0; i<n; ++i) {
    person[i].bib = i;
  }
  // Simulate the rounds
  for (int phase=0; phase<3; ++phase) {
    for (int i=0; i<n; ++i) {
      person[i].add_jump(jumpLengths[phase*n + n-1-i]);
    }
    // Re-sort the contestants to get the new standings
    sort(person.begin(), person.end());
  }
  // Report the final standings
  vector<int> order;
  for(int i=0; i<n; ++i) {
    order.push_back(person[i].bib);
  }
  return order;
}
};

Rather than using a struct to represent a contestant, we could use a pair (sorted vector of all person’s jump lengths, person’s bib number) and utilise standard comparison operators. This could result in a shorter, but a little bit more cryptic code.
The jump lengths are negated, to ensure that the longest jump will be at the beginning of the vector after sorting it non-decreasingly. Since both vectors and pairs are compared lexicographically  we can simply compare such representations to get the correct ordering:

struct LongJumpCompetition {
vector<int> recoverStandings(vector<int> jumpLengths) {
  int n = jumpLengths.size() / 3;
  vector<pair<vector<int>, int> > person(n);
  for(int i=0; i<n; ++i) {
    person[i].second = i;
  }
  for(int phase=0; phase<3; ++phase) {
    for(int i=0; i<n; ++i) {
      person[i].first.push_back(-jumpLengths[phase*n + n-1-i]);
      sort(person[i].first.begin(), person[i].first.end());
    }
    sort(person.begin(), person.end());
  }
  vector<int> order;
  for(int i=0; i<n; ++i) {
    order.push_back(person[i].second);
  }
  return order;
}
};

EvenMatrices

Even matrices have an interesting property. Suppose that we were given an even matrix, but with values in the last row and last column hidden:

0101?
0111?
1010?
?????

Since we know that the number of 1s in each row and columns is even, we could easily deduce the contents of the hidden cells:

01010
01111
10100
10001

Thus if we are given any binary matrix of size (r-1) × (c-1), we can extend it to an even matrix of size r × c.
And vice versa, every even matrix of size r × c is uniquely determined by its top-left submatrix of size (r-1) × (c-1).
That shows that there are exactly 2^(r-1)(c-1) even matrices of size r × c.
(Thus there is no answer to the problem if k >= 2^(r-1)(c-1).)
To obtain the k-th even matrix in lexicographic order, we can find the k-th top-left submatrix in lexicographic order, and extend it. The extension will not break ordering, since each cell in the last column and last row depends only on cells which stands before it in row major order.
To find the k-th submatrix, we can just examine binary expansion of number k:

struct EvenMatrices {
vector<string> findKth(int rows, int cols, long long k) {
  // Fill the matrix with zeros
  vector<string> ans(rows, string(cols, '0'));
  // Iterate over cells of the top-left submatrix of size (rows-1)*(cols-1)
  for (int r=rows-2; r>=0; --r) {
    for (int c=cols-2; c>=0; --c) {
      if (k & 1) {
        // If the corresponding bit of k is 1, change the cell (r,c) in submatrix
        ans[r] = '1';
        // And immediately fix cells in the last column and the last row
        // to get the correct extension
        ans[r][cols-1] ^= 1;
        ans[rows-1] ^= 1;
        ans[rows-1][cols-1] ^= 1;
      }
      k >>= 1;
    }
  }
  // If k is nonzero, it means that it was greater that 2**((rows-1)*(cols-1))
  return k > 0 ? vector<string>() : ans;
}
};

RainForecast

We start by calculating the probability that the Ilko’s report will be broadcasted without change by the TV station.
Let a[i] be the probability that the person i got this report without change; of course a[0] = 1.
There are two cases in which person i can deliver report as intended by Ilko: either she obtains correct report (with probability a[i]) and she passes it without change (with probability p = deliverProbs[i] / 100.), or she obtains incorrect report (with probability 1 – a[i]) and she passes the opposite report (with probability 1 – p).
Therefore a[i+1] = a[i]*p + (1-a[i])*(1-p).
Should Ilko send to the TV station the prediction of the model (r = ilkoRain / 100.), the answer to the task would be r*a + (1-r)*(1-a). But Ilko knows the whole setup and he tries to maximize the above value.
Therefore he could do two changes:

• If the success rate of the model’s prediction is very poor (r < 0.5),
  he should report the opposite forecast, to have a better accuracy.
• If he supposes that people in the TV station will broadcast the opposite
  of what he tells them (a[n] < 0.5), then he should intentionally report
  the opposite.

Performing such changes is equivalent to taking max(r, 1-r) and max(a[n], 1-a[n]).
It is illustrated by the following program:

struct RainForecast {
double predictRain(int ilkoRain, vector<int> deliverProbs) {
  int n = deliverProbs.size();
  double a = 1.0;
  for (int i = 0; i < n; ++i) {
    double p = deliverProbs[i] / 100.;
    a = a * p + (1 - a) * (1 - p);
  }
  double r = ilkoRain / 100.;
  a = max(a, 1-a);
  r = max(r, 1-r);
  return r * a + (1 - r) * (1 - a);
}
};

DieDesign

Note that the probability of winning depends on the following sum: for each face on our die, count how many faces on the input die has less pips. Therefore drawing more pips on a die could not make it weaker.
Thus if we find a strong die which has at most the same number of pips as the input die, we could easily transform it to a strong die which has exactly the same number of pips (by drawing missing pips arbitrarily).
Moreover, suppose that we find an optimal solution. Look at any face of our die, suppose it has X pips.
If the input die has no face with X-1 pips, we can remove one pip from our face and still have a die that wins the same.
Thus, we look for a die that has at most the same number of pips as the input die, and each face of our die is either 0 or it is (some face of the input die) + 1.
We use dynamic programming here. The states are (number of faces painted, sum of pips used), and for each state we find
the winning sum.
If N is the maximal number of faces and P is maximal number of pips per face, we have N*N*P states, and for each states we need to consider N+1 values on a face.
Thus the time complexity is O(N^3 * P).

public class DieDesign {
  public int countSmaller(int val, int[] array) { int answer = 0; for (int i=0; i<array.length; ++i) if (array[i] < val) ++answer; return answer; }
  public int sum(int[] array) { int answer = 0; for (int x : array) answer += x; return answer; }
  public int max(int[] array) { int answer = 0; for (int x : array) answer = Math.max(answer,x); return answer; }
  public int[] design(int[] pips) {
    int sumPips = sum(pips), maxPips = max(pips), faces = pips.length;
    HashSet<Integer> candidateSet = new HashSet<Integer>();
    candidateSet.add(0);
    for (int p : pips) candidateSet.add(p+1);
    int C = candidateSet.size();
    int[] candidates = new int[C];
    { int c=0; for (int cand : candidateSet) candidates = cand; }
    int[] addsWins = new int[C];
    for (int c=0; c<C; ++c) addsWins = countSmaller( candidates, pips );
    int[][] mostWins = new int[faces+1][sumPips+1];
    for (int[] row : mostWins) Arrays.fill(row,-123456789);
    mostWins[0][0] = 0;
    int maxSumSeen = 0;
    int[][] bestFace = new int[faces+1][sumPips+1];
    for (int face=1; face<=faces; ++face) {
      int newMaxSumSeen = maxSumSeen;
      for (int oldSum=0; oldSum<=maxSumSeen; ++oldSum) {
        if (mostWins[face-1][oldSum] < 0) continue;
        for (int c=0; c<C; ++c) {
          int newSum = oldSum + candidates;
          if (newSum > sumPips) continue;
          newMaxSumSeen = Math.max( newMaxSumSeen, newSum );
          int newWins = mostWins[face-1][oldSum] + addsWins;
          if (newWins > mostWins[face][newSum]) {
            mostWins[face][newSum] = newWins;
            bestFace[face][newSum] = candidates;
          }
        }
      }
      maxSumSeen = newMaxSumSeen;
    }
    int bestWins = -1, bestSum = -1;
    for (int sum=0; sum<=sumPips; ++sum) {
      if (mostWins[faces][sum] > bestWins) { bestWins = mostWins[faces][sum]; bestSum = sum; }
    }
    int[] answer = new int[faces];
    int curSum = bestSum;
    while (faces > 0) {
      answer[faces-1] = bestFace[faces][curSum];
      curSum -= bestFace[faces][curSum];
      --faces;
    }
    int remains = sumPips - sum(answer);
    answer[0] += remains;
    return answer;
  }
};

LongPalindromes

Let’s begin with solving an easy version of the problem.
Suppose that we need to find the number of palindromic subsequences in a short string s[0..N-1]. We use dynamic programming approach: denote by dp[i,j] the number of palindromic subsequences of a substring s[i..j].
If letter s[i] differs from letter s[j], then we know that at most one of these letters could be included in a palindromic subsequence. There are dp[i+1,j] subsequences that do not include s[i], and dp[i,j-1] that do not include s[j].
Of course, we should take care of not counting twice subsequences that do not include both s[i] and s[j], thus in this case we have dp[i+1,j] + dp[i,j-1] – dp[i+1,j-1].
If letters s[i] and s[j] are equal, then there are additional palindromic subsequences that include both s[i] and s[j].
There are dp[i+1,j-1] of them (since after removing s[i] and s[j] they should form shorter palindromic subsequences).
Finally, we get a recurrence formula:

dp[i,j] = dp[i+1,j] + dp[i,j-1] - [s[i] != s[j]] * dp[i+1,j-1]

The answer to the problem is dp[0,N-1].
The above algorithm calculates it in time complexity of O(N^2).
Of course, explicitly applying it to the string from the problem is not possible, since N = repeats * n, where n is the length of the pattern and repeats could be as big as 10^9.
Such big value of repeats (which results in a big length of the string) suggests that the efficient solution could use fast matrix exponentiation. But how to find a suitable matrix?
Since the most important here is the length, let’s rewrite the recurrence formula in such a way that it makes more visible the length of the substring len = j-i+1:

dp^len[i] = dp^len-1[i+1] + dp^len-1[i] - [s[i] != s[i+len-1]] * dp^len-2[i+1].

The answer to the problems is dp^N[0].
Moreover, let’s use the fact that the string s[0..N-1] is in fact a result of concatenating copies of string s[0..n-1], therefore s[i] = s[i%n]:

dp^len[i] = dp^len-1[(i+1) % n] + dp^len-1[i] - [s[i] != s[(i+len-1) % n]] * dp^len-2[(i+1) % n].

The above formula shows that to calculate values dp^len[i] for 0 <= i < n we only need to know values dp^len-1[i] and dp^len-2[i] for 0 <= i < n. Moreover, the correspondence between them is linear, thus we could write a matrix of size 2n × 2n which multiplied by a vector of size 2n containing values dp^len-1[i], dp^len-2[i] results in a vector containing values dp^len[i], dp^len-1[i].
There is a small catch here: the linear formulas depends on value of len (thus for different values of len, we would get different matrices). But fortunately this value is inside expression (i+len-1)%n, thus in fact there will be only n different matrices.
By multiplying them all, we would get a single matrix (independent of len) which multiplied by a vector with values dp^len-1[i], dp^len-2[i], gives a vector with values dp^len-1+n[i], dp^len-2+n[i]. Raising this matrix to the power repeats, allows us to calculate dp^N[i] from dp^0[i] (all ones), dp^-1[i] (all zeros).
The overall time complexity is O(n^4 + n^3 log(repeats)) for calculating and multiplying n matrices of size 2n × 2n and raising such a matrix to the power repeats.
See the below code for details:

#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;
const int N=50, S=2*N, MOD=1000000007;
struct mat_t {
  int m[S][S];
};
struct vec_t {
  int m[S];
};
mat_t mat_mult(const mat_t& A, const mat_t& B) {
  mat_t C;
  REP(i,S) REP(j,S) C.m[i][j] = 0;
  REP(i,S) REP(k,S) REP(j,S) {
    C.m[i][j] = (C.m[i][j] + ll(A.m[i][k]) * B.m[k][j]) % MOD;
  }
  return C;
}
vec_t mat_vec_mult(const mat_t& A, const vec_t& B) {
  vec_t C;
  REP(i,S) C.m[i] = 0;
  REP(i,S) REP(k,S) {
    C.m[i] = (C.m[i] + ll(A.m[i][k]) * B.m[k]) % MOD;
  }
  return C;
}
mat_t mat_pow(mat_t A, ll n) {
  mat_t ans;
  REP(i,S) REP(j,S) ans.m[i][j] = i==j;
  while (n) {
    if (n&1) ans = mat_mult(ans, A);
    A = mat_mult(A, A);
    n /= 2;
  }
  return ans;
}
mat_t MAT[N];
void init_mats(string pattern) {
  int n = pattern.size();
  REP(m,n) REP(i,S) REP(j,S) MAT[m].m[i][j] = 0;
  REP(m,n) REP(i,n) {
    MAT[m].m[i][i] = 1;
    MAT[m].m[i][(i+1)%n] += 1;
    if (pattern[i] != pattern[(i+m)%n]) {
      MAT[m].m[i][n + (i+1)%n] += MOD-1;
    }
    MAT[m].m[n+i][i] = 1;
  }
}
struct LongPalindromes {
int count(int repeats, string pattern) {
  int n = pattern.size();
  init_mats(pattern);
  mat_t W;
  REP(i,S) REP(j,S) W.m[i][j] = i==j;
  REP(i,n) {
    W = mat_mult(MAT[i], W);
  }
  W = mat_pow(W, repeats);
  vec_t V;
  REP(i,S) V.m[i] = 0;
  REP(i,n) V.m[i] = 1;
  V = mat_vec_mult(W, V);
  return V.m[0];
}
};