Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
TOSCA Editor - Web Application Wireframe Challenge (1)
Dismiss notification
Earlier Dismiss All
You have no more notifications

April 9, 2020 Single Round Match 730 Editorials

IntervalIntersections

Used as: Division Two – Level One:

Value250
Submission Rate235 / 267 (88.01%)
Success Rate177 / 235 (75.32%)
High Scorecnyali_lk for 248.75 points (2 mins 1 secs)
Average Score202.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:

Value500
Submission Rate106 / 267 (39.70%)
Success Rate87 / 106 (82.08%)
High Scorecxhscst2 for 469.89 points (7 mins 17 secs)
Average Score296.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:

Value1000
Submission Rate18 / 267 (6.74%)
Success Rate3 / 18 (16.67%)
High Scoremaroon_kuri for 897.68 points (9 mins 49 secs)
Average Score640.17 (for 3 correct submissions)

StonesOnATree

Used as: Division One – Level One:

Value250
Submission Rate181 / 216 (83.80%)
Success Rate109 / 181 (60.22%)
High ScoreKriii for 236.54 points (6 mins 51 secs)
Average Score161.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 &amp;x : g[i]) u.push_back({ w[x],a[x] });
    sort(u.begin(), u.end(), [](const pair<int, int> &amp;a, const pair<int, int> &amp;b) {
      return max(a.second, a.first + b.second) < max(b.second,b.first+a.second);
    });

    int r = 0, s = 0;
    for (auto &amp;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:

Value500
Submission Rate63 / 216 (29.17%)
Success Rate51 / 63 (80.95%)
High ScoreKriii for 413.36 points (13 mins 36 secs)
Average Score283.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 &amp;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:

Value1000
Submission Rate24 / 216 (11.11%)
Success Rate24 / 24 (100.00%)
High Scoreksun48 for 975.25 points (4 mins 32 secs)
Average Score722.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;
  }
};

a.poorakhavan

Guest Blogger


categories & Tags


UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds