pyetwi's blog

ICPC DP Problem
By pyetwi, history, 3 years ago, In English

Can anyone give a solution sketch for this problem? I've been stuck on it for a while and cannot find a solution online. Thanks!

https://open.kattis.com/problems/olympiadtraining

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

Look at each topic separately. Let's order the people from highest time to learn to lowest. The person that has the highest cost "dominates" everyone else, so if the set of people has this person then the cost of this topic is the cost of this person. For the second highest, if the set of people has this person and doesn't have the highest cost person, then the cost is the second highest and so on. More generally, the i-th highest cost person will dominate the set in this topic if no person before it is in the set and the i-th person is in the set.

We can solve that directly by using the same idea as prefix sums for range updates but using "SOS dp" instead of prefix sum. To set up a sum over "subset of X" just sum up the value in the position of the mask X. To set up a sum over "subset of X that has some bit Y", sum up in the subset X and subtract in the subset X-{Y}. Complexity O(N * M * logN + 2^N * N)

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Could you re-explain the SOS dp? I'm probably just weak with subset dp (and unfamiliar with the idea of using prefix sums in SOS dp), but I don't quite understand how to avoid processing all M categories for each of 2^N subsets.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You know how to use prefix sum for adding V in a subarray [L, R)?

      add up V in in position L

      subtract V in position R

      then after doing prefix sum the subrange [L, R) has +V

      Here it's the same thing but with subsets.

      We have a mask of bits and for every submask we want to add up v -> add V in position of the mask, then after using "SOS dp" (I hate that name) to have the sum of supermasks, we've added V in every position that's a subset of that mask.

      Other than that, this problems asks for adding up V in every subset of that mask that has a certain bit active. To do that, add up V in every subset of that mask (by adding up V in the position of that mask) and subtract V in every subset of that mask that doesn't have that bit active (by subtracting V in the position of that mask — that bit).

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is the complexity reasonable given that there are 100 datasets? This one seems to be expected solution of course.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I'd say it isn't reasonable but it's probably the intended solution (and most likely the fastest solution possible for max tests). Some problems do this thing of "Solve this but we won't tell you if we filled the tests with max tests". I've run into a problem that did this once just to learn that it was also in another OJ without cramming every test into a single file and ended up complaining for a week that the same solution that got TLE in practice passed the way the problem was originally set. So sometimes there are online judge restrictions. Usually it's safe to assume in this kind of situation that the setter just isn't that experienced and you can try solving just for one or a few big tests in a file.

      Actually just to make it easier to you I just coded it and it passed in 0.42s :D

      → Reply