Блог пользователя 000golabi

Автор 000golabi, история, 5 лет назад, По-английски

“N” people are standing in a line, we name them as a0, a1, ... aN.

The age of any subset of people is defined to be the sum of its individuals.

we want to kill the oldest subset of these N people in a way that for each pair of killed people “ai” and “aj”, the distance is between “p” and “q”.

0< p <= abs(I — j) <= q

p and q are positive numbers. N < 20,000

———-

The above is a problem I came to when designing time series in a charting library. I have converted the original problem into a more readable codeforces style. This will be calculated in each WebGL animation frame, It needs to be fast.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Help me solve this real problem from my workplace.

We want to kill the oldest subset of these N people in a way that....

The above is a problem I came to when designing time series in a charting library...

What a rollercoaster ride!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

a0,a1,.....aN means there are N+1 people not N people.

»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
  • Can the "age" of any "people" be negative (or zero)?
  • Are you sure that you want to get the subset of maximum sum instead of maximum count? I just looked up "time series", and think that it makes sense to ask for maximum count, but not sure what maximum sum is for.
  • I suppose approximate solution is allowed? This is a "real-life" problem, after all.
  • Actually, mathematical description is usually preferred. (Given a sequence of numbers,...) Background can be interesting to read sometimes, but it's usually more annoying.
  • There's an obvious O(n^3) dynamic programming solution, and it can be optimized to O(n^2) with some effort. However in case there's some special condition on p or q (such as p<=10 or q<=10 or n/p<=10 or q/p<=10 ...) the algorithm can be more efficient. What's the real use case?
»
5 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Is this money heist?