BNYHOP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Hemanth Ram
Tester: Anay Karnik
Editorialist: Mohan Abhyas

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

None

PROBLEM:

Bugs Bunny is very smart, but he keeps constantly worrying about the future and is always anxious. Therefore, he keeps hopping between towns without standing still.

The place where Bugs Bunny lives has N towns (numbered 1 through N) with one-way roads connecting them in such a way that they form an arborescence (a tree with all paths directed from the root), rooted at town 1. Therefore, each town except the root has exactly one incoming road; for each i (1 \le i \le N-1), there is a road from town P_i to town i+1. Each town has a distinct rating associated with it; for each valid i, the i-th town has rating A_i.

From a town i, Bugs Bunny is allowed to hop to town j (without visiting any other towns in between), if the following conditions are satisfied:

  • there is a path between towns i and j, i.e. a path from town i to town j or from town j to town i
  • town j has a lower rating than town i, i.e. A_j \lt A_i

This way, Bugs Bunny can visit a sequence of towns by hopping, starting anywhere and stopping whenever he chooses. Clearly, he cannot keep hopping forever, so the number of such sequences is finite.

Tell Bugs Bunny the number of sequences of two or more towns which can be formed by hopping, given that he can start at any town and stop at any town. Since this number can be very large, calculate it modulo 10^9+7.

EXPLANATION:

Number of sequences ending at node i = 1(sequence - {i}) + number of sequences ending in node j such that A_j > A_i and j is in subtree in of i or j is ancestor of i

This can be done in the following way
Find the eulerian tour of the tree. Maintain two fenwick trees on the eulerian tour of tree.
Traverse the nodes of the the tree in the decreasing order of A_i.

In the first fenwick tree maintain number of sequences ending at i at it’s start position of euler tour.
In the second fenwick tree maintain number of sequences ending at i at it’s start position of euler tour, -1*number of sequences ending at i at it’s end position of euler tour

For processing i i.e., finding no of sequences ending at i
number of sequences ending at subtree of i = sum of values stored in first fenwick tree from start, end positions of i.
number of sequences ending at ancestor of i = sum of values stores in second fenwick tree from position 1 to start position of i

Final answer will be sum of values stored in first fenwick tree

TIME COMPLEXITY:

\mathcal{O}(Nlog(N)) per testcase.

SOLUTIONS:

[details = “Setter’s Solution”]

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
const int INF = INT_MAX;
const int M = 1000000007;

class BIT {
    vector<int> tree; int N;
    public:
        BIT(int n) { tree.resize(n+1,0); N = n; }
        int query(int x);
        void update(int x, int v);
        int rangeSum(int l, int r);
};

int BIT::query(int x) {
    x += 1;
    int su = 0;
    while(x>0) {
        su = (su+tree[x])%M;
        x -= (x&(-x));
    } return su;
}

void BIT::update(int x, int v) {
    x += 1;
    while(x<=N) {
        tree[x] = ((tree[x]+v)%M + M)%M;
        x += (x&(-x));
    }
}

int BIT::rangeSum(int l, int r) {
    if(l>r) return 0;
    int ls = query(l-1);
    int rs = query(r);
    return (rs-ls+M)%M;
}

void eulerTour(int u, vector<vector<int>> &g, vector<int> &tour, vector<int> &start, vector<int> &end, int &x) {
    tour.push_back(u);
    start[u] = tour.size()-1;
    for(auto v:g[u]) {
        eulerTour(v, g, tour, start, end, x);
    } tour.push_back(u);
    end[u] = tour.size()-1;
}

void solve(int tc) {
    int n,x=0; cin>>n;

    vector<int> parent(n+1,0), a(n+1);
    vector<pair<int,int>> a_ix(1);
    vector<vector<int>> g(n+1, vector<int>());

    for(int i = 2; i<=n; ++i) {
        cin>>parent[i];
        g[parent[i]].push_back(i);
    }

    for(int i = 1; i<=n; ++i) {
        cin>>a[i];
        a_ix.push_back(make_pair(a[i], i));
    }
    sort(a_ix.begin(), a_ix.end(), greater<pair<int,int>>());

    vector<int> tour, st(n+1), en(n+1), ans(n+1);
    eulerTour(1, g, tour, st, en, x);

    BIT dp_subtrees(2*n), dp_tree(2*n);
    for(int i = 0; i<n; ++i) {
        int ix = a_ix[i].second;
        int cur = 1;
        cur = (cur+dp_tree.rangeSum(st[ix], en[ix]))%M;
        cur = (cur+dp_subtrees.query(st[ix]))%M;

        ans[ix] = cur;
        
        dp_subtrees.update(st[ix], cur);
        dp_subtrees.update(en[ix], -cur);
        dp_tree.update(st[ix], cur);
    }

    int tot = 0;
    for(int i = 1; i<=n; ++i) tot = (tot+ans[i])%M;
    cout<<(tot-n+M)%M<<'\n';
}

int main(){
    fastio;
	#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
	#endif
    int t = 1, u = 1;
    cin>>t;
    while(t--)
    solve(u++);

    return(0);
}
5 Likes

Can you please explain what are the 8 paths in the sample case two of this question?

9 Likes

If you assume the nodes are number 1 to 5, the 8 paths would be:

(1,2), (1,3),(1,4),(1,5),(4,3),(5,3),(1,4,3),(1,5,3)

Edit: (1,4) is possible because there is a path between 1 and 4 and the rating of 1 (50) is > rating of 4 (40). Similarly with (1,5) and the other paths as well. Take (1,5,3) for example: there is a path between 1 and 5 and rating of 1 (50) > rating of 5 (30). The next hop from 5 to 3 is also possible because there is a path from 3 to 5 (the problem statement says the path can be between i and j or j and i) and rating of 5 > rating of 3

2 Likes

Excellent problem but I found the problem statement to be a bit vague/confusing.

20 Likes

Excellent problem. Kudos to the author for setting such a problem. But on the other hand, I think the statement was quite convoluting. Please try to make the statements less complex, or give more explanations to examples if the first one can’t be achieved. I asked quite a few questions, and the person responding from the contest team did his best in helping me with the resources he could share, but still it took me quite a lot of time to understand the statement.

Note: This might not be the case for others, but it certainly is for me. And I know for a fact that a handful of us found the statement convoluting.

Thanks for reading this!

12 Likes

How can we contact the contest team in between contests?

how are (1,4) , (1,5) possible ?

also can you please explain how we got these paths?

40<50 and There exist a path between 1 to 4 i.e. 1->3->4. Similar case for 1 to 5.

I can’t understand the 1(sequence-{i}) part. Can anyone please elaborate this for me?

then why not 3->1->2 ? as there is a path and A2 < A3 ??

1 Like

In the second test case how is (1,4,3), (1,4), (1,5) a possible path? If (1,4,3) is possible then why no (4,2) since we can reach 4 from 4 and 2 has lower rating than 4? Who wrote the statement first tell me? And who approved this?

one-way roads connecting them in such a way that they form an arborescence (a tree with all paths directed from the root), rooted at town 1.

As the roads are one way, and it’s an arborescence, there are no paths between 3 to 2. The edges are 1->3 and 1->2 . So we can’t go 3->1->2 . It’s a one-way road.

Anyway, the statement was confusing, and explanation of the test cases was no help too.

I understood it 1 hour after reading the problem. I was solving a whole different problem earlier.

Solution isn’t the time complexity of this solution N_Square ? or I’m missing something ?

It says that there are no prerequisites but can someone explain Fenwick Trees (or share a video/blog post) please?

try Episode 0 from algorithms live.

You can read about it from CP’s Handbook, cp-algorithm or watch algorithms live video on Fenwick Trees.

What is point of passing x in euler tour when you are not using it? I am new to euler tour :slight_smile:

can u please explain how path 4 → 3 is possible … because there is road from
3 → 4 and not from 4->3

there is a comments button at the bottom of the problem , you can ask doubts regarding statements there.