dreamoon_love_AA's blog

By dreamoon_love_AA, history, 4 years ago, In English

Hi all.

This week's farm training contest will be held on 3.7 hours later. This week's writer is drazil and tester is me (dreamoon). This week's contest consists of 6 problems of difficulties (Div. 2 500-1000-1750-2500-2250-2500). We invite all who is interested to our contest. This contest will be held in our group gym. You can find the contest in our codeforces group.

Thanks!

UPD:

Hi all, Weekly Training Farm 21 has ended.

Congradulations to the winner W4yneb0t and the first runners up eddy1021, they are the only two who solved all six problems!!

Thanks to all who participated in the contest. We hope you enjoy the problems.

The editorial will be posted within a couple of days.

We wish to see you in the next week's training farm prepared by zscoder!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked problem F. How to solve this? W4yneb0t eddy1021

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    Calculate DP[a][b][c]: the minimum number of times you deliver baggage with weight W-1, if you deliver or move only the first a items, and move b items of weight 1 and c items of weight 2 (the moved items aren't delivered, imagine you're placing them in some temporary storage).

    For each b and c, look at DP[n][b][c] and place the remaining b+c items optimally: greedy works, place a 2 if it fits and a 1 otherwise. If the result is optimal, the answer is at most b+c.

    O(n^3) time, O(n^2) space if you store the DP 2 levels at a time.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D, E and F ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Just a few insights =) Perhaps not necessarily the best, though
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please share the editorial :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dreamoon_love_AA Weekly Training Farm 22 passed. I forget. Please announce the contest