Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
Earlier Dismiss All
You have no more notifications

June 1, 2020 Single Round Match 729 Editorials

BrokenChessboard 

Used as: Division Two – Level One:

Value250
Submission Rate266 / 374 (71.12%)
Success Rate181 / 266 (68.05%)
High ScoreAnti-Mage for 249.93 points (0 mins 29 secs)
Average Score200.52 (for 181 correct submissions)

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:

Value500
Submission Rate151 / 374 (40.37%)
Success Rate38 / 151 (25.17%)
High Scorecwystc for 461.25 points (8 mins 22 secs)
Average Score317.10 (for 38 correct submissions)

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] &amp;&amp; x+1<=x2[j] &amp;&amp; y>=y1[j] &amp;&amp; y+1<=y2[j]) ++s;
        ans=max(ans,s);
      }
    return ans;
  }
};

RareItems 

Used as: Division Two – Level Three:

Value800
Submission Rate30 / 374 (8.02%)
Success Rate21 / 30 (70.00%)
High ScoreMeternal for 712.19 points (10 mins 14 secs)
Average Score518.39 (for 21 correct submissions)

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 &amp; (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:

Value225
Submission Rate214 / 223 (95.96%)
Success Rate196 / 214 (91.59%)
High Score2rf for 224.23 points (1 mins 40 secs)
Average Score198.48 (for 196 correct submissions)

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:

Value450
Submission Rate195 / 223 (87.44%)
Success Rate42 / 195 (21.54%)
High Scorenuip for 412.43 points (8 mins 44 secs)
Average Score280.05 (for 42 correct submissions)

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 &amp;&amp; sy==ty) return 0;
    auto ok=[&amp;](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=[&amp;](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:

Value800
Submission Rate54 / 223 (24.22%)
Success Rate19 / 54 (35.19%)
High ScoreUm_nik for 565.34 points (20 mins 9 secs)
Average Score422.23 (for 19 correct submissions)

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) &amp; 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) &amp; 1)
        x ^= a[k];
      continue;
    }
    if (a[k] == -1) {
      if (((x >> k) &amp; 1) == ((bound >> k) &amp; 1)) continue;
      if ((x >> k) &amp; 1) {
        gr = true;
        continue;
      }
      return INF;
    }
    if ((bound >> k) &amp; 1) {
      if (((x >> k) &amp; 1) == 0)
        x ^= a[k];
      continue;
    }
    if ((x >> k) &amp; 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) &amp; 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;
  }
};

a.poorakhavan

Guest Blogger


categories & Tags


UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds