I'm exercising my dp skills and encountered topcoder SRM 694 dev1 250 problem. Can someone explain how to solve it?
I'm exercising my dp skills and encountered topcoder SRM 694 dev1 250 problem. Can someone explain how to solve it?
# | User | Rating |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 163 |
2 | awoo | 163 |
4 | TheScrasse | 154 |
5 | nor | 153 |
6 | maroonrk | 152 |
6 | -is-this-fft- | 152 |
8 | Petr | 145 |
9 | pajenegod | 144 |
9 | orz | 144 |
Name |
---|
I solved it using DP[i][a][b][m] = can I reach state up to student i, where first group has xor sum a, second group has xor sum b and m is a mask that indicates the state for each of the three groups (empty / non empty). Note that sum of third group can be derived from sum of the other two by xoring them with the current prefix xor sum.