vlyubin's blog

By vlyubin, history, 4 years 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.


UPD: Registration is open

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

Full text and comments »

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

By vlyubin, 8 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.

Full text and comments »

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

By vlyubin, 9 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.


  • 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


Full text and comments »

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