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

×

TLE in OJUMPS

hey i'm getting TLE in ojumps and i cannot find the problem in the code pls help . the question is http://www.codechef.com/problems/OJUMPS

the code is.......

inp = int(raw_input())
i = 1
y = 0 
p = 0
while y<=inp:
    if y==inp:
        print "yes"
        p = 1
        break
    y = y + i
    if i==3:
        i = 0
    i+=1
if p==0:
    print "no"

thank you :)

asked 24 Jul '14, 22:18

dpmittal's gravatar image

3★dpmittal
26115
accept rate: 0%


you are unnecessarily making use of loop in the problem .Remember that a can be as large as 10^18,which can result in 10^18 operations if you use loop (since your time complexity is o(a),which is the reason for tle.

Instead a simple implentation like the foll with 0(1) complexity would suffice.

Psuedo Cde:

get input a

a=a%6;

if(a==0||a==3||a==1)

print("Yes")

else

print("No")

if you find my post helpful upvote and mark it as accepted answer.CHEERS HAPPY CODING :)

link

answered 24 Jul '14, 22:40

prem_93's gravatar image

3★prem_93
6233816
accept rate: 19%

edited 24 Jul '14, 22:42

I think you are using brute force in solving the problems. yesterday i had answerd a question on your doubt regarding the prob:"PLZLYKME",where you had used a similar brute force kind of approach. Dont always fall into brute force,there is always scope for optimizations at any level."optimisation is a virtue of a good programmer",So always try to better your approach (keeping in mind the time consraints as well) which will help you in the long run. CHEERS HAPPY CODING:)

(24 Jul '14, 23:02) prem_933★

The constraints on a (inp in your solution ) are a<= 1018
Your solution is of O(a) complexity. So, it will not pass the test cases in the time limit specified.
Try some other logic.
You can refer to the editorial : http://discuss.codechef.com/questions/42547/ojumps-editorial
If you still have any problem, comment below.

link

answered 24 Jul '14, 22:28

pratku123's gravatar image

4★pratku123
1.8k4932
accept rate: 14%

edited 24 Jul '14, 22:32

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:

×717
×122

question asked: 24 Jul '14, 22:18

question was seen: 937 times

last updated: 24 Jul '14, 23:02