JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Div 1 OwaskiAndTree | Reply
Can someone please share their approach for solving Div 1 OwaskiAndTree . I tried reading the codes, but I am unable to understand how is the dp solution working.
Thanks in advance .
Re: Div 1 OwaskiAndTree (response to post by FundamentalEq) | Reply
class TwoDogsOnATree:
	def maximalXorSum(self, parent, w):
		N=len(parent)+1
		fromRoot = [0]*N
		for i in xrange(1, N):
			fromRoot[i]=fromRoot[parent[i-1]]^w[i-1]
		allAvailValsForTwoVertices = [False]*1024
		for i in xrange(N):
			for j in xrange(N):
				allAvailValsForTwoVertices[fromRoot[i]^fromRoot[j]]=True
		twoDogs=[dog1^dog2 for dog1 in xrange(1024) for dog2 in xrange(1024) if allAvailValsForTwoVertices[dog1] and allAvailValsForTwoVertices[dog2]]
		return max(twoDogs)

all bases on XOR fact
 a == a ^ whatever ^ whatever 
RSS