HackerEarth Population outburst problem solution

In this HackerEarth Population outburst problem solution, A new species is trying to rule the planet. This species is creating its own population outburst to dominate other species. It all started with 1 single member of the species. The population increases in treelike fashion abiding by few rules as listed below.

Single-member is able to reproduce by themselves.
A new member is added to the population every minute.
Every member is associated with the integral name.
Multiple members can share a common name.
Every member has its own reproduction capacity, that is the maximum number of children it can reproduce.
A member can start to reproduce only if all members are older than it has exhausted their reproduction capacity.
Level 0 in the family tree of this species comprises the single member at the start of multiplication.
The integral name of the single-member at the start is 0.
The population grows level-wise, where the number of members at level i is dependent on the reproduction capacity of members at the prior level.

Given the integral name of the new member and its reproduction capacity that is added to the population, you have to find its parent, the level at which it is added, and its ascending age-wise rank among siblings.

HackerEarth Population outburst problem solution.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int, int>
#define iiii pair<ii, ii>
#define ff first 
#define ss second 

int main(){
    int i,j,n,k,c,id;
    iiii tp;
    deque<iiii> dq;
    scanf("%d %d", &n, &c);
    dq.push_front({{0, 1}, {0, c}});
    while(n--){
        scanf("%d %d", &id, &c);
        tp = dq.back();
        dq.pop_back();
        if(1 <= c)
            dq.push_front({{id, 1}, {tp.ss.ff + 1, c}});
        printf("%d %d %dn", tp.ff.ff, tp.ss.ff + 1, tp.ff.ss);
        tp.ff.ss++;
        if(tp.ff.ss <= tp.ss.ss)
            dq.push_back(tp);
    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;


void verify(int n, int l, int r){
    assert(n >= l && n <= r);
}

const int N = 1000002;
int level[N], children[N], name[N];

 
int main(){

    int n, rc0;
    scanf("%d%d", &n, &rc0);

    verify(n, 1, 1000*1000);
    verify(rc0, 0, 1000*1000*1000);

    name[0] = 0;
    level[0] = 0;
    queue<int> qq;
    while(rc0-- && (int)qq.size() < n)  qq.push(0);

    int next = 1;
    while(n--){

        int id, rc;
        scanf("%d%d", &id, &rc);
        name[next] = id;

        verify(id, -1000*1000*1000, 1000*1000*1000);
        verify(rc, 0, 1000*1000*1000);

        assert(!qq.empty());
        int par = qq.front();
        qq.pop();

        children[par]++;
        level[next] = level[par] + 1;
        printf("%d %d %dn", name[par], level[next], children[par]);

        while(rc-- && (int)qq.size() < n+1) qq.push(next);
        next++;
    }

    return 0;
}

HackerEarth Population outburst problem solution

HackerEarth Population outburst problem solution.

Second solution

Leave a Reply

Pages

Practice