Single Round Match 777 Editorials

LimpingDog

Problem Link
We can simulate the process since time is small enough

1
2
3
4
5
6
7
8
9
10
11
12
class LimpingDog():
  def countSteps(self, time):
  res = 0
while time 0:
  time -= 1
if res % 4 == 2:
  time -= 1
if time = 0:
  res += 1
if res % 47 == 0:
  time -= 42
return res

StringTransformationEasy

Problem Link
Divide the string into blocks of equal letters. You can never erase a block completely, but you can always erase it down to the last one or two characters (based on parity) by using one character from an adjacent block and three from your block.

Special case: if all letters are the same, you cannot erase anything.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def rle(S):
  answer = [1]
for n in range(1, len(S)):
  if S[n] == S[n - 1]:
  answer[-1] += 1
else:
  answer.append(1)
return answer

class StringTransformationEasy:
  def getResult(self, S, T):
  if len(T) len(S): return "NO"
if T[0] != S[0]: return "NO"
RS, RT = rle(S), rle(T)
if len(RS) != len(RT): return "NO"
if len(RS) == 1:
  return "YES"
if RS == RT
else "NO"
for s, t in zip(RS, RT):
  if t s: return "NO"
if t % 2 != s % 2: return "NO"
return "YES"

BlackAndWhiteBallsEasy

Problem Link
First, we can expand the sequence to sum(balls) length. Now, we can do a dp solution. dp[i] is the number ways to split the first i balls. We can iterate through j, count the number of white balls or black balls between balls i+1 and j, and add dp[i] to dp[j] if it satisfies the conditions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h

using namespace std;

const int MOD = 1000000007;

struct BlackAndWhiteBallsEasy {
  int getNumber(vector < int _balls, int W, int B) {
    vector < int balls;
    for (int n = 0; n < int(_balls.size()); ++n)
      for (int i = 0; i < _balls[n]; ++i) balls.push_back(n % 2);
    int N = balls.size();

    vector < int psum(1, 0);
    for (int b: balls) psum.push_back(psum.back() + b);

    vector < int dp(N + 1);
    dp[0] = 1;
    for (int n = 1; n <= N; ++n) {
      for (int last = 1; last <= n; ++last) {
        int countb = psum[n] - psum[n - last];
        int countw = last - countb;
        if (countw == W) dp[n] = (dp[n] + dp[n - last]) % MOD;
        if (countb == B) dp[n] = (dp[n] + dp[n - last]) % MOD;
      }
    }
    return dp[N];
  }
};

PreviousOccurence

Problem Link
This problem can be solved by simulation. When defaultValue = 1, the sequence is just 0, 1, 1, 1, …, so the answer doesn’t exist unless query is 0 or 1. Otherwise, a simulation works. Since there’s only a limited number of defaultValues, you can try them all and see that they will contain all query values if you go up to 10^7 or so. We can efficiently simulate the process by keeping a map from seen integers to their last occurence, allowing us to generate each element in constant time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;

public class PreviousOccurrence {
  public int findValue(int defaultValue, int query) {
    HashMap < Integer, Integer last = new HashMap < Integer, Integer();
    if (query == 0) {
      return 0;
    }
    int prev = 0;
    for (int i = 1; i < 10000000; i++) {
      int value = 0;
      if (last.containsKey(prev)) {
        value = i - 1 - last.get(prev);
      } else {
        value = defaultValue;
      }
      if (value == query) {
        return i;
      }
      last.put(prev, i - 1);
      prev = value;
    }
    return -1;
  }

}

StringTransformation

Problem Link
Let’s get the run length encoding of both sequences, and call each of these parts a block. A block has a color and number. If there is only one block in T, then T and S must be the same.

It helps to look at things backwards as adding characters from T to S. Each block in T must correspond to a compatible block in S, where a block in T is “compatible” with a block in S if it has the same color, it has the same parity, and the number is equal or less.

If we look at the matched blocks of S, we must somehow generate everything else, and this is several independent problems between matched blocks. We can figure out when we can generate everything in between two already matched blocks in S. We can solve this with a little case work, and find out this is possible if the two blocks are already adjacent (nothing to generate), or all blocks in between have even size and the colors, including endpoints, don’t alternate between only two colors (this can be proven with induction).

This leads to a dp solution, dp[i][j] - true iff we can match first i blocks in T with first j blocks in S. For a fixed i, we sweep from lower j to higher j and keep track of some information to figure out if all previous blocks between the last possible matched position are even size and don’t alternate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class StringTransformation {
  String x = "RGB";
  static class Block {
    int c;
    int n;

    public Block(int c, int n) {
      this.c = c;
      this.n = n;
    }
    public boolean inside(Block other) {
      return other.c == this.c && other.n = this.n && (other.n % 2) == (this.n % 2);
    }
  }
  public List < Block chunk(String s) {
    List < Block ret = new ArrayList < ();
    char last = s.charAt(0);
    int count = 0;
    for (char c: s.toCharArray()) {
      if (c == last) count++;
      else {
        ret.add(new Block(x.indexOf(last), count));
        last = c;
        count = 1;
      }
    }
    ret.add(new Block(x.indexOf(last), count));
    return ret;
  }

  public String getResult(String s, String t) {
    return _getResult(s, t) ? "YES" : "NO";
  }
  public boolean _getResult(String s, String t) {
    List < Block a1 = chunk(s), a2 = chunk(t);
    if (a2.size() == 1) {
      return a1.size() == 1 && a1.get(0)
        .c == a2.get(0)
        .c && a1.get(0)
        .n == a2.get(0)
        .n;
    }
    boolean[] dp = new boolean[a1.size()];
    dp[0] = a2.get(0)
      .inside(a1.get(0));
    for (int i = 1; i < a2.size(); i++) {
      Block b2 = a2.get(i);
      boolean[] ndp = new boolean[a1.size()];
      int msk = 0;
      boolean first = false;
      for (int j = 0; j < a1.size(); j++) {
        Block b1 = a1.get(j);
        int c = b1.c;

        if (b2.inside(b1)) {
          if (j 0 && dp[j - 1]) ndp[j] = true;
          if (first) msk |= 1 << c;
          ndp[j] |= msk == 7;
        }

        if (b1.n % 2 == 1) {
          first = false;
          msk = 0;
        }

        first |= dp[j];
        if (first) msk |= 1 << c;
      }
      dp = ndp;
    }
    return dp[a1.size() - 1];
  }
}

BlackAndWhiteBalls

Problem Link
Let’s say we have two types of segments - type 0 (where number of zeros is X), and type 1 (where the number of ones is Y). Let’s do a bit of a different DP, dp[b][t], which means we’ve covered the first b blocks of balls with segments, and the type of the last segment that the b-th block has included is t. Note that the b-th block might not be completely covered yet. The DP transition will iterate over k, and cover the next k blocks with segments of type t^1. Basically, we are doing DP, but in one turn covering a contiguous range of segments of the same type.

We’ll also assume that if the color of the b-th block is t, then it was decided before how many balls of that block ended up in previous segments, and how many are left for the next one. It’s OK for us to assume this since we’re placing segments of type t^1 and balls of type t are irrelevant.

If the color of the b-th block is not equal to t, then we assume it was NOT yet decided how many balls of that segment ended up in previous segments, and we’ll decide it now during the current dp transition.

Based on that, we can work out the dp transitions. A hard case is when while placing a range of segments of type t^1 and the b-th block and (b+k)-th block are color t^1, we need to decide how many of the balls of those two ‘separator’ blocks end up in segments of type t, and this can affect how we split blocks of color t in the interior. This is doable since there are at most n interesting modulos to consider, and the formulas can get a bit messy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
import java.util.Arrays;
import java.util.Collection;
import java.util.ArrayList;
import java.util.List;
import java.util.*;

public class BlackAndWhiteBalls {
  class PairII {
    public int first;
    public int second;

    public PairII(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }

  class Ranges {
    public long first;
    public ArrayList < PairII second;

    public Ranges(long first, ArrayList < PairII second) {
      this.first = first;
      this.second = second;
    }
  }

  class PairPI implements Comparable < PairPI {
    public PairII first;
    public int second;

    public PairPI(PairII first, int second) {
      this.first = first;
      this.second = second;
    }

    public int compareTo(PairPI c) {
      if (first.first < c.first.first) return -1;
      if (first.first c.first.first) return 1;
      if (first.second < c.first.second) return -1;
      if (first.second c.first.second) return 1;
      if (second < c.second) return -1;
      if (second c.second) return 1;
      return 0;
    }
  }

  class PairIP implements Comparable < PairIP {
    public int first;
    public PairII second;

    public PairIP(int first, PairII second) {
      this.first = first;
      this.second = second;
    }

    public int compareTo(PairIP c) {
      if (first < c.first) return -1;
      if (first c.first) return 1;
      if (second.first < c.second.first) return -1;
      if (second.first c.second.first) return 1;
      if (second.second < c.second.second) return -1;
      if (second.second c.second.second) return 1;
      return 0;
    }
  }

  final int MOD = 1000000007;
  final int INF = 1000000000;
  final int MAX = 256;
  int A[];
  int C[];
  long R[][];
  long W[][];
  int c[];
  int n;
  int it;

  long get(long x, int t) {
    if (x <= 0) return 0;
    return x / c[t];
  }

  long get(long l, long r, int t) {
    if (l r) return 0;
    return get(r, t) - get(l - 1, t);
  }

  long getCoefLeft(int l, int r, int t) {
    long res = 1, sum = 0;
    for (int i = l; i <= r; ++i) {
      if (C[i] == t) {
        sum += A[i];
      } else {
        if ((sum % c[t] == 0) && sum 0) {
          res = res * (A[i] + 1) % MOD;
        }
      }
    }

    return res;
  }

  long getCoefRight(int l, int r, int t) {
    long res = 1, sum = 0;
    for (int i = r; i = l; --i) {
      if (C[i] == t) {
        sum += A[i];
      } else {
        if ((sum % c[t] == 0) && sum 0) {
          res = res * (A[i] + 1) % MOD;
        }
      }
    }

    return res;
  }

  Ranges getRanges(long l, long r, long m) {
    long ta = 0;
    ArrayList < PairII Q = new ArrayList < PairII();
    for (long i = l; i <= r;) {
      if (i % m == 0) {
        long c = (r - i) / m;
        i += c * m;
        ta += c;
      }

      long t = (i / m + 1) * m;
      long p = Math.min(r, t - 1);
      Q.add(new PairII((int)(i % m), (int)(p % m)));
      i = p + 1;
    }

    return new Ranges(ta, Q);
  }
  long countTot(int l, int r, int t, long s) {
    Ranges resA = getRanges(1, A[l] - 1, c[t]);
    int tl = (int)((-(A[r] % c[t]) + c[t] - s % c[t] + c[t]) % c[t]);
    Ranges resB = getRanges(tl, (long) tl + A[r] - 1, c[t]);
    long ta = resA.first;
    long tb = resB.first;

    ArrayList < PairIP Q = new ArrayList < PairIP();

    for (int i = 0; i < resA.second.size(); ++i) {
      Q.add(new PairIP(resA.second.get(i)
        .first, new PairII(0, 0)));
      Q.add(new PairIP(resA.second.get(i)
        .second + 1, new PairII(0, 1)));
    }

    for (int i = 0; i < resB.second.size(); ++i) {
      Q.add(new PairIP(resB.second.get(i)
        .first, new PairII(1, 0)));
      Q.add(new PairIP(resB.second.get(i)
        .second + 1, new PairII(1, 1)));
    }

    Q.add(new PairIP(0, new PairII(2, 2)));
    Q.add(new PairIP(c[t], new PairII(2, 2)));

    Collections.sort(Q);

    long curA = 0, curB = 0;
    long res = 0;

    for (int i = 0; i < Q.size() - 1; ++i) {
      ++it;
      if (Q.get(i)
        .second.first == 0) {
        if (Q.get(i)
          .second.second == 0) ++curA;
        else --curA;
      } else if (Q.get(i)
        .second.first == 1) {
        if (Q.get(i)
          .second.second == 0) ++curB;
        else --curB;
      }

      if (Q.get(i)
        .first != Q.get(i + 1)
        .first) {
        int cnt = (Q.get(i + 1)
          .first - Q.get(i)
          .first) % MOD;
        res += (curA + ta) * (curB + tb) % MOD * cnt % MOD;
        res %= MOD;
      }
    }

    return res;
  }

  long getCoefBoth(int l, int r, int t) {
    if (l == r) {
      long k = A[l] / c[t];
      long res = A[l] * k % MOD;
      long d = k * (k + 1) / 2 % MOD;
      d = d * c[t] % MOD;
      res = (res - d + MOD) % MOD;

      return res;
    } else {
      long s = 0;
      for (int k = l + 1; k < r; ++k)
        if (C[k] == t) s += A[k];

      long cur = 0;
      ArrayList < PairPI Q = new ArrayList < PairPI();
      for (int k = l + 1; k < r; ++k) {
        ++it;
        if (C[k] == t) cur += A[k];
        else {
          int a = (int)((c[t] - (cur % c[t]) + c[t]) % c[t]);
          int b = (int)((c[t] - ((s - cur) % c[t]) + c[t]) % c[t]);
          Q.add(new PairPI(new PairII(a, b), A[k] + 1));
        }
      }

      long tot = countTot(l, r, t, s);

      Collections.sort(Q);

      int pos = 0;
      long res = 0;
      while (pos < Q.size()) {
        int add = 0;
        long d = 1;
        while (pos + add < Q.size() && Q.get(pos + add)
          .first.first == Q.get(pos)
          .first.first && Q.get(pos + add)
          .first.second == Q.get(pos)
          .first.second) {
          d = d * Q.get(pos + add)
            .second % MOD;
          ++add;
        }

        long cl = (A[l] - 1 - Q.get(pos)
          .first.first) / c[t];
        if (Q.get(pos)
          .first.first 0 && A[l] - 1 = Q.get(pos)
          .first.first) ++cl;

        long cr = (A[r] - Q.get(pos)
          .first.second) / c[t];
        if (Q.get(pos)
          .first.second 0 && A[r] = Q.get(pos)
          .first.second) ++cr;

        tot = (tot - cl * cr % MOD + MOD) % MOD;

        res += cl * cr % MOD * d % MOD;
        res %= MOD;

        pos += add;
      }

      res = (res + tot) % MOD;

      return res;
    }
  }
  public int getNumber(int[] balls, int white, int black) {
    n = balls.length;
    A = new int[n];
    C = new int[n];
    for (int i = 0; i < n; ++i) {
      A[i] = balls[i];
      C[i] = i % 2;
    }

    c = new int[2];
    c[0] = white;
    c[1] = black;

    R = new long[MAX][2];
    W = new long[MAX][2];

    for (int i = n - 1; i = 0; --i) {
      for (int j = 0; j < 2; ++j) {
        long s[] = new long[2];
        for (int k = i; k < n; ++k) {
          s[C[k]] += A[k];

          if (C[k] == j) {
            W[i][j] += getCoefBoth(i, k, j) * R[k + 1][j ^ 1] % MOD;
            W[i][j] %= MOD;

            if (k == n - 1) {
              W[i][j] += get(s[j] - A[i] + 1, s[j] - 1, j) * getCoefRight(i, k, j) % MOD;
              W[i][j] %= MOD;
            }
          } else {
            W[i][j] += get(s[j] - A[i] + 1, s[j] - 1, j) * getCoefRight(i, k - 1, j) % MOD * W[k][j ^ 1] % MOD;
            W[i][j] %= MOD;

            if (k == n - 1) {
              W[i][j] += get(s[j] - A[i] + 1, s[j] - 1, j) * getCoefRight(i, k - 1, j) % MOD;
              W[i][j] %= MOD;
            } else {
              W[i][j] += get(s[j] - A[i] + 1, s[j] - 1, j) * getCoefRight(i, k - 1, j) % MOD * R[k + 1][j ^ 1] % MOD;
              W[i][j] %= MOD;
            }
          }
        }
      }

      for (int j = 0; j < 2; ++j) {
        long s[] = new long[2];
        for (int k = i; k < n; ++k) {
          s[C[k]] += A[k];

          if (C[k] == j) {
            R[i][j] += get(s[j] - A[k] + 1, s[j], j) * getCoefLeft(i, k, j) % MOD * R[k + 1][j ^ 1] % MOD;
            R[i][j] %= MOD;

            if (k == n - 1 && s[j] % c[j] == 0) {
              R[i][j] += getCoefLeft(i, k, j);
              R[i][j] %= MOD;
            }
          } else {
            if (s[j] % c[j] == 0 && s[j] 0) {
              R[i][j] += getCoefLeft(i, k - 1, j) * W[k][j ^ 1] % MOD;
              R[i][j] %= MOD;

              if (k == n - 1) {
                R[i][j] += getCoefLeft(i, k - 1, j);
                R[i][j] %= MOD;
              } else {
                R[i][j] += getCoefLeft(i, k - 1, j) * R[k + 1][j ^ 1] % MOD;
                R[i][j] %= MOD;
              }
            }
          }
        }
      }
    }

    int res = (int)((R[0][0] + R[0][1]) % MOD);
    return res;
  }
}