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
Friend, first thing, share your code link.
Note:
- Dist(i, j) means distance between ith and jth location, using euclid distance formula.
- mask[i] means mask at ith position (1-based indexing, mask[0] = 0.)
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.
Feel free to ask anything.
Finally Found the error in your solution!!!
Here’s the corrected version CodeChef: Practical coding for everyone
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)
- Using separate dist function instead of inline calculation, to simplify.
- 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.
- I used int for fl instead of bool, because i don’t know about behavior of bool in c++.
- Slightly edited printing part.
I think that only the dp part was giving WA.
That’s all…
2 Likes
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.
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 CodeChef: Practical coding for everyone
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.
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