June 1, 2020 Single Round Match 729 Editorials

BrokenChessboard 

Used as: Division Two – Level One:

If we determine the color of the upper-left corner of the grid others will be uniquely determined. So we have only two different valid colorings.

For a fixed coloring, let’s count how many cells must be changed such that we reach the state. It’s simple using comparing the cells one by one.

Code by dhruvsomani:

    def minimumFixes(self, tup):
        a = 0
        b = 0
        for i in range(len(tup)):
            for j in range(len(tup[0])):
                if (((i + j)%2) and tup[i][j] == 'W') or (((i + j + 1)%2) and tup[i][j] == 'B'):
                    a += 1
                else:
                    b += 1
        return min(a, b)

SoManyRectangles 

Used as: Division Two – Level Two:

The observation is to think about when we add a new rectangle to the plane, how many regions added? When we add the first rectangle, it adds only one new region. The second rectangle can increase the number of regions to four. The i-th region adds at most i new regions.

So at the total, we have at most n * (n + 1) / 2 regions.

So we can iterate all of the regions and count how many rectangles cover this area. This leads to O(n^3) time complexity.

Now to find all of the possible regions, iterate on different x’s and different y’s. There is at most 2n different x’s in the input and 2n different y’s in the input.

For example if the input is {0, 0, 10, 20, 30}, {0, 0, 0, 0, 0}, {100, 10, 20, 30, 40}, {1, 1, 1, 1, 1}, the x’s we iterate are {0, 0, 10, 20, 30, 100, 10, 20, 30, 40} and y’s we iterate are {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}. For example for the point (10, 0) rectangles {1, 3} cover it.

Another strategy is sweep line. Sweeping from left to right, adding rectangles when sweep line reaches x1[i] and removing it when it reaches x2[i]. This way at each moment we have track of segments that present rectangles create on y-axes.

Code by cwystc:

#define FOR(i,a,b) for (int i=a;i<=b;++i)
int X[11111],Y[11111],n,XS,YS,ans;
class SoManyRectangles{
  public:
  int maxOverlap(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2){
    n=x1.size();
    XS=YS=0;
    FOR(i,0,n-1){
      X[++XS]=x1[i];
      X[++XS]=x2[i]-1;
      Y[++YS]=y1[i];
      Y[++YS]=y2[i]-1;
    }
    ans=0;
    FOR(i,1,XS)
      FOR(j,1,YS){
        int x=X[i],y=Y[j];
        int s=0;
        FOR(j,0,n-1)
          if (x>=x1[j] && x+1<=x2[j] && y>=y1[j] && y+1<=y2[j]) ++s;
        ans=max(ans,s);
      }
    return ans;
  }
};

RareItems 

Used as: Division Two – Level Three:

Consider we are in the middle of choosing. What is important for us? For sure, nothing is important but to keep track of the collection purchased. So let’s define dp[mask] where the mask is the collection seen so far. dp[mask] = expected number of purchases we need to perform to reach complete collection while we have seen the items present in the mask so far.

We have

because in this case, we are finished. The answer is dp[0].

Let’s think of transition. If we have seen items present in mask, there are two possibilities for the next purchase, name it item i:

• It’s present in the mask before.
  So we reach dp[mask] again and our state doesn’t change.
• It isn’t present in the mask before.
  So we reach dp[mask | 2^i].

Consider

We have

Overall time complexity is O(2^n * n).

Code by Meternal:

long double dp[1100000];
long double a[22];

double expectedPurchases(vector <int> frequency)
{
  int n = frequency.size();
  long double sum = 0;
  for (auto it : frequency)sum += it;
  for (int i = 0; i < frequency.size(); i++)
  {
    a[i] = (long double)frequency[i] / sum;
  }
  memset(dp, 0, sizeof(dp));
  int m = (1 << n) - 1;
  dp[m] = 0;

  for (int sta = m - 1; sta >= 0; sta--)
  {
    long double s1 = 0, s2 = 0;
    for (int j = 0; j < n; j++)
    {
      if (!(sta & (1 << j)))
      {
        s1 += a[j] * dp[sta | (1 << j)];
      }
      else
        s2 += a[j];
    }
    s1 += 1;
    dp[sta] = s1 / (1 - s2);
  }
  return dp[0];
}

MagicNumberThree

Used as: Division One – Level One:

We should calculate the number of subsequences of s that their sum is divisible by 3.

What is the maximum sum of a subsequence of s? 50 * 9 = 450.

So the problem could be converted to the knapsack problem. We have several items, we need to count how many subsets of them have the sum equal to k.

Let’s define dp[i][k] = in how many ways we can get sum equal to k if we can only use the first i digits.

dp[0][0] = 1, we can get sum equal to zero without using any of digits.

For i > 0, dp[i][j] = dp[i – 1][j] + dp[i – 1][j – s[i]]. Using 1-based indexing for s. If j – s[i] < 0, ignore it.

Finally, sum up all values of dp[n][k] which k is divisible by 3.

Further step: one can use dp[i][3], just store the sum modulo 3.
Code by 1007:

    def countSubsequences(self, s):
        n = len(s)
        dp = [1, 0, 0]
        for i in range(n):
            x = int(s[i])
            dpn = copy.deepcopy(dp)
            for j in range(3):
                k = (j + x) % 3
                dpn[k] += dp[j]
            dp = dpn
        return (dp[0] - 1) % MOD

FrogSquare  

Used as: Division One – Level Two:

Consider in the middle of the path, we jump from the cell v to u to t. If u is not on the border of the table, we can swap it with a cell on the border without losing the connection between v and u and, u and t.

The result is simple. We always use border cells as intermediate cells. So we have a graph with something like 4n vertices and 16n^2 edges. Which is small enough to run BFS.

Let’s review again. We use BFS with the cell (sx, sy) as the starting cell. When we want to discover neighbors of the current cell (which is present at the top of the queue), say v, we are only interested in cells which jump is possible from v to them and also they are on the border.

Finally, for each cell on the border, we check if it’s possible to reach (tx, ty) from this cell and update the answer.
Code by nuip:

int dst[1123][1123];

class FrogSquare {
public:
  int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) {
    if(sx==tx && sy==ty) return 0;
    auto ok=[&](int x,int y){return x*x+y*y>=d*d;};
    if(ok(sx-tx,sy-ty)) return 1;
    fill(dst[0],dst[1123],MOD);
    dst[sy][sx]=0;
    queue<pii> que; que.emplace(sx,sy);
    auto moveTo=[&](int x,int y,int X,int Y){
      if(ok(x-X,y-Y)){
        if(MN(dst[Y][X],dst[y][x]+1)) que.emplace(X,Y);
      }
    };
    while(que.size()){
      int x,y;
      tie(x,y)=que.front(); que.pop();
      if(ok(x-tx,y-ty)) return dst[y][x]+1;
      rep(i,n){
        moveTo(x,y,0,i);
        moveTo(x,y,i,0);
        moveTo(x,y,n-1,i);
        moveTo(x,y,i,n-1);
      }
    }
    return -1;
  }

};

XorAndLIS

Used as: Division One – Level Three:

Let’s reform the operation and make another operation. We want to prove that for every i < j, it’s possible to set x[j] = x[i] ^ x[j].

For example to make x[2] ^= x[0], we do x[2] ^= x[1], x[1] ^= x[0], x[2] ^= x[1], x[1] ^= x[0].

We can prove it by induction. Consider we can do x[j] ^= x[i] for j – i = k – 1, we want to prove that it’s possible to do x[j] ^= x[i] for j – i = k.

First, using assumption, do x[j] ^= x[i + 1]. Then x[i + 1] ^= x[i]. Again using assumption, x[j] ^= x[i + 1] and finally x[i + 1] ^= x[i] to undo changes on i + 1. This way we proved that it’s possible for every i < j to make x[j] ^= x[i] without changing any other values.

Using the new operation we can make x[i] ^= S which S = xor sum of a subset of indexes less than i.

We use the typical approach for solving LIS problems. Consider all of the increasing subsequences with length j we can make using the first i elements (maybe by applying some changes), we store the minimum value of the last element of these subsequences in dp[i][j].

dp[i][j] = min(dp[i  – 1][j], X) where X is the minimum possible value of x[i] ^ S > dp[i – 1][j – 1] (using 1-based indexing) where S = xor sum of a subset of indexes less than i.

To find the minimum possible value of x[i] ^ S > dp[i – 1][j – 1], we use guassian elimination.

Time complexity is O(N^2B) where B = number of bits = 60.
Code by Um_nik:

typedef long long ll;
 
const ll INF = (ll)3e18;
const int N = 105;
const int K = 60;
int n;
ll dp[N][N];
ll a[K];
 
ll getBiggest(ll x, int k) {
  for(; k >= 0; k--) {
    if (a[k] == -1) continue;
    if (((x >> k) & 1) == 0)
      x ^= a[k];
  }
  return x;
}
 
ll solve(ll x, ll bound) {
  bool gr = false;
  for (int k = K - 1; k >= 0; k--) {
    if (gr) {
      if (a[k] == -1) continue;
      if ((x >> k) & 1)
        x ^= a[k];
      continue;
    }
    if (a[k] == -1) {
      if (((x >> k) & 1) == ((bound >> k) & 1)) continue;
      if ((x >> k) & 1) {
        gr = true;
        continue;
      }
      return INF;
    }
    if ((bound >> k) & 1) {
      if (((x >> k) & 1) == 0)
        x ^= a[k];
      continue;
    }
    if ((x >> k) & 1)
      x ^= a[k];
    if (getBiggest(x, k - 1) < bound) {
      x ^= a[k];
      gr = true;
    }
  }
  if (x < bound) throw;
  return x;
}
 
void addToGauss(ll x) {
  for (int k = K - 1; k >= 0; k--) {
    if (((x >> k) & 1) == 0) continue;
    if (a[k] != -1) {
      x ^= a[k];
      continue;
    }
    a[k] = x;
    return;
  }
}
 
class XorAndLIS {
public:
  int maximalLength(vector<ll> val) {
    n = (int)val.size();
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= n; j++)
        dp[i][j] = INF;
    for (int i = 0; i < K; i++)
      a[i] = -1;
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= i; j++) {
        if (dp[i][j] == INF) break;
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        ll x = solve(val[i], dp[i][j]);
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], x + 1);
      }
      addToGauss(val[i]);
    }
    int ans = n;
    while(dp[n][ans] == INF) ans--;
    return ans;
  }
};