Perfect Trees [Code Overflow 1.2]

help
, , , ,
1

Question : “CodeChef: Practical coding for everyone”

My solution : “CodeChef: Practical coding for everyone”

For 30 marks what i did is store all the descendent of each node and check each of them.

Can anyone please share approach , how can I do this question for 100 marks , seems to be some standard technique or dp on tree , but don’t know share your approach I will try to code.

@everule1 @galencolin @souradeep1999

1 Like
2

First initially precompute for a number i what are the possible number j exists such that i * j = x^2.
In dfs when you go to the subtree of a node u then take the contribution of node u in account and increase the count of a_u using map and when you came out of that node decrease it’s contribution from map. And to keep track of min distance let keep a list for each value 1 to 500. And when you go into a subtree of node u then push this node in list_{level_u} and when you came out just pop, it’ll help to keep min distance as you always take most recent one.
Time Complexity: O(N * sqrt(500))
My solution: here

3 Likes
3

Thanks .

4

I don’t know why A[i] \leq 500, it can solved for A[i] \leq 100000 also.

5

by same approach ?

6

Note that when A[i] \leq 100000, then you can prime factorize the numbers in O(N*max(log(A[i]))), after that we would use hashing. Suppose for a particular number A[i], prime p occurs odd times, then add 2^j modulo mod(j is position of prime) to its hash values. For example if p = 2, then j = 0. And if p = 3, then j = 1. You can use hashing function like 2^p also.
Now note that if A[i] and A[j] can form a possible pair, then the hash value would be same. After that, use @souradeep1999 logic on tree.
My code: CodeChef: Practical coding for everyone
I have not added the O(N*log(A[i])) part because I realized it later but I think idea is clear.

7

Seems cool and it’s correct.

1 Like
8

Can anyone suggest more problems like this?

9

Bro please tell the dp for last problem. I am not able to solve it.

1 Like
10

Till now I’m not upsolve it, may be at night I’ll do that. So the rough idea is,
Our dp state will be N*2^M*3

  1. dp_{i, mask, 0} = We are at index i and didn’t take any element till now. (obviously mask will be 0).
  2. dp_{i, mask, 1} = We are at index i and we take some element till now and the set bit in mask denotes that those value from B array we’ve taken so far.
  3. dp_{i, mask, 2} = We are at index i and we won’t take any elements from i onwards. Here you can directly return as base case by checking if mask is 2^M-1 or not.

Will share the solution link by tonight.

11

Good Explanation… Thanks