You are not logged in. Please login at www.codechef.com to post your questions!

×

Partial Submission of CHEFSUM

problem statement--- https://www.codechef.com/SEPT17/problems/CHEFSUM
my solution ----- https://www.codechef.com/viewsolution/15187157

how can i edit my code so that it can perform second subtask also

asked 17 Sep '17, 14:11

chopper_pkg's gravatar image

2★chopper_pkg
1
accept rate: 0%


You are using a brute force approach whose complexity is n^2.By understanding the question you can solve the solution in O(n). We can observe that val[i] is used in both prefix(i) and suffix(i). Total sum of prefix(i) +sufix(i) will be equal to sum of array + val[i] (val[i] is in both prefix and suffix). So to minimize the sum we have to find the index( convert the index to 1-based) with minimum value.

link

answered 17 Sep '17, 14:35

nrz_2's gravatar image

3★nrz_2
1
accept rate: 0%

ok but after doing that it only reduce the complexity of the program but i want to know how can i edit my code so that i can take constraints 1 ≤ N, A[i] ≤ 10^5

(17 Sep '17, 15:09) chopper_pkg2★

You can use prefix_sum and sufix_sum array calculated before hand so that u dont need to do it every time it will reduce your complexity of your code from O(N^2) to O(N) here is my solution

link

answered 17 Sep '17, 16:45

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

try to do complexity low as O(n^2) won't work.so try to make it in O(n). https://www.codechef.com/viewsolution/15191274

link

answered 17 Sep '17, 19:44

tutejahimanshu's gravatar image

1★tutejahimanshu
412
accept rate: 33%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×26

question asked: 17 Sep '17, 14:11

question was seen: 330 times

last updated: 17 Sep '17, 19:44