As they were totally exhausted with the daily chores, Ketani and Nilswap decided to play a game.They get alternate turns in the game and Ketani starts the game. The game consists of a tree containing N nodes numbered 1 to N. On each turn the person chooses a node of the tree that is not yet numbered. If it’s Ketani’s turn, he writes an odd number to this node whereas if it’s Nilswap’s turn, he writes an even number to this node.
After the entire tree has been numbered, all the odd numbered nodes that are adjacent to an even numbered node turn even (instantaneous, no propagation).
If the tree contains any odd number in the end, Ketani wins otherwise Nilswap wins. You need to output the name of the winner.
Note: Initially none of the nodes contains a number. Both players play optimally.
Input
The first line of the input contains an integer N, the number of nodes in the tree.
The next N-1 lines contain two integers u, v indicating there is an edge between u and v.
Constraints
2 <= N <= 100000
1 <= u, v <= 100000
u != v
The given edges form a tree.
Output
Output a single string, the winner of the game.
Sample Input 1
3
1 2
2 3
Sample Output 1
Ketani
Sample Input 2
2
1 2
Sample Output 2
Nilswap
Explanation 1:
→ Ketani writes an odd number to node 2.
→ Nilswap writes an even number to node 3.
→ Ketani writes an odd number to node 1.
→ After this, node 2 converts to an even number. But node 1 is still white. So Ketani wins.
Its from newton challenge which ended yesterday.
Link - https://my.newtonschool.co/course/ldrj7tqzlt/timeline/
@everule1 @aryan12 @ajaymalik
@aryan12 So , basically we have to check If any node has more than 1 leaf node ?
If yes, then ketani wins, otherswise Nilswap wins.
Is that right?
Also , since it is a tree , so there’s only one connected component, then why are you checking this -
if(g[i].size() != 1 && vis[i] == false) {
dfs(i, -1);
break; //the graph is connected, so why waste time
}
What will be the answer to the test case
5
1 2
2 3
3 4
4 5
I believe it should be
Ketani.
If Ketani Starts with 4, Nilswap will be forced to play on 5, then ketani will play on 2, Then Nilswap can play on either 3 or 1, and will lose either ways.
1 Like
So , basically we have to check If any node has more than 1 leaf node ?
As its immediate children.
Eg.
3
1 2
2 3
If the current node is 1, we will only consider edges going out from 1. There is only 1 edge connecting to 2, thus we will ONLY consider 2, not 3.
I am checking that because you if you are traversing from a root, the code won’t work. But yes, you can do that, and will have to modify the dfs() function a bit.
//snippet from dfs() solution
if(to != parent) //we can't go back to the parent
continue;
if(g[to].size() == 1) { //if it a leaf or not. Leaf has a size of 1 because it has a connecting edge with its parent
LeafChildren++;
}
You just have to interchange the 2 if conditions. Thanks for making me realize this.
Oh, ya, I missed this. My solution is wrong.
I believe your solution is correct for even N.
1 Like
Let me see If I can find a counterexample.
Try
7
1 2
2 3
1 4
4 5
1 6
6 7
Ketani can choose 2,4 and 6 in an arbitrary order and force Nilswap to choose 3, 5 and 7, after which she can choose 1.
But yeah, there is a single path of length 3 na. In the sense that there is
1 2
2 3.
And there is no way to go from 2 to any other node except 3. I mean like a basically there have to be 2 bridges originating from one node only.
Wait, did I get the answer, finding 2 bridges originating from a single node?
1 Like
Yeah, but in even length also, if a node has 2 leaf nodes as its immediate children, the edges connected them are bridges na?
Leaf nodes seem to be an exception.
I don’t think ketani can win the last case if I extended all the bridges by 1.
In fact, Ketani will always win when n is odd, at least under testing 10 to 15 trees.
1 Like
In n is even, then also Ketani can win in some cases.
Where do you submit the code?
It was from a coding challenge, but its link is expired now.