Hi folks,

The problem set from 2019 Fall Waterloo Local Contest that was held this Sunday will be available in the gym today in roughly 8 hours (timedate link).

This is an individual contest that contains 5 problems with 3 hours to solve them. It's good for both div 2 and div 1 participants — at least 3 problems should be accessible for div 2.

Div 1 participants are especially invited to solve problem E — so far only three people solved E.

GL&HF

UPD: Registration is open

UPD: Solution sketches are available at https://www.dropbox.com/s/hs9oy0y9ep0nmmq/Solution%20Sketches.pdf?dl=0

Have anyone thought of making Div 2 contests rated for violet users (or perhaps a fraction of yellow users as well)? Basically, they will get a chance to compete in both D2 and D1 contests (though in D2 they will be separated from everyone else)? Looking at a couple of the most recent D2 contests, it appears that most of violet users actually solve 3 problems or less (in a 5 problem contest), which means it will still be a good competition for them. The only problem I can see with this is that you can become yellow without participating in a single D1 contest, but this doesn't seem to be so horrible if more people can write more contests as official participants.

Can someone help me with solving a problem of online knapsack with small constraints. Formally: you have a knapsack that can fit items of weight at most W. You are given N queries, where each query is one of:

• Add a new item of weight w and cost s to a set of possible objects.

• Remove the oldest item from the set of possible objects (the one which was added to the set before others)

• Solve knapsack — print the largest cost you can achieve by choosing some objects from your current set so that their combined weight is at most W.

Constraints:

• W <= 2000 (fixed and is given to you)

• N <= 10000

• Cost <= 1000000

• There can be at most L = 2000 items in your set of objects at any time.

• TL: 5 seconds

Example (W = 100):

• Add (w=20,c=30)

• Add (w=20,c=35)

• Query: C=65

• Remove

• Query: C=35

There are a LOT of articles about online knapsack problem out there, but most of them try to approximate the result. In this case, we have a pretty small constraint on W, but I cannot take advantage of this. The naive approach (do a DP each time a knapsack query comes along) gets a TL.

Source: https://www.hackerrank.com/contests/cs-quora/challenges/quora-feed-optimizer

Thanks!