First and foremost I apologize, I don’t know the rules about asking questions here. So forgive me if it is not valid, and let me know. I will make appropriate changes.
I had tried solving the August Challenge’s Simple Queries problem. I am not aware of the STL and the data types of it. This is the solution I tried, and it seemed to work with the sample data and the logic I could think.
I do not know where is this failing, it might be an overflow of stack problem. I would kindly like you to help me figure out why.
although i don’t know how to solve this problem but if you are new to codechef and beginner then i wanna say you that this is toughest problem of this contest and it requires advanced data structure and algorithm like persistent segment tree etc.
but if you have knowledge about advanced DS then sorry for this comment
For a high-school(Indian) guy, your coding skills are very good. But you should analyze the time complexity of your problem and compare that to the time limit allotted for the problem.You can refer to the book Introduction to algorithms by cormen for that. Also the WA you are getting is due to integer over-flow in the multiplication operation for calculating the sum.
On a general note, this problem is way out of the league of any common STL or data-types. You should start with simpler update-query problems.
Secondly, why would it be overflowing in the sum variable? I used a long integer. As far as I could search int ranges from -2,147,483,648 to 2,147,483,647. So I assumed long int should be enough. Why would it not be, and in that case, a long long would make the code error (WA) free?
Third, It would be great if you could elaborate upon “way out of the league of any common STL or data-types”
@admin123 I have to admit, I do not have knowledge about advanced DS. And I would like you to kindly tell me, why does it require that complex things when essentially what I wrote is correct (If it is not, How?)
Concerning the range of integers:
long int is defined as having the range from -2,147,483,648 to 2,147,483,647, short int from -32xxx to 32xxx (the last three digits don’t really matter). int is actually not defined by the standard, but today it typically is the same as long (on old machines is used to be short). So long int doesn’t increase your range, you have to use long long (no overflows up to 10^{18}).
You also used the wrong type for n and q. short is not enough to store values potentially larger than 10^5. That’s why your solution terminated after 0.0 for many testcases.
Concerning the problem in general:
the task is deceptively simple. You can get a correct output with a rather straightforward solution as you did. But you will not get anywhere near the time limits for the tasks. This is the real difficulty of the problem and the reason only 10 programmers solved it during the contest. Understanding and using STL-datastructures still won’t pass any task but the first one (neglecting the stupid task that doesn’t have any output). In order to pass the other tasks of the problem you have to implement adequate datastructures of similar or higher complexity than the STL datastructures.
the array b[] is of integer type whose max value is 1e9 + 6. so a product like b[i] * b[j] * b[k] would be of the order ~1e27, so a definite overflow. Typically in these cases you could multiply like
Also the range of long int or int is ~ 2e9, so you need variables temp and sum here to be long long type. 1ll is added to increase the range to long long because b[] is integer type.
There isn’t any STL which can process all the queries in the given problem in log(n) time or at least sqrt(n) time so that you could pass the time limit. You would need some sort of sqrt decomposition method with flexible bucket sizes or some sort of implicit segment tree or maybe a wavelet tree (what the hell is it?).
