CHEFSUM answer issue

general
#1

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.

#2

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
#3

Why does your code have 2 int main() :o

Some things to remember-

  1. 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.
  2. The element in prefix[i]+suffix[i], element arr[i] should be getting included twice. Make sure you are accounting for that!
  3. Try to universally follow either 1 based or 0 based indexing. Dont switch between, its not a very good programming practice.
  4. Why is your array B unsigned char instead of int or long long? :confused:
#4

Please include some related text and links… It will be really helpful then…

#5

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??

#6

It should be, if you code it right :slight_smile:

#7

Naively calculating the prefsum and the sufsum will get timed out. You may want to store them in another array or something.

#8

@ista2000 You mind if you take a look into my code. Only hints would be really appreciable.

#9

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.

#10

One of the mains is within #if 0 :3

#11

I know that, I am asking why did he do that. Do you know how difficult it becomes to read such codes?

#12

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…

#13

I see issues with your arrays being unsigned char data type. Try changing them.

#14
#15