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

×

what does it signify " sum of n over all the test cases"..????

I have seen this condition in some question like "sum of n over all the test cases <=10^6"... what does author wants to tell us with this condition..??(how can we use this condition in our solution ?) http://www.codechef.com/problems/DEVSTR

asked 20 May '15, 01:25

va1ts7_100's gravatar image

3★va1ts7_100
4721730
accept rate: 11%


In that example, 1 ≤ T ≤ 10^5, 1 ≤ n ≤ 10^5. Without that constraint, you'd be looking at the worst case scenario, T=10^5, and in every case n=10^5. If the program were to run in O(n), it would take 10^10 iterations to solve the entire test, which is not feasible in under 2 seconds.

The condition serves as a clue: Because you have to process an overall input size of 10^6, you're likely going to be looking for an O(n) solution.

link

answered 20 May '15, 12:11

jlrz's gravatar image

4★jlrz
26
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:

×304

question asked: 20 May '15, 01:25

question was seen: 3,831 times

last updated: 20 May '15, 12:11