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.
PS: Thanks
Sorry i too couldnât implement it due to lack of time,if u wanna read it refer this: https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/
Didnât expect a Combinatorics solution for this problem.
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 too tried this, but forgot to consider ans == 9 case and got many WAs.
1 Like
Can you explain the logic behind this?
Yeah,I too didnât expect a combinatorics solution. Infact I think DP solution is quite simple.It was an overkill I suppose 
.
Great editorials btw! 
To be frank, i didnât think about time complexity, but implemented it because i had an intuition that this will be accepted.
Theoretically, worst case complexity should be around 50^4, but i donât think this limit is actually achieved in any test case.
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.
Very nice. But this means that the time limit is very very lenient, I wonder why.
@meooow, my solution would be costly had i used dp table. But by using map, i didnât visit those states. Therefore, there might be only slight difference in runtime i guess.
F(A^n)=F((F(A))^n) so i calculated F(a) now only possible values of a are from 0 to 9 if it is 0 or 1 the f(a)^n will be only 0 and 1 respectively. if it is 3 ,6 or 9 the if n==1 then it will be 3,6,9 respectively else it will be 9. for 2 and 5 it repeat the patter of sum. the pattern of sum for the powerâs of 2 is {2,4,8,7,5,1} ans for and sum pattern 5 is {5,7,8,4,2,1} ans similar for 7 ,8,4
I explained it as a reply as it wasnât fitting in a comment :v
@taran_1407 itâs not about that, my comment was for @teja349. By his optimizations, the complexity comes to \mathcal{O}(p^3). Actually it can be reduced further to \mathcal{O}(p^2 + N^2) by considering box 1 and 2 separately as I have done in my solution (not optimal). So in the worst case iterations required is in the order of 10^4 only. Whereas there were 10 test cases with a time limit of 3 sec!
OhâŚ
I thought you was saying that about my solution.
And Yeah, i too wondered, because when i read problem statement, i expected p+q upto 1000.