## February 16, 2020 Single Round Match 778 Editorials

Saturday, Feb 15th, 2020

# The Problems

#### OppositeParity

Used as: Division Two – Level One:

Value250 Submission Rate157 / 186 (84.41%) Success Rate143 / 157 (91.08%) High Scorehp_Vardhanfor 249.36 points (1 mins 26 secs)Average Score209.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:

Value500 Submission Rate120 / 186 (64.52%) Success Rate61 / 120 (50.83%) High ScoreAmAtUrECoDeRfor 452.89 points (9 mins 21 secs)Average Score310.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:

Value1000 Submission Rate17 / 186 (9.14%) Success Rate1 / 17 (5.88%) High Scoreallllekssssafor 618.86 points (25 mins 56 secs)Average Score618.86 (for 1 correct submission)

Value250 Submission Rate119 / 172 (69.19%) Success Rate52 / 119 (43.70%) High Scorecerberus97for 237.04 points (6 mins 42 secs)Average Score163.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:

Value600 Submission Rate67 / 172 (38.95%) Success Rate17 / 67 (25.37%) High Scorenullfor null points (NONE)Average Score323.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:

Value900 Submission Rate19 / 172 (11.05%) Success Rate16 / 19 (84.21%) High ScorePetrfor 726.25 points (14 mins 38 secs)Average Score577.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.poorakhavan*Topcoder Editorialist*

**a.poorakhavan**

Guest Blogger