hiddentesla's blog

Problem on Spoj problem (INGRED
By hiddentesla, history, 8 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

still needs help...

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply