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

×

doubt-any help????

solution link:https://www.codechef.com/viewsolution/14156262 problem link:https://www.codechef.com/problems/COINS what is wrong with the solution?

asked 08 Jun '17, 16:46

viralivora's gravatar image

4★viralivora
1838
accept rate: 14%


You are doing a basic error.

Lets say the coin value is X.

We see that X/2 +X/3+X/4 is greater than X. Good! But we can further break that X/2 , X/3 and X/4 into even smaller pieces such that we get more coins.

Eg- lets take X=100

We get coin 50,33,25.

Now we can divide 50 to- 25, 16,12.

Similarly we can do to 33 and 25.

Meaning, you have to do the process on and on, until dividing into smaller coins yields no profit. (Maths will show that this for X<=12 , we get no profit)

What you will ahve to do is recursion +memonisation.

But how will you store the values? (As such large array isnt possible)

In C++, there is a data structure called maps. Its speciality is that, you can define the "key" by which you will access the element. So when you say map[x]=x, it will store x and make a key "x" to access it. (Do some research on it if needed)

OR

You can just store results for values <=10^7 or 10^8 in array and still happily solve the question. Get back to me if doubt exists.

link

answered 08 Jun '17, 17:45

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

This is a basic dp question and here is my accepted solution

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

if you still have any doubt then feel free to comment

link

answered 08 Jun '17, 16:52

hruday968's gravatar image

5★hruday968
1.7k210
accept rate: 14%

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:

×349
×302
×65

question asked: 08 Jun '17, 16:46

question was seen: 351 times

last updated: 08 Jun '17, 17:45