peacebringer167's blog

By peacebringer167, history, 13 months ago, In English

Hi guys, as the title stated, I really need some help with a problem (It appeared in my country's OI years ago). I remember it being a problem on Codeforces, the statement goes something like this:

Given N knowledges, numbered from 1 to N, each knowledge i has a cost of S[i] for you to be proficient in it. There are M tests, for each test from 1 to M, it gives you A[i] money, but it has a set of knowledges that require you to be proficient in all of it. Calculate the maximum benefit, if you learn knowledges optimally. For example,
N = 5
1 2 2 1 3
M = 4
A[1] = 2, knowledge requirements of 1 : (1,2)
A[2] = 5, knowledge requirements of 2 : (2,3)
A[3] = 1, knowledge requirements of 3 : (5)
A[4] = 1, knowledge requirements of 4 : (1)

The maximum benefit will be 3, since you learn knowledges (1,2,3) costs 1+2+2 = 5, and the tests 1,2,4 will give you 2+5+1 = 8 profit — cost = 8 — 5 = 3

Thanks for any help in advance!!!

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by peacebringer167 (previous revision, new revision, compare).

»
13 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I wonder what are the contraints(n m and the sum of set sizes)?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also this sounds like a div 3 past problem(i cant find it)

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The constraints were likely: N <= 1000, M <= 1000.

»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think it's RMI 2017 — Fashion (solution).