Recently, I came across this problem which I have worded below

k-Subset Sum You are given an array A[] of positive integers containing N elements. Now you need to form a new array containing K elements from the given array A[] and also its sum should be equal to S. Also the newly formed array of size K should be lexicographically minimum.

Constraints

size of the given array A[] (<=10^5).

integer K , size of newly formed array (<=10^5).

sum of newly formed array (<=10^5).

S , sum of newly formed array (<=10^5)

My Approach

It looks like a dp problem to me where at each index 'i' , I have to decide to either pick or leave behind the item, and then possibly backtrack to find the answer. I was only able to come up with the state dp[i][j][k] : is it possible to reach ith index having collected j items which sum up to k.

I didn't go forward with approach since this will surely give TLE O(n^3) and n~~10^5

Hello , i was having trouble understanding uva 11080 Place The Guards.

My idea is that if each the connected components is of the form NODE-->NODE-->NODE-->... and so on , and the number of nodes are even then it is possible to place the guards , but this seems to be giving me WA .

Also this question was tagged under bipartite graph check , so if someone could explain that angle of looking into it too , it will be appreciated ,

thanks

THE QUESTION (not really required)

http://www.spoj.com/problems/BLMIRINA/1

MY ANSWER****

http://ideone.com/SbYs7J

PROBLEM****

the answer should be 6 decimal places , for the TEST CASE

1

179 56 56

ACCEPTED ANSWER = 147.084601 102.015294

MY ANSWER = 147.084593 102.015289

As you see , it is only a minute difference and depends on technique used for solving a problem...any suggestions to get around it .