ECPC10D - Editorial

editorial
, , , ,
2

I tried doing this but I it gave me WA somewhere
39285453

1 Like
3

Can you please point out what’s wrong with this code ?

WA CODE 
#include<bits/stdc++.h>
using namespace std ;
const int mxN =1e5+2 ;
int n,a[mxN],ans;
vector<int>adj[mxN] ; 
int ok[mxN]  ;
void dfs(int v=1,int p=0){
  for(int x:adj[v])
    if(x^p)
      dfs(x,v) ;
  int r=0 ;
  for(int x:adj[v]){
    if(x==p)
      continue; 
    r+=ok[x] ;
  }
  if(r%3==0)
    ok[v]=1 ;
  ans-=(r/3)*3 ;
}
void solve(){
  cin >> n ;
  for(int i=1;i<n;i++){
    cin >> a[i] ;
    adj[a[i]].push_back(i+1) ;
    adj[i+1].push_back(a[i]) ;
  }  
  ans =n ;
  dfs() ;
  cout << ans << '\n' ;
  for(int i=1;i<=n;i++)
    adj[i].clear()  ;
  memset(ok,0,sizeof(ok)) ;
  memset(a,0,sizeof(a)) ;
}
signed main(){
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}
4

Whats wrong with the logic of my code ? CodeChef: Practical coding for everyone

5

Try this input
2
17
1 1 1 1 1 4 3 4 4 3 4 3 6 5 5 5
15
1 1 1 3 3 3 3 3 5 6 6 12 12 12
Correct -
5
9
Yours
5
6

1 Like
6

Found my problem . Wasnt counting the nodes which cant be deleted

7

Try this
2
17
1 1 1 1 1 4 3 4 4 3 4 3 6 5 5 5
15
1 1 1 3 3 3 3 3 5 6 6 12 12 12

8

Oh thanks broski
I was stuck on this for a long time
Thanks for the help :smile:

9

Thanks @ash432, the testcase you mentioned is where above mentioned codes fail,
Feel free to write if you need me again here :grin: :blush:

10

@kaalbhairav01 Hi In Question :
(i) For each parent node(which has a valid leaf node attached to it). Can u explain valid leaf nodes means?
(ii) If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node. (from this what I understand is count only leaf nodes and if the count of the leaf node is multiple of 3 then parent also become new leaf but in the editorial problem statement says if all children of a parent are removed it becomes a new leaf node which means I have to check non leaf node also ).
can u explain why my understanding is wrong

11

@sivayempalli

  1. You can see that in the problem statement, leaf node was defined as the one, with no outgoing edges

  2. “if a parent has all its leaf nodes cut”, this is the source of confusion I assume, carefully reading further and to full, the question provides every non leaf node a scope to convert itself into a leaf node. The counting of any non leaf node can not be skipped as such because there would be no guarantee if it had the capability to turn into a leaf node. Hence if you have checked all child nodes of a parent to see if a non leaf node can become leaf, only then will you know the actual number of leaf nodes. We require a strong basis to not take into account a node which is non leaf, which can’t be obtained without checking it. Now after confirming all nodes which are “actually leaf”, we can count them and if this count is a multiple of 3, all of them will be removed, so in this case all child nodes are being removed, and all child nodes were leaf nodes too.

Also see the explanation to sample testcase, for better clarity, you can also think of a sudoku or minesweeper, where you must be sure before taking the decision. Same goes with ignoring a non leaf node.
Hope it helps

12

Thanks man.one point
for example, a parent node with child nodes is (1 leaf and 2 potential leaf nodes and 2 non-leaf nodes(its child node are not multiplies of 3 )). this information I will get doing dfs on parent node . now what I’m doing is counting leaf node and potential leaf node (1+2 = 3) so 3 multiply of 3 so I’m considering parent as a potential leaf node.

But after reading the editorial, what I got is, for that parent 2 non-leaf child node are present so parent cannot be a new leaf node or potential leaf node

Can u explain for this example?

13

Hey brother, I recognise the confusion you are referring to, and that is why the case similar to the one you wrote was shown in the explanation which might be you have missed out, here
Sample1
Consider node 4 which had 3 nodes removed but was not considered a leaf because it still had a outgoing edge. “If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node” the line is the next parameter for any parent node to satisfy, it nowhere demurs the basic definition of leaf node- which has no outgoing edges as written in the problem statement, i hope the explanation image above clarifies it in the question

14

Hi, have you uploaded the Editorials for ECPC10E, ECPC10F and ECPC10G? If not, could you please upload it? If yes, could you please provide the link? I am not able to find them.
Thanks

15

Hey there @shashank2409 , Those three editorials are underway and will be posted as soon as possible, the same will be notified on the Contest Invitation post too. The delay has occured due to the sudden ill health of the setter cum editorialist, we hope the wait will be worth

1 Like
16

Okay. Not an issue. Hope he gets well soon. :slight_smile:

17

I’m thinking about a solution where I would find the level of every nodes, then going up level by level from the leaf nodes, calculating how many nodes will be deleted and which parent will no longer be parent node, would this work ?

18

@shashank2409 They are available now, refer to rest editorials here Invitation to ECPC 1.0

19

Okay. Thank you.

20

@bubu2006, as i see that, it’s a straight forward dfs approach ques, however what you wrote sounds exactly what needs to be done, it depends on your implementation, you can try that

1 Like
21

Thanks!

1 Like