Could somebody tell me how to solve specops and subset sum?
@jaskaran_1 For SPECOPS there is already a post with two ways to solve the question here : http://discuss.codechef.com/questions/37555/specops-codex for subset sum : This question can be solved using a DP solution where dp[i] will represent that using numbers up till index i all numbers till dp[i] can be made i.e if dp=4 then using elements with indices 0,1,2,3 we can make all numbers till 4(I have sorted the array before I construct the dp). So for any index i it is known that all numbers upto dp[i] can be formed then including the (i+1)th index we get the new numbers that can be made are a[i+1],a[i+1]+1,a[i+1]+2…a[i+1]+dp[i] so what happens if dp[i] is less than a[i+1]-1, then the number a[i+1]-1 can never be made hence the answer will become NO if dp[i]<a[i+1]-1, otherwise dp[i+1]=dp[i]+a[i+1] as all numbers till here can be made using indices upto i+1. Also if the array has more than 1 element then a has to be 1 otherwise there will always be an index i(i<total elements) such that (sum till i)+1 cannot be made.
@amitrc17 , i have a doubt for this test case 4 2 2 2 2…Would you please clarify this… what if there are duplicate elements??
For “Subset sum” problem what is basic idea behind the solution?Is it a observation or anything else? Please tell.