March 20, 2020 Single Round Match 781 Editorials
EasyPartition
Used as: Division Two – Level One:
Value | 250 |
Submission Rate | 106 / 144 (73.61%) |
Success Rate | 82 / 106 (77.36%) |
High Score | z3r0dmg for 249.07 points (1 mins 44 secs) |
Average Score | 176.85 (for 82 correct submissions) |
Find and implement a pattern. Many different patterns work. For example:
1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
…
Sum of odd numbers less than 2*k is k^2.
So if we choose odd numbers less than 2*(2*N), the sum will be (2*N)^2.
def getPartition(self, N):
return "10" * 2 * N + "0" * 4 * N
Another solution is to take numbers 2N+1, …, 2N+N, and also 2N-1, …, 2N-N. The numbers 2N+i and 2N-i have sum 4N, and we have N such pairs.
NicePartition
Used as: Division Two – Level Two:
Value | 500 |
Submission Rate | 93 / 144 (64.58%) |
Success Rate | 83 / 93 (89.25%) |
High Score | hp_Vardhan for 495.80 points (2 mins 37 secs) |
Average Score | 386.70 (for 83 correct submissions) |
Sort H.
Imagine that we are constructing the buildings from the tallest to the smallest. Where can we build the tallest one without violating the conditions? At the end of A, or at the beginning of B. Where can we build the second tallest? Again, at the last free position in A, or the first free position in B. And so on.
Pause the process after constructing the N tallest buildings. Regardless of how many buildings we put into A and how many into B, we now have exactly one building in each pair of buildings. Thus, regardless of how we partition the buildings, each pair of buildings will always contain one of the N tallest and one of the N shortest buildings. So, in each pair we will take the height of a tall building and subtract the height of a short building. And therefore the sum of all instabilities will be always simply the sum of the N tallest buildings, minus the sum of the N shortest buildings.
It turns out that the answer does not depend on the partitioning.
int minCost(vector<int> H){
sort(H.begin(), H.end());
int ans = 0;
for(int i = 0; i < H.size() / 2; i++)
ans += H[H.size() - i - 1] - H[i];
return ans;
}
Python code:
def minCost(self, H):
H = list(H)
H.sort()
N = len(H) // 2
return sum( H[N:] ) - sum( H[:N] )
PolygonalRegions
Used as: Division Two – Level Three:
Value | 1000 |
Submission Rate | 8 / 144 (5.56%) |
Success Rate | 2 / 8 (25.00%) |
High Score | yhchang3 for 799.21 points (15 mins 2 secs) |
Average Score | 692.00 (for 2 correct submissions) |
For a given, fixed state of the polygon, which it’s determined that each vertex is good or not, the calculation of the number of regions is simple. Imagine that we draw the diagonals one at a time. Each diagonal will divide some regions into two. The number of regions it divides is 1 + the number of other diagonals it intersects. Thus, the final answer is 1 (the original region) + the number of diagonals + the number of intersections of two diagonals.
The number of regions can also be derived from https://en.wikipedia.org/wiki/Planar_graph#Euler%27s_formula: the original vertices and the intersections are the nodes of the graph, line segments between them are the edges, and regions + the infinite part of the plane are the faces of the graph.
By linearity of expectation, the expected number of diagonals is the sum of probabilities that a diagonal is present in the drawing, and the expected number of intersections is the sum of probabilities that each pair of diagonals appears together. If we denote the probability of point i being good P[i], the expected number of diagonals is the sum of P[i]*P[j] over all diagonals, and the expected number of intersections is the sum of P[i]*P[j]*P[k]*P[l] over all pairs of diagonals (i,j) and (k,l) that intersect. This gives us an O(n^4) solution:
const long long MOD = 1000000007;
long long modexp(long long a, long long b) {
if (b == 0) return 1;
long long t = modexp(a,b/2);
t *= t;
t %= MOD;
if (b % 2) {
t *= a;
t %= MOD;
}
return t;
}
struct PolygonalRegions {
int expectedRegions(int N) {
long long N2 = (N*N) % MOD;
long long denominator = (N2*N2) % MOD;
long long numerator = denominator; // the one initial region
for (int i=0; i<N; ++i) for (int j=i+2; j<N; ++j) if (!(i == 0 && j == N-1)) {
// diagonal i-j adds one region if present
long long pij = (1LL * (i+1) * (j+1)) % MOD;
numerator += pij * N2;
numerator %= MOD;
// each present k-l that crosses i-j adds one region
for (int k=i+1; k<j; ++k) for (int l=j+1; l<N; ++l) {
long long pkl = (1LL * (k+1) * (l+1)) % MOD;
numerator += pij * pkl;
numerator %= MOD;
}
}
long long inverse_denominator = modexp(denominator, MOD-2);
return (numerator * inverse_denominator) % MOD;
}
};
The solution can be further improved by counting more cleverly, all the way to an O(n) solution:
long mod = 1000000007;
long power(long base, long exponent) {
long ret = 1 % mod;
base %= mod;
while(exponent > 0) {
if(exponent % 2 == 1) {
ret = (ret * base) % mod;
}
base = (base * base) % mod;
exponent >>= 1;
}
return ret;
}
long inv(long val) {
return power(val, mod - 2);
}
public int expectedRegions(int N) {
long[] DP = new long[N + 1];
long invN = inv(N);
for(int i = 1; i <= N; i++) {
DP[i] = (i * invN) % mod;
}
long two_together = 0, four_together = 0;
for(int i = 1; i <= 3; i++) {
long[] prev = new long[N + 1];
for(int j = 1; j <= N; j++) {
prev[j] = DP[j];
}
long sum_so_far = 0;
DP[0] = 0;
for(int v = 1; v <= N; v++) {
long here = (v * invN) % mod;
DP[v] = (here * sum_so_far) % mod;
sum_so_far = (sum_so_far + prev[v]) % mod;
}
if(i == 1) {
for(int j = 1; j <= N; j++) {
two_together += DP[j];
two_together %= mod;
}
}
}
for(int j = 1; j <= N; j++) {
four_together += DP[j];
four_together %= mod;
}
long answer = (four_together + two_together) % mod;
long adjacent = 0;
for(long i = 1; i <= N; i++) {
adjacent = (adjacent + (i * (i % N + 1))) % mod;
}
adjacent = (adjacent * ((invN * invN) % mod)) % mod;
answer = (answer - adjacent + 1 + mod) % mod;
return ((int)answer) % (int)mod;
}
EpicPartition
Used as: Division One – Level One:
Value | 250 |
Submission Rate | 76 / 135 (56.30%) |
Success Rate | 45 / 76 (59.21%) |
High Score | bqi343 for 213.26 points (12 mins 14 secs) |
Average Score | 134.15 (for 45 correct submissions) |
There are many valid ways to partition the given set in the given way. You can either find and implement a specific pattern, implement a backtracking solution, and if you’re feeling a bit adventurous, you can even try a random walk: split the set into subsets of desired sizes and swap items around until the sums are correct.
Notably, it is obvious that the answer only exists for N=4*k, and thus we only need to find only 25 answers in any way we can. The submitted solution can then contain those 25 cases hard-wired.
One possible pattern:
int K = N / 4;
char[] filled = new char[6 * N];
for(int i = 0; i < 24 * K; i++) {
filled[i] = 'a';
}
filled[-1 + 24 * K] = 'c';
filled[-1 + 18 * K] = 'c';
for(int i = 1; i <= 4 * K - 1; i++) {
filled[-1 + 18 * K - i] = 'c';
filled[-1 + 18 * K + i] = 'c';
}
filled[-1 + 9 * K] = 'b';
filled[-1 + 12 * K] = 'b';
for(int i = 1; i <= 4 * K - 1; i++) {
if(i == 3 * K) {
filled[-1 + 5 * K] = 'b';
filled[-1 + 13 * K] = 'b';
} else {
filled[-1 + 9 * K + i] = 'b';
filled[-1 + 9 * K - i] = 'b';
}
}
The random walk solution:
from random import randint
def random_split(seq, target_size, target_sum):
part1, part2 = list(seq[:target_size]), list(seq[target_size:])
steps = 0
while True:
if sum(part1) == target_sum: break
while True:
steps += 1
if steps == 10000: return None
i = randint(0, len(part1)-1)
j = randint(0, len(part2)-1)
if (part1[i] < part2[j]) == (sum(part1) < target_sum):
break
part1[i], part2[j] = part2[j], part1[i]
return part1, part2
class EpicPartition:
def createPartition(self, N):
if N % 4 != 0: return ""
while True:
try:
S = range(1,6*N+1)
C, AB = random_split(S,2*N,sum(S)//2)
A, B = random_split(AB,2*N,sum(AB)//2)
break
except:
continue
answer = [ None for _ in range(6*N+1) ]
for a in A: answer[a] = 'a'
for b in B: answer[b] = 'b'
for c in C: answer[c] = 'c'
return ''.join( answer[1:] )
RandomPartition
Used as: Division One – Level Two:
Value | 450 |
Submission Rate | 35 / 135 (25.93%) |
Success Rate | 30 / 35 (85.71%) |
High Score | neal_wu for 427.80 points (6 mins 32 secs) |
Average Score | 327.99 (for 30 correct submissions) |
See the editorial to NicePartition. The randomness is just a ruse, the sum of all instabilities, and therefore their average is always the same. We just need to calculate it and return it.
def expectedSum(self, nums, N, M, B1, B2):
H = list(nums)
while len(H) < 2*N:
H.append( (H[-1]*B1 + H[-2]*B2) % M )
H.sort()
num = sum( H[N:] ) - sum( H[:N] )
den = N
invden = 1
while (invden * den) % 786433 != 1:
invden += 1
return (num * invden) % 786433
RoseDressGame
Used as: Division One – Level Three:
Value | 1000 |
Submission Rate | 12 / 135 (8.89%) |
Success Rate | 7 / 12 (58.33%) |
High Score | Egor for 688.80 points (21 mins 13 secs) |
Average Score | 560.39 (for 7 correct submissions) |
The game can be called a “misère annihilation NIM” (“misère” describes the reversed winning condition, annihilation describes what happens to piles of equal size). In normal NIM it is obvious that annihilation doesn’t change the outcome, but, perhaps surprisingly, it does change the outcome under misère play: misère NIM without annihilation has a different set of losing positions. To solve the problem you need to find the pattern of losing positions (and possibly prove that you found them correctly, although in a contest a test against your brute-force solution is much more practical). Here, it can be shown that the losing positions can be described as follows:
- Pile of size 0 can be ignored, so below we only consider positions with no such pile.
- Call a position paired if the pile sizes can be divided into pairs of the form (2k, 2k+1).
- Call a position generalized paired if it’s a paired position + maybe a pile of size 1.
- All generalized paired positions such that xor of pile sizes is 1 are losing positions.
- All positions that have xor = 0 and are not generalized paired positions are losing positions.
- All other positions are winning.
The proof is essentially just casework: We have to show that all moves from a losing position lead to a winning position, and that each winning position is either terminal or it has a move to a losing position.
public String getWinner(int[] roses) {
int x = 0;
for (int r : roses) x ^= r;
if (x > 1) return "Coco";
int bigc = 0;
for (int r : roses) if (r > 1) ++bigc;
int[] big = new int[bigc];
int hlp = 0;
for (int r : roses) if (r > 1) big[hlp++] = r;
Arrays.sort(big);
boolean all_pairs;
if (bigc % 2 == 0) {
all_pairs = true;
for (int i=0; i<bigc/2; ++i) if (big[2*i] + 1 != big[2*i+1]) all_pairs = false;
for (int i=0; i<bigc/2; ++i) if (big[2*i] % 2 == 1) all_pairs = false;
} else {
all_pairs = false;
}
if (x == 1 && all_pairs) return "Yves";
if (x == 0 && !all_pairs) return "Yves";
return "Coco";
}
misof