# SHOPTRIP : Recursive DP gives WA

Problem My approach is similar to that in editorial except the implementation where I have solved it recursively and it passes sample case but gives WA. Can anyone find the problem in my code or give any test case for which it gives WA ?
My solution

1 Like

Recursive solution

Note:

1. Dist(i, j) means distance between ith and jth location, using euclid distance formula.

DP state: last position i visited (i == 0 means home kitchen, else ith position) and mask M, representing ingredients selected.

Base Case: All ingredients selected. return dist(i, 0).

Recurrence Relation: Suppose we are at ith position, with mask M ingredients selected.

For all j , if mask[j]|M != M (means we get a new ingredient by visiting jth position),

ans = min(ans, dist(i,j) + solve(j, M|mask[j]));

This way, we have also avoided cycles, as we will never visit same position twice, because all ingredients will be present in mask M after first visit.

Also, use map (preferably unordered) to avoid recomputation of state defined by position i and mask M.

solve(0,0) will give us our answer.

Oh sorry, I forgot to give my code. And using maps would give TLE.

My java solution ran within 0.57 seconds using mapsâ€¦

I guess it wonâ€™t give TLE, just because of that.

Give a look to my solution mateâ€¦

Okay sure. But can you find problem in my solution it does not use any map and my dp states are using ingredients mask with last shop visited.

@taran_1407 I have done exactly the same thing, still I am getting WA.

1 Like

Sorry for delay, I have been busy all day since my last reply.

Now Iâ€™m implementing it in c++.

Thanks. But you can look at my code that I have posted in question and it does not use map.

Friend, i found a recursive C++ implementation for this problem https://www.codechef.com/viewsolution/16311283

I too had written a complete recursive solution, but kept on getting RE (because of string input).

Of course it can be solved recursively but I want to know what is wrong in my code and the code you gave is almost identical to mine.

Finally Found the error in your solution!!!

Hereâ€™s the corrected version https://www.codechef.com/viewsolution/16628037

Your mistake was, to take dp[5000][15] instead of dp[5000][40] since N can be upto 36. I guess you mixed it with constraints of K.

Further, in your loop where You set dp[i][j] = -1, run loop upto 40 instead of 15.

I made a few other changes, which are (though i guess they arenâ€™t necessary)

1. Using separate dist function instead of inline calculation, to simplify.
2. When i input string, i reversed it, to simplify mask creation, and used bitwise OR to turn on jth bit. If you donâ€™t know about bitwise operations much, refer this.
3. I used int for fl instead of bool, because i donâ€™t know about behavior of bool in c++.
4. Slightly edited printing part.

I think that only the dp part was giving WA.

Thatâ€™s allâ€¦

2 Likes

Thank you so much for giving your time and finding error @taran_1407. I wasted a lot of time behind this and I just needed to change size of dp array, but I am surprised it did not give segmentation fault, otherwise it would have became easy to find out error.

Segmentation fault was not shown because when accessing 2-D array dp[i][j],it is done as base-address + (i*size of column) + j and since I had used more space then required index never went out of range and hence no segmentation fault.

Even im suprised that i found duch bug. Im not muchin C++, and in java, you would have got index out of bounds.

Got to learn something new about segmentation in c++

I had noticed this , 15 in place of 40, but thought that verdict would be RE, had it been segmentation faultâ€¦

Yes in c++, if you have array of size 10 and you ask for element at index 15 array[15] it will not give you index out of bounds error like in java instead it will give you some random number.

1 Like