https://www.acmicpc.net/problem/15900
initial
Basically if you have even number of total moves, you lose. Else you win.
So calculating the total number of moves is the primary impl. I tried calculating the total number of moves by doing dfs on each leaf nodes Obviously this ran to correct but runtime issues
initial correct but v inefficient code
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
import math
n=int(input())
graph=defaultdict(list)
for _ in range(n-1):
a,b=map(int,input().split())
graph[a].append(b)
graph[b].append(a)
ans=[]
for key in graph.keys():
if len(graph[key])==1 and key != 1:
ans.append(key)
count=0
visited=[False for _ in range(n+1)]
def dfs(node):
global count
for i in graph[node]:
if i==1:
count+=1
return
if not visited[i]:
count+=1
visited[i]=True
dfs(i)
visited[i]=False
for i in ans:
visited[i]=True
dfs(i)
if count%2==0:
print("No")
else:
print("Yes")I initially thought of doing dfs from root node 1 but my logic for adding the distance was completely misguided like I thought it is impossible to calculate distance.
What I did wrongly was
def dfs(node):
visited[node]=True
for a in graph[node]:
if not visited[a]:
dist[a]+=1
dfs(a)If you look, I am incrementing the distance by 1. So there is an overlap of moves, the total number of moves is below than the expected answer because the move is skipped.
For example,
4
1 2
2 3
2 4
dist[2] should be 2, not 1 as calculated with my approach.
What I should have done is update the distance from the previous node's distance +1 like dist[a]=dist[node]+1.
def dfs(node):
visited[node]=True
for a in graph[node]:
if not visited[a]:
dist[a]=dist[node]+1
dfs(a)solution
I keep getting recursionerror for pypy so chatgpt suggested using an iterative wawy
recurisve
recursionerror but correct:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
graph = defaultdict(list)
dist = [0 for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
count = 0
visited = [False for _ in range(n + 1)]
# Stack for iterative DFS
stack = [1] # Start with the root node
while stack:
node = stack.pop()
visited[node] = True
for a in graph[node]:
if not visited[a]:
dist[a] = dist[node] + 1
stack.append(a)
for i in range(2, len(dist)):
if len(graph[i]) == 1:
count += dist[i]
if count % 2 == 0:
print("No")
else:
print("Yes")revisited jan 30th
put 200000 as the recursion limit and this recursive method works.
Also I managed to think of dfs from root node 1 but we shouldnt do dist[a]+=1 like my initial explanataion. It should be taking the previous state and incrementing it by 1.
iterative (good time)
using a stack and pretty good timewise
[fixed] using a stack is to fix that recursionerror. the time complexity is the same. wait is it?
import sys
from collections import defaultdict
n = int(input())
graph = defaultdict(list)
dist = [0 for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
count = 0
visited = [False for _ in range(n + 1)]
# Stack for iterative DFS
stack = [1] # Start with the root node
while stack:
node = stack.pop()
visited[node] = True
for a in graph[node]:
if not visited[a]:
dist[a] = dist[node] + 1
stack.append(a)
for i in range(2, len(dist)):
if len(graph[i]) == 1:
count += dist[i]
if count % 2 == 0:
print("No")
else:
print("Yes")complexity
i thought stack is more timeefficient but it is only to fix recursionerror
The time complexity of both the recursive and iterative approaches for tree traversal in your code is O(N), where N is the number of nodes in the tree. This is because you need to visit each node once to calculate the distances and check for the desired condition.
The space complexity is different between the two approaches:
-
Recursive Approach: The recursive approach uses the call stack for function calls. In the worst case, where the tree is very deep (skewed), the space complexity for the recursive approach can be O(N), as each function call is pushed onto the stack. If the tree is balanced, the space complexity is O(log N).
-
Iterative Approach: The iterative approach uses an explicit stack to simulate the depth-first traversal. The space complexity for the iterative approach is O(N) in the worst case, as you may need to push all nodes onto the stack. It can be less in practice when the tree is balanced, making it O(log N).
The recursive approach might be simpler to implement, but it has the drawback of potentially exceeding the Python maximum recursion depth, which is why you increased the recursion limit using sys.setrecursionlimit(). The iterative approach is generally considered safer and more robust for deep or unbalanced trees.
In most practical scenarios, the choice between the two approaches doesn't significantly affect performance, as both have the same time complexity. However, if you anticipate working with very deep or unbalanced trees, the iterative approach is preferred to avoid stack overflow errors.
