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

×

Solution taking higher time on small contraints

I recently solved a question where my algo has complexity of O(N).

Surprisingly, on constraint where N<=1000, Solution takes 0.97 seconds ; but on constraint where N<=100000 ; it takes 0.00 seconds (C++ Solution). Why is that happening...??? And even why at a constraint of N<=1000 ; solution is taking nearly 1 second time even in C++ ?

This is the link to My Solution for this problem

I have recently began to upsolve problems in C++ and am new to language... Please help...

asked 13 Dec '18, 17:45

ritesh1340's gravatar image

3★ritesh1340
17018
accept rate: 11%


It actually took me a while to figure it out why the hell is this happening for smaller test cases .

But if you see it clearly then 0.97s is for 70 pts.

The subtasks are placed in wrong order in your submission page .

https://www.codechef.com/viewsolution/21917673

link

answered 13 Dec '18, 22:10

raj_13's gravatar image

4★raj_13
662
accept rate: 42%

okayy I got it... Thanks a lot.

But one extra thing @raj_13 ... Could you please help me understand that if my code had a complexity of O(N) ; and constraints N<=100000 ; why even the run time goes nearly to 1 second...???

I am trying to shift to C++ because it is way faster than python. But even that seems quite slow...

Please help

(14 Dec '18, 00:27) ritesh13403★

Whenever adding a character to a string use '+=' operation i.e.

ans += "B" instead of ans=ans+"B"

First operation just adds character B to the string whereas the second operation makes a copy of first string, adds character and then assigns to the original string. Therefore your code might look like O(n) but its not.

link

answered 14 Dec '18, 00:50

alpha_q2's gravatar image

5★alpha_q2
17116
accept rate: 16%

1

thank you @alpha_q2

I didn't knew the difference between ans += "B" and ans=ans+"B"

Finally Had a fast submission and learnt something new... THANKS :)

(14 Dec '18, 01:09) ritesh13403★
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:

×205

question asked: 13 Dec '18, 17:45

question was seen: 172 times

last updated: 14 Dec '18, 01:09