Question 1

N cities are there connected using (n-1) bidirectional roads. Each city has a score given by A[i]. Two Marathons were to be organized. But the path of the marathon to contain cities with only even score or an odd score. You have to tell max number of cities in the marathon path if the cities were with even score or with odd score.

Input

5 (n cities)
4 3 2 3 5 (n scores of cities)
1 2 (n-1 lines denoting a road b/w two cities)
1 3
2 4
2 5

Output

2 3

Question 2

Doctor Strange is finding the number of outcomes where Avengers will win the war given that number of days the war will go on.

The possible number of wins given by d days = number of pure number sequences of length d.

A pure number sequence is a sequence of digits where any digit (0-9) can come at any index i iff either n is 0(zero) or any divisor of n(except for 1) has been already placed before such that (j

ADD COMMENT • link

Entering edit mode

Question 1 : Simple Approach using Disjoint set union.

Connect those edges were score of the nodes have same parity. (even / odd)
Check the size of the largest connected component.
Do the above process separately for odd score nodes and even score nodes.


vector&lt;int&gt; par;
vector&lt;int&gt; size;

void find(int u){
    if(par[u] == -1) return u;
    else return par[u] = find(par[u]);
}

void merge(int u , int v){
    u = find(u);
    v = find(v);
    if( u != v){
        par[u] = v;
        size[v] += size[u];
    }
}

void solve(int n , vector&lt;int&gt; score , vector&lt;vector&lt;int&gt;&gt; edge){
    par.assign(n , -1);
    size.assign(n, 1);

    // find largest odd score connected component.
    for(auto i : edge){
        int u = i[0];
        int v = i[1];
        if( score[u]%2 &amp;&amp; score[v]%2 ){
            merge(u,v);
        }
    }

    int odd_size = *max_element(size.begin() , size.end());

    par.assign(n , -1);
    size.assign(n, 1);

    // find largest even score connected component.
    for(auto i : edge){
        int u = i[0];
        int v = i[1];
        if( (score[u]+1)%2 &amp;&amp; (score[v]+1)%2 ){
            merge(u,v);
        }
    }

    int even_size = *max_element(size.begin() , size.end());
}

ADD COMMENT • link 2.2 years ago Gigaliths 570

Entering edit mode

did u check for the and ?? , as I think question is stating about a marathon meaning each node is visited only once during a path from start to end

In that case the max size of connected component will be wrong (ex a plus shaped tree having nodes of same parity)

ADD REPLY • link 11 weeks ago

jolly • 0

Entering edit mode

Question 1

Overview

N cities are there connected using (n-1) bidirectional roads.
Each city has a score given by A[i].
Two Marathons were to be organized.
But the path of the marathon to contain cities with only an even score or an odd score.
You have to tell the max number of cities in the marathon path if the cities were with an even score or with an odd score.
So basically one marathon will contain a simple path where the score of every city is even and the other will contain a simple path where the score of every city is odd.
We just have to maximize the number of cities.

Solution

We will start our dfs from node 1.If you have not read about dfs then read it and come back again.
Now for every city we will do the following.
- Let's say the current city has multiple children some of which will contain an even score path and others an odd score path.
- Put even score paths in one vector(ve) and odd score paths in another vector(vo).
- Sort these vectors in descending order.
- Now if the current city score is odd then,
  - ans_odd_path=max(ans_odd_path,1+vo[0]+vo[1]) if vo.size()>1
  - ans_odd_path=max(ans_odd_path,1+vo[0]) if vo.size()==1
  - ans_odd_path=max(ans_odd_path,1) if vo.size()==0
- Now if the current city score is even then,
  - ans_even_path=max(ans_even_path,1+ve[0]+ve[1]) if ve.size()>1
  - ans_even_path=max(ans_even_path,1+ve[0]) if ve.size()==1
  - ans_even_path=max(ans_even_path,1) if ve.size()==0

Now at last return a pair {max_even_length_path,max_odd_length+path} starting from current vertex and going down.
After the dfs is over, cout ans_even_path and ans_odd_path.

ADD COMMENT • link 2.2 years ago Ujjwal Srivastava 320