vlyubin's blog

By vlyubin, history, 19 months ago, In English

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

Read more »

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

By vlyubin, 6 years ago, In English

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.

Read more »

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

By vlyubin, 6 years ago, In English

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!

Read more »

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