We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Nice solution ... I thought the greedy solution would have worked ... but like you pointed out, it doesn't. Want an example (and the process on deriving such an example) where the greedy soln doesn't work? Here we go:
==========
Let T(i) be minimum no. of steps for N=i.
1) Manually fill in the minimum no. of steps for some values of N, such as N = 0,1,2,3,4,5,6
2) At this point, you notice: T(5) > T(6)
Hmmm... this is the first hint towards the fact that a greedy solution may not be good.
Notice that this is because for all prime numbers "p",
T(p) = T(p-1=even number) + 1
3) Building on this idea, we try to find a number such that we can confirm our hypothesis. How about we try 30 = 5x6 ? Hmmm, This won't help in finding an example to conradict the greedy method , because we are looking for an example such that
N = max(a1,b1) = a1 (just for example)
N = max(a2,b2) = b2 (just for example)
and min(a1,b2) = a1 (just for example)
but T(b2) < T(a1).
4) How about we try some multiples of prime numbers (like 5 in our case) ? Why you may ask, so that we can factorize it and redistribute it to the other factor to make it bigger (so that the other factor is chosen when taking N = max(a,b) ?
Finally, we arrive at an example. We try (for N = 60):
Factors1: **10 x 6 **(why ? Because 10 is multiple of prime number 5)
Factors2: **(5x2)x6 = 5x12 ** (redistributing the "2" makes the second factor "6" from previous example into a bigger number and makes first factor smaller)
What happens now when N=max(a,b) for both and we choose minimum (greedy metdho) of the two maxes ? We get N = 5, which is worse than N = 6.
===============
Hope the explanation was clear. this was my thought process when trying to find an example for contradicting the greedy solution after reading this discussion forum. Ofcourse I myself made the mistake of writing the greedy solution when I first tried solving this question.
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
Nice solution ... I thought the greedy solution would have worked ... but like you pointed out, it doesn't. Want an example (and the process on deriving such an example) where the greedy soln doesn't work? Here we go:
==========
Let T(i) be minimum no. of steps for N=i.
1) Manually fill in the minimum no. of steps for some values of N, such as N = 0,1,2,3,4,5,6
2) At this point, you notice: T(5) > T(6) Hmmm... this is the first hint towards the fact that a greedy solution may not be good.
Notice that this is because for all prime numbers "p", T(p) = T(p-1=even number) + 1
3) Building on this idea, we try to find a number such that we can confirm our hypothesis. How about we try 30 = 5x6 ? Hmmm, This won't help in finding an example to conradict the greedy method , because we are looking for an example such that
N = max(a1,b1) = a1 (just for example) N = max(a2,b2) = b2 (just for example)
and min(a1,b2) = a1 (just for example) but T(b2) < T(a1).
4) How about we try some multiples of prime numbers (like 5 in our case) ? Why you may ask, so that we can factorize it and redistribute it to the other factor to make it bigger (so that the other factor is chosen when taking N = max(a,b) ?
Finally, we arrive at an example. We try (for N = 60):
Factors1: **10 x 6 **(why ? Because 10 is multiple of prime number 5)
Factors2: **(5x2)x6 = 5x12 ** (redistributing the "2" makes the second factor "6" from previous example into a bigger number and makes first factor smaller)
What happens now when N=max(a,b) for both and we choose minimum (greedy metdho) of the two maxes ? We get N = 5, which is worse than N = 6.
===============
Hope the explanation was clear. this was my thought process when trying to find an example for contradicting the greedy solution after reading this discussion forum. Ofcourse I myself made the mistake of writing the greedy solution when I first tried solving this question.