problem link: http://www.spoj.com/problems/INGRED/ my code: https://ideone.com/H30OGG
so im having troubles with this problem, my approach using dp: first i represent S as a mask, where if the I'th element of mask is on, it means that we have not visited store at city s[i]
firstly run Floyd-Warshall to get all distances between two cities
dp[x][y][mask] = minimum distance needed to get all S ingridients, with person A at city x, person b at city y, and the mask
if person A lives in city A, person B lives in city B, and there are SS ingridients, the answer is dp[A][B][(2^SS) — 1];
so i made recursive function solve(x,y,mask,dist)
x= position of person A, y= position of person B, dist = distance so far
then i just check for each bit that is on in the mask, assign person A or person B to get it..
but i got WA... cant seem to find where i did wrong. any help?
still needs help...
I think that, in your dp, since you may travel a certain road s times (once for each level of the dp), you might be overflowing int. Also, in case that doesn't work, you might consider an alternate approach: for the input sizes given, (2^s) * n * n ~= (s!) * s (actually, the second one is smaller). Therefore, you could take all possible permutations of visitable cities, split them at a point, then verify the cost of the respective tours. Asymptotically it is worse, but for the input sizes given, it is equivalent, and possibly simpler to implement.
First of all, I think regular permutations would suffice since S<=8, but of course DP with bitmasks works quicker.
However, what you've implemented is not exactly DP — it actually behaves more like a greedy. Once we reach a terminal state with mask=0 you set the current value of dist to it, assuming it's the best one — but it might not be.
To implement such recursive DP you need to change some stuff. As you said:
dp[x][y][mask] = minimum distance to get all ingridients (not yet taken), with person A at city x and person B at city y.
So, what is dp[x][y][0]? It's 0. We obviously got all products so what more to get? Then what is the formula for dp[x][y][mask]? Well, we pick one guy to go to some of the free shops, so it would be:
dp[nextshop][y][newmask] + cost[x][nextshop] or dp[x][nextshop][newmask] + cost[y][nextshop]
for all possible unvisited shops.
And that's it. Here is your code modified to get AC.
thanks!