Блог пользователя astrocoder

Автор astrocoder, история, 8 лет назад, По-английски

I'm exercising my dp skills and encountered topcoder SRM 694 dev1 250 problem. Can someone explain how to solve it?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.