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

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.