Soluție HackerRank pentru Company Retreat. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Company Retreat

Cerinta completa

The LRT Company has [Expresie matematică indisponibilă în copia arhivată] employees. Each employee has a unique ID number from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], where the director’s ID is number [Expresie matematică indisponibilă în copia arhivată]. Every employee in the company has exactly one immediate supervisor — except the director, who has no supervisor. The company’s employee hierarchy forms a tree of employee IDs that’s rooted at employee number [Expresie matematică indisponibilă în copia arhivată] (the director).

The director decides to have a retreat lasting [Expresie matematică indisponibilă în copia arhivată] days. Each day, the employees will be assigned to different groups for team building exercises. Groups are constructed in the following way:

  • An employee can invite their immediate supervisor (the director has no supervisor and, thus, doesn’t invite anyone). If employee [Expresie matematică indisponibilă în copia arhivată] is invited by employee [Expresie matematică indisponibilă în copia arhivată], then [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] are considered to be in the same group.
  • Once an employee is invited to be in a group, they are in that group. This means that if two employees have the same immediate supervisor, only one of them can invite that supervisor to be in their group.
  • Every employee must be in a group, even if they are the only employee in it.

The venue where LRT is hosting the retreat has different pricing for each of the [Expresie matematică indisponibilă în copia arhivată] days of the retreat. For each day [Expresie matematică indisponibilă în copia arhivată], there is a cost of [Expresie matematică indisponibilă în copia arhivată] dollars per group and a per-group size limit of [Expresie matematică indisponibilă în copia arhivată] (i.e., the maximum number of people that can be in any group on that day).

Help the director find optimal groupings for each day so the cost of the [Expresie matematică indisponibilă în copia arhivată]-day retreat is minimal, then print the total cost of the retreat. As this answer can be quite large, your answer must be modulo [Expresie matematică indisponibilă în copia arhivată].

Input Format

The first line contains two space-separated integers denoting the respective values of [Expresie matematică indisponibilă în copia arhivată] (the number of employees) and [Expresie matematică indisponibilă în copia arhivată] (the retreat’s duration in days).
The next line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers where each integer [Expresie matematică indisponibilă în copia arhivată] denotes [Expresie matematică indisponibilă în copia arhivată] ([Expresie matematică indisponibilă în copia arhivată]), which is the ID number of employee [Expresie matematică indisponibilă în copia arhivată]‘s direct supervisor.
Each line [Expresie matematică indisponibilă în copia arhivată] of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines contain two space-separated integers describing the respective values of [Expresie matematică indisponibilă în copia arhivată] (the cost per group in dollars) and [Expresie matematică indisponibilă în copia arhivată] (the maximum number of people per group) for the [Expresie matematică indisponibilă în copia arhivată] day of the retreat.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Subtask

  • [Expresie matematică indisponibilă în copia arhivată] for [Expresie matematică indisponibilă în copia arhivată] of the maximum possible score.

Output Format

Print a single integer denoting the minimum total cost for the [Expresie matematică indisponibilă în copia arhivată]-day retreat. As this number can be quite large, print your answer modulo [Expresie matematică indisponibilă în copia arhivată].

Sample Input

7 3
1 1 3 4 2 4
5 3
6 2
1 1

Sample Output

46

Explanation

In the Sample Case above, the company has [Expresie matematică indisponibilă în copia arhivată] employees and the retreat goes on for [Expresie matematică indisponibilă în copia arhivată] days. The hierarchy looks like this:
company hierarchy

On the first day, the cost per group is [Expresie matematică indisponibilă în copia arhivată] dollars and each group has a maximum size of [Expresie matematică indisponibilă în copia arhivată]. The employees split into the following three groups:

  1. Employee [Expresie matematică indisponibilă în copia arhivată] invites their manager, employee [Expresie matematică indisponibilă în copia arhivată]. Employee [Expresie matematică indisponibilă în copia arhivată] then invites their manager, employee [Expresie matematică indisponibilă în copia arhivată] (the director).
  2. Employee [Expresie matematică indisponibilă în copia arhivată] invites their manager, employee [Expresie matematică indisponibilă în copia arhivată]. Employee [Expresie matematică indisponibilă în copia arhivată] then invites their manager, employee [Expresie matematică indisponibilă în copia arhivată].
  3. Employee [Expresie matematică indisponibilă în copia arhivată]‘s manager is already in another group, so they are in a group by themself.

These groupings are demonstrated in the following image where each group has a different pattern:

groupings

In other words, the final groups are [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]. This means the total cost for the first day is [Expresie matematică indisponibilă în copia arhivată] dollars.

On the second day, they split into [Expresie matematică indisponibilă în copia arhivată] groups with a maximum size of [Expresie matematică indisponibilă în copia arhivată] at a total cost of [Expresie matematică indisponibilă în copia arhivată] dollars. On the third day, they split into [Expresie matematică indisponibilă în copia arhivată] groups of size [Expresie matematică indisponibilă în copia arhivată] at a total cost of [Expresie matematică indisponibilă în copia arhivată] dollars. When we sum the costs for all three days, we get [Expresie matematică indisponibilă în copia arhivată] as our answer.

Limbajul de programare folosit: cpp14

Cod:

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 1 << 17;
const int LOG = 17;

int n, m, tick, cnt;
int dep[N], st[N], nd[N], a[N], leaf[N];
vector < int > v[N], q[N];

int t[N << 1], sparse[LOG][N];

void up(int x, int k) {
    t[x += N] = k;
    while(x > 1) {
        x >>= 1;
        t[x] = min(t[x + x], t[x + x + 1]);
    }
}

int get(int l, int r) {
    int res = 1e9;
    for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
        if(l & 1) res = min(res, t[l]);
        if(~r & 1) res = min(res, t[r]);
    }
    return res;
}

void dfs(int p, int x) {
    st[x] = ++tick;
    dep[x] = dep[p] + 1;
    sparse[0][x] = p;
    for(int i = 1; i < LOG; i++)
        sparse[i][x] = sparse[i - 1][sparse[i - 1][x]];
    leaf[x] = 1e9;
    for(auto u : v[x]) {
        dfs(x, u);
        leaf[x] = min(leaf[x], leaf[u] + 1);
    }
    if(leaf[x] > 5e8) {
        leaf[x] = 0;
        cnt++;
    }
    q[leaf[x]].push_back(x);
    nd[x] = tick;
}

int calc(int group) {
    int res = cnt;
    priority_queue < ii > Q;
    for(auto x : q[group])
        Q.push({dep[x], x});
    vector < int > vv;
    while(!Q.empty()) {
        int x = Q.top().second;
        Q.pop();
        if(leaf[x] < group or get(st[x], nd[x]) - dep[x] < group)
            continue;
        vv.push_back(x);
        up(st[x], dep[x]);
        res++;
        if(dep[x] > group) {
            int k = group;
            for(int i = LOG - 1; i >= 0; i--) {
                if(k >= (1 << i)) {
                    k -= 1 << i;
                    x = sparse[i][x];
                }
            }
            Q.push({dep[x], x});
        }
    }
    for(auto x : vv)
        up(st[x], 1e9);
    return res;
}

int main () {

    for(int i = 1; i < N + N; i++)
        t[i] = 1e9;

    scanf("%d %d", &n, &m);

    for(int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        v[x].push_back(i);
    }

    dfs(0, 1);

    for(int i = 1; i <= n; i++)
        a[i] = calc(i);

    ll ans = 0;

    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ans += (ll) x * a[min(n, y)];
        ans %= (int) 1e9 + 7;
    }

    printf("%lld\n", ans);

    return 0;

}

Scor obtinut: 1.0

Submission ID: 464654078

Link challenge: https://www.hackerrank.com/challenges/company-retreat/problem

Company Retreat