# April 9, 2020 Single Round Match 730 Editorials

#### IntervalIntersections

Used as: Division Two – Level One:

There are several cases to consider. We need to check if segments intersect or not.

• y1 < x2: the answer is x2 – x1.
• y2 < x1: the answer is x1 – y2.
• Otherwise, segments intersect and the answer is zero.

Code by bohuss:

int ans = 0;
if(y1<x2)
return x2 - y1;
if(y2<x1)
return x1 - y2;
return 0;


#### ExpectedMinimumPowerDiv2

Used as: Division Two – Level Two:

For each s, let’s count in how many ways s is the minimum element. We must choose s and also x – 1 elements greater than x. So we want to calculate

We can calculate the n choose r for each i. This leads to an O(n^2) solution. Note that n choose r never overflows from the 64-bit integer (e. g. long long in C++) when n, r are in the range [1, 50].Another solution is to calculate n choose r for all of the possible values in the range [1, 50] (preprocessing). Like the code below by cxhscst2:

const int M = 60;
long long c[M][M];
double findExp(int n, int x) {
memset(c, 0, sizeof c); // fill all of the array with 0
c[0][0] = 1;
for(int i = 0; i <= 50; i++){
c[i][0];
for(int j = 1; j <= i; j++)
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
double ans = 0;
for(int i = 1; i <= n - x + 1; i++){
int now = n - i;
double ss = 1;
for(int j = 1; j <= i; j++)
ss = ss * 2;
ans = ans + ss / (double) c[n][x] * c[now][x - 1];
}
return ans;
}


Another solution written in java:

  public double findExp(int n, int x) {
long total = 0;
long p = 0;
for (int min = 1; min <= n - x + 1; min++) {
long sets = comb(n - min, x - 1);
total += sets;
long bit = (1L << min);
p += bit * sets;
}
return p / (double) total;
}

private long comb(long n, long k) {
if (k == 0) return 1L;
return (n * comb(n - 1, k - 1)) / k;
}


#### StonesOnATreeDiv2

Used as: Division Two – Level Three:

#### StonesOnATree

Used as: Division One – Level One:

The main goal of the game is to put a stone on the root. What is the last step before we can do it? Putting a stone on each of the children of the root. Because w[] is increasing, we will put a stone on each of the children one by one. i. e. we find a permutation of children, then we will manage to put a stone on each of them one by one.

dp[v] = The smallest W for which there is a way to put a stone on v such that during the game the total weight of nodes with stones never exceeds W. Note that we only consider subtree of v.

For example, consider the root has only two children: c, d. If we choose to put a stone on c then d, the answer is max(dp, w + dp[d]).

If we choose permutation p, then dp[0] = max(dp[p[0]], w[p[0]] + dp[p[1]], w[p[0]] + w[p[1]] + dp[p[2]], …).

We should find a permutation that leads to the minimum answer. Consider two children c, d. We put c before d in the permutation if and only if w + dp[d] < w[d] + dp.

So we sort the children with the comparison function above and calculate the dp.C++ code by Kriii:

int minStones(vector<int> p, vector<int> w) {
int n = p.size() + 1;
vector<vector<int> > g(n);
for (int i = 1; i < n; i++) g[p[i - 1]].push_back(i);

vector<int> a(n);
for (int i = n - 1; i >= 0; i--) {
vector<pair<int, int> > u;
for (auto &x : g[i]) u.push_back({ w[x],a[x] });
sort(u.begin(), u.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
return max(a.second, a.first + b.second) < max(b.second,b.first+a.second);
});

int r = 0, s = 0;
for (auto &p : u) {
r = max(r, s + p.second);
s += p.first;
}
a[i] = max(r, s + w[i]);
}
return a[0];
}


#### Subgraphs

Used as: Division One – Level Two:

Here is the graph:

• There is no edge between vertices in the range [1, k].
• All of the vertices in the range [k+1, 2k] are pairwise connected.
• Vertex i (i <= k) is connected to k + 1, k + 2, … k + i.

Now to select a subgraph with x edges and k vertices, let p be the greatest integer such that p * (p – 1) / 2 <= x. We select the vertices in the ranges [2k – p + 1, 2k], [1, k – p – 1], and the vertex k – p + x – p * (p – 1) / 2.

vector<string> findGroups(int k) {
int f[50][50] = { 0, };
vector<string> choose;
choose.push_back("YN");
for (int j = 2; j <= k; j++) {
vector<string> nchoose;
for (auto &s : choose) nchoose.push_back(s + "NY");
for (int i = 0; i < 2 * j - 2; i++) f[i][2 * j - 2] = f[2 * j - 2][i] = 1;
int u = j * (j - 1) / 2;
for (int i = choose.size(); i <= u; i++) {
nchoose.push_back(choose[i - (j - 1)] + "YN");
}
choose = nchoose;
}
vector<string> ans;

int n = 2 * k;
for (int i = 0; i < n; i++) {
string s;
for (int j = 0; j < n; j++) {
if (f[i][j]) s += '1';
else s += '0';
}
ans.push_back(s);
}

ans.insert(ans.end(),choose.begin(), choose.end());
return ans;
}


#### ExpectedMinimumPower

Used as: Division One – Level Three:

The problem is asking for

We calculate

Consider the following problem: “We have n people. Choose one of them as the leader, then choose x – 1 people with greater index as deputy and choose a subset (possibly empty) of people with less index (than the leader) as an employee. How many ways are there?

You can deduce that answer to this problem is

Let’s calculate the answer in another way. For each of the ways for the above problem, the last x – 1 chosen persons are deputy. The x-th one is the leader and others are employees.

So, for each subset of n people having at least x people, it is also an answer to the above problem. So,

typedef long long LL;
#define MOD 1000000007
LL powmod(LL a, LL n){
if(n == 0) return 1;
if(n % 2) return (a*powmod(a,n-1)) % MOD;
LL c = powmod(a, n/2);
return (c*c) % MOD;
}
LL inv(LL a){
return powmod(a, MOD-2);
}

// call init();
class ExpectedMinimumPower{
public:
LL findExp(LL n, LL x){
LL ans = 0;
LL cur = 1;
for(LL a = 0; a < x; a++){
ans += cur;
cur = (cur * (n - a)) % MOD;
cur = (cur * inv(a + 1)) % MOD;
ans %= MOD;
}
ans = powmod(2, n) - ans;
ans %= MOD;
ans *= 2;
ans %= MOD;
while(ans < 0) ans += MOD;
return ans;
}
};


Guest Blogger

categories & Tags

Close