Single Round Match 778 Editorials

Archive

Match Overview

Single Round Match 778

Saturday, Feb 15th, 2020

Used as: Division Two - Level One:

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:

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:

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:

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:

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