SUBMEXS - Editorial

editorial
, , , , , ,
54

Can someone help me out with yesterdayā€™s Lunchtime submexes question ? Canā€™t seem to figure out where Iā€™m going wrong.

Question link CodeChef: Practical coding for everyone

My solution link : CodeChef: Practical coding for everyone

I saw the video editorial of Codechefā€™s official channel on YouTube and Iā€™m getting proper output for the test inputs they have used
Test Input :
3
9
1 1 2 2 3 4 5 6
9
1 1 2 2 3 6 7 8
11
1 2 2 2 2 2 2 1 9 10
Output(which is correct) that Iā€™m getting
17
24
19

Approach that Iā€™ve used :
1)Store the tree in an adjacency list and also store the number of nodes every leaf node has in an array.
2)Initialise count variable to 0,
Traverse root node, increment count by (number of children of that node +1) and go to the child node with highest number of children and keep doing this till leaf node is reached

If you want you can uncomment all the stuff that Iā€™ve commented in my code and try running it in your pc, it will better describe what exactly the code is doing.

Any help is appreciated

1 Like
56

Hey Brother,
Your code is failing for the following test case:

Input:

1
10
1 1 1 4 2 2 3 3 5

Expected Output - 16
Your output - 14

This is due to fact that considering maximum number of nodes in a subtree for calculating MEX is wrong. You have to consider height too.

Draw the tree on pen and paper and dry run it.You will get what i just told. :slightly_smiling_face:

1 Like
57

Brother,Your simple code explains the approach itself.

I watched the editorial video which made me more confused than i was before.

After looking at your code,i got to know where i went wrong and how the correct approach is really working!

Good Job!

1 Like
58

Finally I understood it. Thank you for you help bud, really appreciate it. :innocent:

1 Like
59

I know right, even i felt the editorial was a little confusing :sweat_smile:

1 Like
60

Video is focussed more on formality.
The part where explaination was needed,There was no explaination.

1 Like
61

Thanks a lot man but I m too weak in codeforces :neutral_face:

1 Like
62

Brother, its about about how to write a user friendly code so that others can understand. :slightly_smiling_face:

1 Like
63

:grinning:

1 Like
65

Nice and user friendly code!
Good job!

1 Like
66

Got AC.
Time 0.13 sec.

Approach :
Calculate and store subtree size of each node in a vector called subtree[i].
While backtraking at each node return subtree[node] + max(value returned by below subtree)ā€¦

Please see solution for clear understanding ā€¦
https://www.codechef.com/viewsolution/39266674

Thanks

67

Link u have given does not lead to your solution. This is correct link

68

If anybody is facing difficulty in understanding the reason for the solution.
Check my solution, i have added comments to explain the reason.

Solution-Click Here

Draw tree on a paper,it helps in getting a better understanding!

1 Like
69

Take a look, I used the same approach but

70

Thxx

71

@zephxr Editorial was confusing, Thanks for the code with comments.

1 Like
72

Welcome Buddy!

73

My code is not passing 1 and 2 test cases. Anyone can help me, please?

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
vector adj[MAX];
long long cnt[MAX];
long long size[MAX];
void dfs(int i,int p)
{
cnt[i] = -1;
size[i] = 1;
for(int k=0;k<adj[i].size();k++)
{
int node = adj[i][k];

   if(node==p) continue;
   
   dfs(node,i);
   
   size[i] += size[node];
   cnt[i] = max(cnt[i],cnt[node]);

}
if(adj[i].size()>1)
cnt[i] += size[i];
else
cnt[i] = 1;

}
void init()
{
for(int i=0;i<MAX;i++)
{
adj[i].clear();
size[i]=0;
cnt[i]=0;
}
}
int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
   int n;
   cin>>n;
   init();
   for(int i=1;i<n;i++)
   {
       int x;
       cin>>x;
       adj[x].push_back(i+1);
       adj[i+1].push_back(x);
   }
  
  dfs(1,-1);    
  
  cout<<cnt[1]<<endl;
    
}

return 0;

}

1 Like
75

Below is my code ,O(n) solution .But it is passing only first testcase and TLE in rest .Please let me know why is it so !

#include
#include
#include
#define lli long long int
using namespace std;

int size[100001];
int vis[100001];
lli final[100001];
void dfs(int s,vector<vector > adj)
{
if(vis[s] == 0) vis[s] = 1;
int max = -1;
for(int i =0;i<adj[s].size();i++)
{
int child = adj[s][i];
if(vis[child] == 0)
{
dfs(child,adj);
size[s]+=size[child];
if(final[child]>max) max = final[child];

	}
	if(max!= -1)
	final[s]=max + size[s];
}

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int T;
scanf("%d",&T);
while(T--)
{
	int N,p;
	scanf("%d",&N);
	
	vector<vector<int > > adj(N+1);
	size[1] = 1;
	vis[1] = 0;
	final[1] = 1;
	for(int i =2;i<=N;i++)
	{
		size[i] = 1;
		vis[i] = 0;
		final[i] = 1;
		scanf("%d",&p);
		adj[p].push_back(i);
		adj[i].push_back(p);
	}
	dfs(1,adj);
	printf("%lld\n",final[1]);
}
return 0;

}

76

nice man what a nice test casesā€¦
Thanks for this. which clearly breaks greedy approachā€¦ thanks