Classical Round Table algorithm?
Posted
by
user1795954
on Stack Overflow
See other posts from Stack Overflow
or by user1795954
Published on 2012-11-07T16:58:26Z
Indexed on
2012/11/07
17:00 UTC
Read the original article
Hit count: 383
algorithm
Coins with different value are spread in circle around a round table . We can choose any coin such that for any two adjacent pair of coins , atleast one must be selected (both maybe selected too) . In such condition we have to find minimum possible value of coins selected .
I have to respect time complexity so instead of using naive recursive bruteforce , i tried doing it using dynamic programming . But i get Wrong Answer - my algorithm is incorrect .
If someone could suggest an algorithm to do it dynamically , i could code myself in c++ . Also maximum number of coins is 10^6 , so i think O(n) solution exists .
© Stack Overflow or respective owner