February 5, 2020 Single Round Match 777 Editorials
LimpingDog
We can simulate the process since time is small enough
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
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.
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
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.
#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
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.
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
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.
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
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.
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;
}
}
Harshit Mehta
Sr. Community Evangelist
