Sort 9 Discussions, By:
Please Login in order to post a comment
Dang, this one was tough. Anyone able to do this with a single approach? I had to split it into two: one for large L (e.g. L > 1000000), and one for small (<= 1000000).
Nice problem. Learnt a lot about segment tree and use of sieve and recursive approach to pass all test cases. Thanks a lot.
Have been working on the second constraint. My strategy was to first sort the input , and sort the radicals in place according to the increasing . With Python, I couldn't work around the in-place sorting quickly enough (thought of insertion sort, but without pointer it's hopeless).
Then I tried to use the radicals as hash keys, so we won't have to go through the smaller integers again and again (sorting is, after all, at best, which is a lot when we need to do this for every ). But with this kind of hashing, getting the target element is no longer , as we would have to iterate all the hash keys before we hit our target (that makes it I believe). Still not passing it on time.
By the way, I was generating all radicals till aiming for the first two constraints. I think we need to take another approach (iterating on radical and count its occurrences within the upper limit) for the last.
is there a way to get test cases??.I have done some optimizations,but it does not seems to run.Any one able to solve it succesfully.
Can someone please explain to me how 12 is a rad of 6?