Sort 8 Discussions, By:
Please Login in order to post a comment
shouldnt this be rather under Number theory???
This was an interesting problem with a good editorial and I learned a few things. However I really wish the test cases were not designed to take 90%-95% of the allowed runtime. I'd rather think about algorithms with decent asymptotic running times rather than optimize to save microseconds here and there.
Completes in under .40 secs for me in C++. Possibly your GCD is slow.
Got 0.26sec in C++. Solved in O(2^N * (Q + log a[i])). I have no idea to optimize more.
can be done in O(N*2^N + M*2^N)~ O(M*2^N)
Precompute the odd and even sized subsequences and put it into two arrays named odd and even.( O(N*2^N+2^N))~ O(N*2^N)
Now go through D queries and in each instance add the odd values and subtract the even value from variable TOTAL as per the range mentioned . (O(M*2^N))
Has anybody got a link to the mathematical theory behind this problem? Individually testing each number in the number range just doesn't cut the mustard.
I even pruned the coin list by deleting all multiples from it (if a price is divisible by 10 then it is also divisible by 2 or 5 so the 10 is not needed) but with up to 10^20 sets of prices, just running an empty loop would probably cause a timeout.
Awesome problem. Loved it, though messed up in calculating lcm. :P :D
It's failing on the 12th test case: https://www.hackerrank.com/challenges/mehta-and-the-typical-supermarket/submissions/code/46267071
You need to handle overflow. long won't work in that case. if lcm > 1e18 don't multiply, and no need to consider that one either.
The 12th case also presents the coins out of order, so be careful you're not relying on the coins being presented in order (for pruning reduntant ones, for example)
can someone explain the compute() part in the editorial?
Now, since we have been given queries, we can simply precompute all the possible subsets along with their bitcount modulo 2, and perform the required calculations as mentioned above for all given queries.
why do we need to do this in this problem?
No more comments