SUBMEXS - Editorial

float_sammy · October 31, 2020, 7:07pm

Can you help me how the answer is 23.

sayan_1999 · October 31, 2020, 7:14pm

First construct the tree as given. Then try to find out. But then please also help me with my solution.

sayan_1999 · October 31, 2020, 7:14pm

Can anyone help me please??

sudeept9876 · October 31, 2020, 8:00pm

My solution is

Find all the leaves
Find the number of immediate children nodes for each node
Go from leaf to root and recursively add number of immediate children for current node+1 for each node coming in the path from leaf to root.
find the maximum possible recursive addition for every leaf.
Result is answer.

But it is giving wrong answer, i can’t think of any test case that fails, please point out the mistake, or just provide a test case.

My solution link:
https://www.codechef.com/viewsolution/39229234

kanisht09 · October 31, 2020, 8:05pm

https://www.codechef.com/viewsolution/39250093
see it

karthickshiva · November 1, 2020, 3:05am

My approach:

Calculate and store the size of subtree for each node. Initialize DP array.

dp[1] = subtreeSize[1]

Starting from root node, start BFS:

dp[children] = dp[parent] + subtreeSize[children]

The answer will be maximum of the DP array.

My solution in Java: https://www.codechef.com/viewsolution/39223219

vishalg8454 · November 1, 2020, 3:05am

I have also the same problem. I checked with an AC code, answer was 23 only. Now figuring out why?

roshan7461 · November 1, 2020, 3:28am

my solution is in o(n ) but it still gives tle can any one please help

#include <bits/stdc++.h>
#define int long long int
#define MOD 1000000000+ 7
#define pb push_back
//memset(a,1,sizeof(a));
using namespace std;

int cnt=0;

int binPow(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res = (1LL * res * a) % MOD;
a = (1LL * a * a) % MOD;

    n >>= 1;
}
return res;

}
int numc(int x,int nc[],vector v[])
{
if(v[x].size()==0)
{

    return 0;
}

int ans=0;

for(int i=0;i<v[x].size();i++)
{
ans+=numc(v[x][i],nc,v)+1;
}
nc[x]=ans;
return ans;
}

int dfs(int x,int visited[],int cnt[],int nc[],int N,vector p,vector v[])
{
visited[x]=1;

cnt[x]=nc[x]+1+cnt[p[x]];
for(int i=0;i<v[x].size();i++)
{
    if(visited[v[x][i]]==0)
    {
        dfs(v[x][i],visited,cnt,nc,N,p,v);
    }
}

}

main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vector p;
p.pb(0);
p.pb(1);
for(int i=1;i<=n-1;i++)
{
int x;
cin>>x;
p.pb(x);
}
vector v[n+1];
for(int i=2;i<=n;i++)
{
v[p[i]].pb(i);
}
int cnt[n+1]={0};
int nc[n+1]={0};
numc(1,nc,v);

  /* for(int i=1;i<=n;i++)
   {
      cout<<nc[i]<< " ";
   }*/
 int visited[n+1]={0};
dfs(1,visited,cnt,nc,n,p,v);
 sort(cnt,cnt+n+1);
 cout<<cnt[n]<<endl;






}

}

roshan7461 · November 1, 2020, 3:30am

i did same but its giving tle can you ols help

#include <bits/stdc++.h>
#define int long long int
#define MOD 1000000000+ 7
#define pb push_back
//memset(a,1,sizeof(a));
using namespace std;

int cnt=0;

int binPow(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res = (1LL * res * a) % MOD;
a = (1LL * a * a) % MOD;

    n >>= 1;
}
return res;

}
int numc(int x,int nc[],vector v[])
{
if(v[x].size()==0)
{

    return 0;
}

int ans=0;

for(int i=0;i<v[x].size();i++)
{
ans+=numc(v[x][i],nc,v)+1;
}
nc[x]=ans;
return ans;
}

int dfs(int x,int visited[],int cnt[],int nc[],int N,vector p,vector v[])
{
visited[x]=1;

cnt[x]=nc[x]+1+cnt[p[x]];
for(int i=0;i<v[x].size();i++)
{
    if(visited[v[x][i]]==0)
    {
        dfs(v[x][i],visited,cnt,nc,N,p,v);
    }
}

}

main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vector p;
p.pb(0);
p.pb(1);
for(int i=1;i<=n-1;i++)
{
int x;
cin>>x;
p.pb(x);
}
vector v[n+1];
for(int i=2;i<=n;i++)
{
v[p[i]].pb(i);
}
int cnt[n+1]={0};
int nc[n+1]={0};
numc(1,nc,v);

  /* for(int i=1;i<=n;i++)
   {
      cout<<nc[i]<< " ";
   }*/
 int visited[n+1]={0};
dfs(1,visited,cnt,nc,n,p,v);
 sort(cnt,cnt+n+1);
 cout<<cnt[n]<<endl;






}

}

roshan7461 · November 1, 2020, 3:32am

numc is number of all child i.e directly on indirectly connected below any vertex;

johndoe_297 · November 1, 2020, 4:12am

My solution is getting AC on 1, 4 & 5 but is gettin RE in 2 & 3. Could someone help what is the problem with my approach?

from sys import stdin
readline, writeline = stdin.readline, stdin.write


class Graph:
def __init__(self):
    self.nnodes = 1
    self.count = 1
    self.children = []


def dfs(node):
    mxc = 1
    for next in adj[node].children:
        dfs(next)
        adj[node].nnodes += adj[next].nnodes
        mxc = max(mxc, adj[next].count)
    if adj[node].children:
        adj[node].count = adj[node].nnodes + mxc


def addEdge(a, b):
    adj[a].children.append(b)


for _ in range(int(readline())):
    n = int(readline())
    a = list(map(int, readline().split()))

    adj = [Graph() for i in range(n+3)]
    for i, p in enumerate(a):
        addEdge(p, i+2)
    dfs(1)
    writeline("{}\n".format(adj[1].count))

abhisek_12345 · November 1, 2020, 4:13am

kanisht , Your code and approach is very elegant and classy, easy to understand. Thanks bro understood everything. I would recommend this sol. for all beginners who find this question and sol. difficult to understand.

sayan_1999 · November 1, 2020, 4:45am

@l_returns Please help him Sir

anon58713095 · November 1, 2020, 4:45am

My approach was about the same but, I didn’t allocate mexes and my code got the sample testcases passed, but somehow on submission it only pasess one out of five-six sub tasks.

What’s wrong with this:
CodeChef: Practical coding for everyone

code_red1 · November 1, 2020, 5:23am

4/5 test cases are passing though I have used the same approach.
Solution link - https://www.codechef.com/submit/complete/39253778

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define sz(v) (int)v.size()

const int MAX = 1e5 + 5;
vector<int> adj[MAX], subsz(MAX), mexSum(MAX);

//Calculating subtree size
void dfs(int ch, int p = -1){
  subsz[ch] = 1;
  mexSum[ch] = 0;
  for(int x : adj[ch]){
      if(x == p){
          continue;
      }else{
          dfs(x, ch);
          subsz[ch] += subsz[x];
      }
  }
  
}

// Calculating mex sum.
void dfs1(int ch, int p = -1){
  if(sz(adj[ch]) == 1 && adj[ch][0] == p){
      mexSum[ch] = 1;
  }

  int ans = 0;
  for(int x : adj[ch]){
      if(p == x)
          continue;
      dfs1(x, ch);
      ans = max(ans, mexSum[x]);
  }
  mexSum[ch] = ans + subsz[ch];
}

int main() { 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  #ifndef ONLINE_JUDGE
      freopen("input.in","r",stdin);
      freopen("output.in","w",stdout);
  #endif
  int t=1;    
  cin>>t;
  while(t--){
      int n;
      cin >> n;
      for(int i = 2; i <= n; i++){
          int x;
          cin >> x;
          adj[x].push_back(i);
          adj[i].push_back(x);
      }
      dfs(1);
      dfs1(1);
      cout << mexSum[1] << endl;

      for(int i = 0; i <=n; i++)
          adj[i].clear();
      
  }
return 0;
}

I have tried to debug many times but still don’t what is the problem.
@psychik Can you please look into it?

not_ay · November 1, 2020, 6:01am

I see… thanks a lot! I got frustrated that I couldn’t solve it and then just gave up should’ve looked at it properly.

shivam_pandey9 · November 1, 2020, 6:09am

I tried the same logic but got TLE

https://www.codechef.com/viewsolution/39254721

santosh780 · November 1, 2020, 6:48am

Did anyone see the video tutorial, I think explanation in video tutorial is not correct from [17:01] to [19:20]. We get pairs( 0+1, 1) from both nodes 2 and 3 . Since our loop runs for two times, ‘s’ will be s+2=3, and maximum m will be 1, And hence from node 1 , pair ( 1+3 =4 , 3) will be returned not (4,2).

susmit_mishra · November 1, 2020, 6:54am

My code is passing 4/5 testcases. Please help me find the bug in my code.
https://www.codechef.com/viewsolution/39255623

I tried stress testing with AC codes but all of them were matching with my answers. Probably testcase generator is not producing the corner testcase.

santosh780 · November 1, 2020, 7:23am

You have initialized ‘m’ as int m=-1 … m should be long long that is the only glitch I see in your solution.