000golabi's blog

Help me solve this real problem from my workplace.
By 000golabi, history, 5 years ago, In English

“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.

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

»
5 years ago, # |
  Vote: I like it +57 Vote: I do not like it

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!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Guys, don't help this serial killer

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know alot of countries' populations are getting older but this is just excessive.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it
  • 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?
→ Reply
»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Is this money heist?

→ Reply