April 9, 2020 Single Round Match 730 Editorials
IntervalIntersections
Used as: Division Two – Level One:
| Value | 250 |
| Submission Rate | 235 / 267 (88.01%) |
| Success Rate | 177 / 235 (75.32%) |
| High Score | cnyali_lk for 248.75 points (2 mins 1 secs) |
| Average Score | 202.81 (for 177 correct submissions) |
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:
| Value | 500 |
| Submission Rate | 106 / 267 (39.70%) |
| Success Rate | 87 / 106 (82.08%) |
| High Score | cxhscst2 for 469.89 points (7 mins 17 secs) |
| Average Score | 296.77 (for 87 correct submissions) |
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:
| Value | 1000 |
| Submission Rate | 18 / 267 (6.74%) |
| Success Rate | 3 / 18 (16.67%) |
| High Score | maroon_kuri for 897.68 points (9 mins 49 secs) |
| Average Score | 640.17 (for 3 correct submissions) |
StonesOnATree
Used as: Division One – Level One:
| Value | 250 |
| Submission Rate | 181 / 216 (83.80%) |
| Success Rate | 109 / 181 (60.22%) |
| High Score | Kriii for 236.54 points (6 mins 51 secs) |
| Average Score | 161.34 (for 109 correct submissions) |
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:
| Value | 500 |
| Submission Rate | 63 / 216 (29.17%) |
| Success Rate | 51 / 63 (80.95%) |
| High Score | Kriii for 413.36 points (13 mins 36 secs) |
| Average Score | 283.53 (for 51 correct submissions) |
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:
| Value | 1000 |
| Submission Rate | 24 / 216 (11.11%) |
| Success Rate | 24 / 24 (100.00%) |
| High Score | ksun48 for 975.25 points (4 mins 32 secs) |
| Average Score | 722.85 (for 24 correct submissions) |
The problem is asking for
We calculate
instead and then double the answer.
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
