Dynamic programming problems with bitmasking

general
, ,
1

Hi all,

Please suggest some DP problems that involve bitmasking in the increasing order of difficulty level on any online judge.

Thanks

6 Likes
2

One (EASY)

Two (Medium+)

Three (Hard)

Four (Hard)

Five (Easy, Can be solved without Bitmask)

Six (Easy)

Seven (Easy, Can be solved without Bitmask)

Eight (I dint solve this, Not sure but seeming so)

Happy Coding!

25 Likes
3

And try THIS

4

There is also MARCHA1 (Easy), it has a very nice tutorial about bitmask but can be solved without it

1 Like
5

@anudeep2011:Thanks for the problems. I was trying the problem COURIER on SPOJ.
I am getting WA for this problem. My approach is :
I have used the matrix dp[mask][i] which denotes the shortest distance when request “i” is delivered last among all the requests whose bit is set in “mask”. I have stored all the requests in array src[] and dest[]. Array src[] denotes the source city of request and dest[] denotes the destination city of that request. So if the request is 1 2 2 then these are two requests and are stored individually in the array.Finally, Floyd-Warshall is used to calculate the shortest distance between two cities.
You can find my code here.

It would be very helpful if you could point out where I am wrong.
Thanks.

6
7

@sourabh912

Test case :

1
5 5 3
1 2 10
3 2 13
1 5 3
5 4 2
4 3 1
1
1 2 1

Expected : 29 ( 6 + 10 + 13 )

Let me know if you need my solution!

Edit : Mistake is in Floyd-Warshall

1 Like
8

@anudeep2011 Thanks a lot. I have got AC now :).Indeed mistake was in calculating Floyd-Warshall.

9

im using dp+bitmask for solving the problem http://www.spoj.com/problems/HELPBOB/ . my complexity is O(N*2^N) which seems fine for n=15(max).but im getting tle. please suggest what could be wrong with my code here’s the link http://ideone.com/KwQC2f

10

@sourabh912 @anudeep how to solve this problem i am new to DP with bitmasking please help me to solve this problem http://www.spoj.com/problems/COURIER/

11

@sourabh912 i saw your solution at ideone.com can u expain it i am unable to understand your logic … :frowning:

12

Can someone tell me the better editorial of DP+bitmasking?.. I am trying to understand but still could not get the way~…