@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.
What is the complexity for F(n) ?
Can you explain how you’re excluding the solutions with z_i \ge S_i? Is it possible to do that by fixing some i elements such that S_i \le z_i \le p and excluding those solutions?
1 Like
Well, i too tried centroid decomposition but couldn’t formulate the idea properly.
Would be a lot better if you could share your implementation with us.
I checked the constraints of p, q, B1 and B2 and choose 201. To get a better idea, consider a grid with n rows and M columns. Each cell can be uniquely represented as i*M+j where i and j are row number and column number respectively.(0<= i <N, 0<=j<M).
I used same hash for multiple variables.
1 Like
Yes, ur solution for strange function is very neat and simple. But i believe its and overkill here. My approach can also be applied where F(X) is “strangely” defined, say any unique property.
I liked ur solution of too much sweetness, but it requires good knowledge of combinatorics which even i dont possess. Ur solution has better time complexity, but mine is widely applicable. 
I cannot surely say, but i suspect ur hash function to be faulty. Consider ur has function for 2 pair of values (1,111) and(11, 11) both will have hash value “1111”.
Conclusion: your hash function is poor.
1 Like
Initially I thought of keeping the constraints so as to pass only solutions of order 50^3 (4 states) but then I changed it so as to pass 50^4 (5 states) also. I didnt know about the 50^2 solution and also of the combinatorics solution. Its good to see people coming up with so many different ideas.
Thanks man! Understood where I went wrong. Changed the hash function to b1+201*(b2+201*(p+201*(q)))+last; Using an unordered hash map and a hash of numbers instead of strings removes the TLE. The new hash function removes the WA. Got AC! Only if this has dawned on me during the contest time :\
Could you give further insights as to how you chose the hash function like this? A hash function of p+201*(q+201*(b1+201*(b2)))+last; fails even for the sample test case. What’s the difference?
Wow. the concept is really is good. I used to struggle a lot with these DP problems.
It would be really helpful if you can link few more problem of the similar type.
I remember reading an editorial written by @likecs where he had hashed a bitmask, and grid coordinates this way.
Nice one… Though an overkill…
You didn’t multiply p+201(q+201(b1+201*(b2))) by 2 before adding last. This causes collisions in your hash values. There must be atleast two different tuple (p,q,b1,b2,last) which give same hash value.
But dont you discuss with the coordinator or someone(atleast testers) regarding your solutions or questions .
@teja349 Yes we do discuss the problems as well as the solutions. But if you see to it around 5% (of the total participants) got 100 points and that was the difficulty which I intended to put up for the 3rd problem…so that way it was fine.
plz format the test case accordingly…