Apology to ask but what I don’t understand that the answer should have two function that calculate the sum of first i numbers of the array and sum of last N - i + 1 numbers of the array. However, the answer I have seen in this forum doesn’t have any function and neither performing this iteration.
Any clue, what I am missing or am I off-track?
Thanks in advance…
P.S.
link: CHEFSUM -Editorial. Just look at the quick explanation and this is my answer that I submitted.
Please include some related text and links… It will be really helpful then…
Lets take an example: A = [3, 2, 1, 4, 5]
Here, lets take the presum(i)+sufsum(i) for each i. presum(0) = 3 and sufsum(0) = 3+2+1+4+5.
Similarly, presum(1) = 3+2 and sufsum(i) = 2+1+4+5.
You may notice that for each i, presum(i)+sufsum(i) = sum of all elements+A[i]. Sum of all elements is always constant for each i, to minimize presum(i)+sufsum(i) you need to take the i such that the ith element(A[i]) is minimum. Thus, the problem reduces to finding the first occurrence of the minimum element in the given array A.
You may want to take a look at the editorial: https://discuss.codechef.com/questions/110216/chefsum-editorial
1 Like
It helps and that’s the smart move but I code in the straight way like calculating the presum and sufsum and then find the minimum index. I guess it should be accepted. shouldn’t it??
It should be, if you code it right
Naively calculating the prefsum and the sufsum will get timed out. You may want to store them in another array or something.
@ista2000 You mind if you take a look into my code. Only hints would be really appreciable.
Why does your code have 2 int main()
:o
Some things to remember-
- Prefix and Suffix sum of the array doesnt change. All you need to do is to make 2 arrays, prefixsum[n] and suffixsum[n] , where prefix[i]=prefix sum till index i and so on. This way you dont have to re-calculate those things again and again. This is to tackle TLE in larger test cases.
- The element in prefix[i]+suffix[i], element arr[i] should be getting included twice. Make sure you are accounting for that!
- Try to universally follow either 1 based or 0 based indexing. Dont switch between, its not a very good programming practice.
- Why is your array B unsigned char instead of int or long long?
You are indeed doing it in a naive way and that’s why you get TLE in the second subtask. As for the first subtask, it maybe an implementation bug. As @vijju123 already pointed out, you are switching between 0 and 1 indexing which is causing some logical errors.
One of the mains is within #if 0
:3
I know that, I am asking why did he do that. Do you know how difficult it becomes to read such codes?
First I tried to rum my code and after some unsuccessful attempt, I copied the code from the submitted answers and execute them… Thanks for the feedback. I will look into this…
I see issues with your arrays being unsigned char data type. Try changing them.