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âŚ
You may refer this solution. CodeChef: Practical coding for everyone
I know this is not the best implementation and probably complex than other ones mentioned above, but i had implemented it this way, so i shared. This one use dp table instead of map, thus doesnât use hash.
thanks but currently i donât know java. So, if possible please explain the dp states.
P and Q are number of sweets left in bag 1 and 2 respectively, B mean number of times box can be opened, and cur is the current box to be opened.
count0 and count1 has only one difference, see the recursive call, count0 calls with B-1 when cur is 1 while count1 calls with B-1 when cur is 0.
isnât it O(50^4) because you are looping for building each dp states!