February 16, 2020 Single Round Match 778 Editorials
Saturday, Feb 15th, 2020
The Problems
OppositeParity
Used as: Division Two – Level One:
Value 250 Submission Rate 157 / 186 (84.41%) Success Rate 143 / 157 (91.08%) High Score hp_Vardhan for 249.36 points (1 mins 26 secs) Average Score 209.72 (for 143 correct submissions)
Read the input and keep two lists, one for even values and one for odd values. Take a for loop again on input. When you see an odd value, if the list of even values is empty, return an empty array. Otherwise, pick an element from the even list and pop it.
The overall complexity is O(n).
Here is the solution in Python:
class OppositeParity:
def __init__(self): pass
def rearrange(self, B):
A = list(B)
n, odd, even = len(A), filter(lambda x : x % 2 == 1, A), filter(lambda x : x % 2 == 0, A)
if len(odd) != len(even): return ()
p, q = 0, 0
for i in range(n):
if A[i] % 2 == 0: A[i], p = odd[p], p + 1
else: A[i], q = even[q], q + 1
return tuple(A)
And here is the C++ code:
struct OppositeParity{
vector<int> rearrange(vector<int> a){
vector<int> v[2];
for(auto x : a)
v[x % 2].push_back(x);
vector<int> ret;
for(auto x : a)
if(v[!(x % 2)].empty())
return {};
else
ret.push_back(v[!(x % 2)].back()), v[!(x % 2)].pop_back();
return ret;
}
};
AlienOccupation
Used as: Division Two – Level Two:
Value 500 Submission Rate 120 / 186 (64.52%) Success Rate 61 / 120 (50.83%) High Score AmAtUrECoDeR for 452.89 points (9 mins 21 secs) Average Score 310.85 (for 61 correct submissions)
Hint: Use BFS.
Let q be an empty queue. Add A to q at first. Now pick elements from q one by one like BFS. Keep a value for each planet, it’s level. Let the picked element be v. For each i (1 <= i <= K), check if u = (X[i] * v + Y[i]) modulo N has seen before or not. If not, set level[u] = level[v] + 1. At last, T is the number of seen planets. U is the maximum level. V is the level with the maximum number of vertices that are at this level.
The overall complexity is O(NK).
Here is the solution in C++:
struct AlienOccupation{
const int inf = 1e9;
vector<int> getInfo(int n, int a, vector<int> x, vector<int> y){
queue<int> q({a});
vector<int> d(n, inf), w(n);
d[a] = 0;
int cnt = 0, mxh = 0, mxoih = 0;
while(!q.empty()){
int v = q.front();
q.pop();
cnt++;
mxh = max(mxh, d[v]);
if(v != a)
mxoih = max(mxoih, ++w[d[v]]);
for(int i = 0; i < x.size(); i++){
int nx = (x[i] * ll(v) + y[i]) % n;
if(d[nx] == inf){
d[nx] = d[v] + 1;
q.push(nx);
}
}
}
return {cnt, mxh, mxoih};
}
};
KRectangleIntersection
Used as: Division Two – Level Three:
Used as: Division One – Level One:
Value 1000 Submission Rate 17 / 186 (9.14%) Success Rate 1 / 17 (5.88%) High Score allllekssssa for 618.86 points (25 mins 56 secs) Average Score 618.86 (for 1 correct submission)
Value 250 Submission Rate 119 / 172 (69.19%) Success Rate 52 / 119 (43.70%) High Score cerberus97 for 237.04 points (6 mins 42 secs) Average Score 163.33 (for 52 correct submissions)
Hint: Solve the problem in 1D.
Consider the problem in 1D: There are several segments, what is the largest segment that is a subsegment of at least k segments?
Sort segments by their start point. Sweep them from left to right. At each point like x, we have several alive (not removed) segments. If they are more than k, sort them by their endings from end to beginning (so if there are two alive segments, one ending in 3 and one in 5, the sorted list will be {5, 3}). Let this list be e[0], e[1], … . The intersection of these alive segments is [x, e[k – 1] ]. It’s enough to manage to keep the list sorted. It’s possible using set in C++, for example.
Now let’s solve the original problem. For each pair of (i, j) 1 <= xl[i] <= xl[j] <= n, consider the rectangles like k such that xl[k] <= xl[i] && xl[j] <= xr[k], the problem is now converted to 1D.
The overall complexity is O(n ^ 3 * log).
Here is the solution in C++:
struct KRectangleIntersection{
ll maxIntersection(vector<int> xl, vector<int> yl, vector<int> xr, vector<int> yr, int k){
int n = xl.size();
ll ans = 0;
for(auto sx : xl)
for(auto ex : xr){
if(ex <= sx)
continue;
vector<pair<int, int> > ava;
for(int i = 0; i < n; i++)
if(xl[i] <= sx && ex <= xr[i])
ava.push_back({yl[i], yr[i]});
sort(ava.begin(), ava.end());
multiset<int> ends;
auto it = ends.begin();
for(auto X : ava){
int x = X.first, y = X.second;
while(ends.size() && *ends.begin() < x)
ends.erase(ends.begin());
ends.insert(y);
if(ends.size() >= k){
if(ends.size() == k)
it = ends.begin();
else if(y >= *it)
it++;
ans = max(ans, ll(ex - sx) * (*it - x));
}
}
}
return ans;
}
};
Here is the solution is Java:
// O(N^3)
public long maxIntersection(int [] xl, int [] yl, int [] xh, int [] yh, int K){
int n = xl.length;
long ret = 0;
int [] compressedYH = new int[n];
int [] revL = new int[n];
int [] revH = new int[n];
TreeSet<Integer> st = new TreeSet();
TreeMap<Integer, Integer> compress = new TreeMap();
for(int i = 0; i < n; i++){
st.add(yh[i]);
}
int cnt = 0;
int [] ulta = new int[n];
for(int x : st){
compress.put(x, cnt);
ulta[cnt] = x;
cnt++;
}
for(int i = 0; i < n; i++){
compressedYH[i] = compress.get(yh[i]);
}
int [] order = new int[n];
ArrayList<Long> al = new ArrayList<>();
for(int i = 0; i < n; i++) al.add( (((long)yl[i])<<30) + i);
Collections.sort(al);
for(int i = 0; i < n; i++){
order[i] = (int)(al.get(i) & ((1 << 30) - 1));
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(xl[i] < xh[j]){
int [] num = new int[cnt];
int curr = 0, val = 0;
int diff = xh[j] - xl[i];
for(int r = 0; r < n; r++){
int k = order[r];
if(xl[k] <= xl[i] && xh[k] >= xh[j]){
int pos = compressedYH[k];
num[pos]++;
if(pos >= curr) val++;
while(curr < cnt && val - num[curr] >= K){
val -= num[curr];
curr++;
}
if(val >= K){
ret = Long.max(ret, diff * 1L * (ulta[curr] - yl[k]));
}
}
}
}
}
}
return ret;
}
// O(N^3 logN)
public long maxIntersectionSlower(int [] xl, int [] yl, int [] xh, int [] yh, int K){
int n = xl.length;
long ret = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(xl[i] < xh[j]){
int diff = xh[j] - xl[i];
ArrayList<Long> al = new ArrayList<>();
for(int k = 0; k < n; k++) if(xl[k] <= xl[i] && xh[k] >= xh[j]){
long L = yl[k];
int R = yh[k];
al.add((L << 30) + R);
}
Collections.sort(al);
TreeSet<Long> curr = new TreeSet<>();
for(int r = 0; r < al.size(); r++){
long val = al.get(r);
long L = (val >>> 30);
long R = (val & ((1 << 30) - 1));
curr.add((R << 30) + r);
if(curr.size() > K) curr.remove(curr.first());
if(r + 1 >= K){
ret = Long.max(ret, Long.max(0L, ((curr.first() >>> 30) - L)) * diff);
}
}
}
}
}
return ret;
}
CollectingCoins
Used as: Division One – Level Two:
Value 600 Submission Rate 67 / 172 (38.95%) Success Rate 17 / 67 (25.37%) High Score null for null points (NONE) Average Score 323.48 (for 17 correct submissions)
Hint: Try to convert the problem to knapsack problem. Consider we have dp[i, i + 2 * k]. Try to find dp values for every integer in [2 * i, 2 * i + 2 * k].
After each power-down (among any k consecutive days there must be at least one day when the machine is powered down and does not produce any coins at all) everything is reset. So we can consider that we start everything from the beginning.
Let several consecutive working days with a power-down day, a block. So for example, in the first sample case, the maximum income of a block with length 2 is 1 (a working day + a power-down day). The income of a block with length 3 is 2. We can’t have a block with a size more than k.
What’s inside a block? For each type of coin, we stuck as much as possible of it into the block. Consider a block with size L and coin type i, we can gain v[i] * ((wd – 1) – (wd – 1) / d[i]) in this block with stocking (wd – 1) – (wd – 1) / d[i] coins of type i.
Increase m by 1. Now we need to put several blocks together and maximize the income. For sure, you’re thinking about knapsack. Yes! it’s a special type of knapsack problem. Let dp[i] be the answer for i days (last day is power-off). The point is, because of the small size of blocks, it’s enough that we have an interval around i / 2 with size k – 1. In other words, consider we know dp values for every integer in [i, i + 2 * k]. We can simply find dp values for every integer in [2 * i, 2 * i + 2 * k].
By doing this, we achieve complexity O(log m * k^2).
Here is a slow solution that uses the key idea:
struct CollectingCoins{
map<int, ll> cache;
vector<ll> income;
ll f(int m, int k){
if(m < income.size())
return income[m];
if(cache.count(m))
return cache[m];
ll &ret = cache[m];
for(int i = min(m - k + 1, m / 2); i < min(m - k + 1, m / 2) + k - 1; i++)
ret = max(ret, f(i, k) + f(m - i, k));
return ret;
}
ll maxValue(int m, int k, vector<int> v, vector<int> d){
cache.clear();
income = {0, 0};
m++;
ll all = 0;
for(int wd = 1; wd < k; wd++){
ll ans = 0;
for(int i = 0; i < v.size(); i++)
ans += v[i] * (wd - wd / d[i]);
income.push_back(ans);
}
for(int i = 0; i < k; i++)
for(int j = 1; j < i; j++)
income[i] = max(income[i], income[j] + income[i - j]);
return f(m, k);
}
};
Here is the full solution:
private void lift(long [] f, int k){
long [] ret = new long[2 * k + 1];
Arrays.fill(ret, Long.MIN_VALUE / 10);
for(int i = 0; i <= 2 * k; i++)
for(int j = 0; j <= 2 * k; j++){
if(f[i] < 0 || f[j] < 0) continue;
//2 * n - k + i + j - k
if(i + j >= k && i + j <= 3 * k){
ret[i + j - k] = Long.max(ret[i + j - k], f[i] + f[j]);
}
}
for(int i = 0; i <= 2*k; i++) f[i] = ret[i];
}
private void shift(long [] f, long[] g, int k){
long val = Long.MIN_VALUE;
for(int i = 0; i < k; i++) val = Long.max(val, f[2 * k - i] + g[i + 1]);
for(int i = 0; i < 2 * k; i++) f[i] = f[i + 1]; f[2 * k] = val;
}
public long maxValue(int m, int k, int[] v, int[] d){
m++;
int n = v.length;
long [] g = new long[k + 1];
long [] f = new long[2 * k + 1];
Arrays.fill(f, Long.MIN_VALUE / 10);
for(int i = 1; i <= k; i++){
for(int j = 0; j < n; j++) g[i] += v[j] * (i - 1 - (i - 1) / d[j]);
}
for(int i = k; i <= 2 * k; i++){
f[i] = g[i - k];
}
for(int i = 30; i >= 0; i--){
lift(f, k);
if((m >>> i) % 2 == 1){
shift(f, g, k);
}
}
return f[k];
}
DominoPlacement
Used as: Division One – Level Three:
Value 900 Submission Rate 19 / 172 (11.05%) Success Rate 16 / 19 (84.21%) High Score Petr for 726.25 points (14 mins 38 secs) Average Score 577.47 (for 16 correct submissions)
Hint: Use dp on bitmasks. Try to solve column by column.
Let’s fix the number of rows is less than the number of columns. So the number of rows is at most 17, The dp state is: consider the matrix from i-th column to the last column.
Let mask be the set of cells in i-th column which are filled by horizontal dominos (1*1 is assumed to be horizontal domino).
Find the number of ways to cover the remaining cells by vertical dominos.
Let nmask be the set of cells covered by horizontal dominos in (i+1)-th column.
Then you should multiply by 2 ^ numberOfSetBits(mask & nmask). Because there are two options for each covered cell, to be continue of the previous covered cell (in i-th column) or to be a new horizontal domino.
The transform function (in the solution) does this efficiently, in O(n * 2^n) instead of O(3^n) or O(4^n).
The overall complexity is O(m * n * 2 ^ n).
Here is the solution:
public DominoPlacement(){
f = new int[305];
f[0] = 1;
for(int n = 1; n <= 300; n++) for(int i = 2; i <= n; i++) f[n] = add(f[n], f[n - i]);
}
static final int MOD = 1000*1000*1000 + 7;
int add(int x, int y){x += y; if(x >= MOD) x -= MOD; return x;}
int mul(int x, int y){return (int) (x * 1L * y % MOD);}
int [] f;
void transform(int [] arr, int k){
if(k == 0) return;
int halfn = 1 << (k - 1);
int [] lft = new int[halfn];
int [] rgt = new int[halfn];
for(int i = 0; i < halfn; i++){
lft[i] = arr[i];
rgt[i] = arr[halfn + i];
}
transform(lft, k - 1);
transform(rgt, k - 1);
for(int i = 0; i < halfn; i++){
arr[i] = add(lft[i], rgt[i]);
arr[i + halfn] = add(arr[i], rgt[i]);
}
}
int get(int mask, int n){
int ret = 1, lst = -1;
for(int i = 0; i < n; i++){
if((mask >>> i & 1) > 0){
ret = mul(ret, f[i - lst - 1]);
lst = i;
}
}
ret = mul(ret, f[n - 1 - lst]);
return ret;
}
public int countWays(String [] T){
int n = T.length;
int m = T[0].length();
int [] masks = new int[Integer.max(n, m)];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(T[i].charAt(j) == '#'){
if(n > m) masks[i] |= 1 << j;
else masks[j] |= 1 << i;;
}
}
}
if(n > m){
n ^= m; m ^= n; n ^= m;
}
int [] curr = new int[1 << n];
curr[0] = 1;
for(int i = 0; i < m; i++){
transform(curr, n);
for(int mask = 0; mask < (1 << n); mask++){
if((mask & masks[i]) != 0){
curr[mask] = 0;
}
else curr[mask] = mul(curr[mask], get(mask ^ masks[i], n));
}
}
long ret = 0;
for(int x : curr) ret += x;
return (int) (ret % MOD);
}
You can also check https://www.overleaf.com/8336967563zvfyczpmmsrh for another editorial wrote by the setter.
By a.poorakhavanTopcoder Editorialist
Guest Blogger
