Hii there,in the Question “Too Much Sweetness”, during the contest I tried this approach
Algo:
Generate all the 2^N permutations containing 1 and 2.
-check every permutations if it satisfies all conditions
if yes cnt++;
this approach has Time complexity = O(2^N)
for subtask 2, N=p+q<=20 so TO(2^N) = 10O(2^20) = 10^7(approximately)
so this solution should pass subtask 1 and 2.
But my solution is clearing only subtask1 and give TLE for the second.
my code :CodeChef: Practical coding for everyone
Plz help me to rectify this.
I have never implemented Persistent Segment Tree. So, it would be better if you could either share your approach in detail, possibly accompanied by implementation if possible.
To understand it more clearly,u could assume that there are N segment trees for each combination (1 for each node) where N is the number of nodes in tree which store the valid edges along the path from root to that node.Persistent just helps to use previous things (as u could see for a node v the segment tree would be the same as its parent except that only edge[v][parent] is not included in parents segment)
I know there can be many optimizations, but i happened to keep my solution simple.
And by the way, your statement proves that only those certain states will be visited where for example N = P-p+Q-q. My solution, technically won’t visit such states.
Yeah, your optimization is really helpful for reduction of dp table size, but i happened to use map, which solved my problems.