# Mehta and the Typical Supermarket

# Mehta and the Typical Supermarket

harshnigm + 0 comments shouldnt this be rather under Number theory???

marcv81 + 1 comment 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.

mrussotto + 1 comment Completes in under .40 secs for me in C++. Possibly your GCD is slow.

square1001 + 1 comment Got 0.26sec in C++. Solved in O(2^N * (Q + log a[i])). I have no idea to optimize more.

DrManhattan + 0 comments 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))

gschoen + 0 comments 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.

rofi93 + 0 comments Awesome problem. Loved it, though messed up in calculating lcm. :P :D

akhilhello + 2 comments It's failing on the 12th test case: https://www.hackerrank.com/challenges/mehta-and-the-typical-supermarket/submissions/code/46267071

rofi93 + 0 comments 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.

milkshakeiii + 0 comments 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)

not_acceptable + 0 comments great problem!

nitishingde + 0 comments can someone explain the compute() part in the editorial?

cbuff + 0 comments 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

Sort 8 Discussions, By:

Please Login in order to post a comment