Weak tests?
2 Likes
The solution above mentioned is not O(2^N * N) but actually O(3^N).
While calculating dp_2, for each mask a traversal is made on each subtask, which actually gives a complexity of O(3^N - 2^N + 1) as per the given code. Even the tester’s code makes 387158346 iterations for line 48-53. Please check and provide a O(2^N * N) solution if there is possible.
1 Like
How did you simplify the summation to 3 ^ N ?
Nice editorial 
I thought of the bitmask dp method, but couldn’t figure out anything to reduce the complexity!
can anyone tell me why it is O(2^n*n) for dp1 instead of O(2^n).
@student2 First 2^n or (1st for loop) is used for generating all combination of generating bits in binary form and other one (2nd for loop) is used for manipulating these bits i.e., doing manipulation on individual bits!
I hope you get this… otherwise feel free to ask
Thank you bansal.Can anyone tell me what are the submasks and how they can be computed
could anyone explain in dp1 why we are considering to minimize A meals by just reducing 1 meals from B meals.
suppose we have meals 3,4,5 for price 10 and meals 3,4,5,6,7 for price 5 then we have to just take second set price for both set.BTW I solved it by assigning like this but I don’t understand in editorial.
How this statement ‘The thing to notice there is that we iterate from the masks containing the most meals to the masks containing less meals in order to try to reduce their prices.’ holds true? We are iterating in descending order, that does’nt mean that all numbers containing highest number of bits come first. consider 4 and 3. 4 has 1 bit where 3 contains 2 bits
Link to setter’s solution is broken.
Thanks, I updated it and added a description why the complexity of the second part is O(3^N)
You’re right, I made an update and added a detailed explanation for this part.
2^{18}*18 + 3^{18} = 392139081 > 2*10^8, how does it pass within the time limit? Does the present server compute faster than 10^8 operations also?
^^ Same question. I also tried a 3**n approach (which was wrong) but it still gave tle: CodeChef: Practical coding for everyone
Binomial theorem. \sum_{k=0}^{n} \binom{n}{k} \cdot 2^k \cdot 1^{n-k} = (2+1)^n
1 Like
10^8 Operations per s is just a rough estimate. If you have a cache friendly algorithm with simple operations you can get much higher. On the old servers cache friendliness seemed to be paramount. In some problem I computed the transpose of a 1000x1000 int matrix in the straightforward naive fashion. It took on the order of a second!
2 Likes
I think so. Somhow I passed with a barely optimized O(2^n\cdot M) (M being the number of meal combos in the input).
How each mask has 2^(N-k) submasks ?