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

×

[closed] COINS-TLE why

What is wrong with my approach?

problem
Solution

p.s. The time limit is 9 sec. But I am getting TLE before 6 seconds. Shouldn't the cod atleast run for 9 seconds before giving any verdicts?

asked 19 Jul '15, 13:05

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

closed 30 Jul '15, 12:48

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 30 Jul '15, 12:48


Hi! I tried submitting your solution and found that the problem is because you're pre- processing so many values which is not required for the problem. You can make changes to your solve() function only to get you the result.

You can also see my solution.

link

answered 19 Jul '15, 13:28

ho_oh's gravatar image

3★ho_oh
757
accept rate: 33%

If u are forming an iterative dp solution....and the problem requires the solution for values as large as 10^9... the solution will tle cause it will fill all the states which are not even required to be filled...causing unnecessary computation...so switch to recursive dp solution...which is also called lazy dp solution...as it will only memoize the states which are necessary...thus saving extra computation... :D ..

link

answered 19 Jul '15, 13:40

coolsduy's gravatar image

2★coolsduy
1659
accept rate: 25%

check my solution ...its simple! https://www.codechef.com/viewsolution/6990677

link

answered 19 Jul '15, 19:18

monu7z's gravatar image

1★monu7z
11
accept rate: 0%

Thank you guys. Learnt a new thing :)

link

answered 21 Jul '15, 15:01

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

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:

×65

question asked: 19 Jul '15, 13:05

question was seen: 709 times

last updated: 30 Jul '15, 12:48