Hackerearth had it's version of long challenge which ended yesterday. It had this problem. I wonder if hackerearth or may be any site hosting competitive programming test the limits for questions for most languages. This question seems to be written in such a way (not intentionally) that it can be only solved using c++/c only. For java, the memory limits seem to be insufficient. I would like to see a solution written in java.

I recently had to solve this problem for a test, but was not able to find an efficient solution for the same.

Is it possible to make 'n' insertions to a linked list efficiently when we are given the positions of all insertion, and the element which has to be inserted.

Eg: position = [0,1,2,1,2] , elements = [5,6,7,8,9], list = []

So basically the operations we would be doing are

1. add 5 at 0th index in list => list = [5]
2. add 6 at 1st index in list => list = [5, 6]
3. add 7 at 2nd index in list => list = [5, 6, 7]
4. add 8 at 1st index in list => list = [5, 8, 6, 7]
5. add 9 at 2nd index in list => list = [5, 8, 9, 6, 7]

So the final list would be [5, 8, 9, 6, 7]

Does anyone know an efficient solution for the same? (better than O(n^2)) In the original problem the elements to be inserted are between 0 to n-1

I would like to what makes these 2 solutions different for which first solution is getting TLE but second solution is able to solve the question in around 3.5 sec ? Link1 : 49967236 Link2 : 49899826

I would like to know if we can solve 1023D - Array Restoration like this....

change any zero to a non zero value just to its left (or right, doesn't matter), check for occurrence of value "q" in the array, keep track of li and ri as index of first and last appearance of i in array for all possible i given in array and then for every "i" in the array check if there is a value less than i (let that be j) in the array in index range [li, ri] . If such a value exists then we can say that such an array cant occur because query with j < i will always happen after jth query so there can be complete overlap or partial of ith query over jth query and not vice-versa....

I think this a sufficient condition for the solution but I m not able to get ans.... (solution link : 42340677)

I would to like to know for some flaw in the solution or counter example for the same (explaining the flaw)

Thanks in advance!!!

Can somebody help with my code for 914D? Link:34413402 I would like to know what is the problem in code for query in segmentTree or anything else? (I hope the code is understandable)

Can this problem be solved by sqrt decomposition?