mouse_wireless's blog

Efficient solution for query problem?
By mouse_wireless, history, 6 years ago, In English

During one of my problem solving sessions, I thought about this problem somewhat related to what I was solving:

Say you have a set of numbers a_1, a_2, ..., a_n and some values x_1, x_2, ..., x_n.

On this set, you can make the following operation:

a_1, a_2, ..., a_n ------> a_1 + x_1, a_2 + x_2, ..., a_n + x_n

(in other words, you add to each number its corresponding x value).

You have to repeat this operation many times and after each time answer what is the minimum element in the set. By many I mean (for example) that the number of elements and the number of queries have the same order.

If all x values are equal, it's easy to solve with something like segment tree. However, the way the problem is, I have tried different approaches (including some algebraic ones) but I can't seem to come up with a solution that is better than quadratic. It seems like it should be a simple problem, is there a simple solution I am not seeing?

UPDATE: reading random (completely unrelated) posts on codeforces, I have by chance found something called "Convex hull trick" which can be used to determine the minimum element from a set of linear functions evaluated at a certain point. It seems like it could be applied in this situation, since the value of a_i after k steps can be expressed a linear function in k: f_i(k) = a_i + k * x_i. This method would provide a linearithmic solution. I will check it out tomorrow.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I probably didn't get this right... if all the x values are equal, won't it just be enough to find the initial minimum in set a, and add to it the required amount of x?

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

    Yeah, that is correct.

    The point I was trying to illustrate is that you can use segment trees for range updates as long as the update value is constant and I was pondering the existence of a maybe somewhat similar data structure that allows range updates for different values.

    But you are right, segment trees would not even be needed in this case.

    Anyway, the main problem mentions nothing about equal x values, that was just a parenthesis :)

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

It can be solved easily using Convex Hull Trick.

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

    Thanks

    I've only just found out about it by randomly reading the blog of adamant. Seems like you were 1 minute faster with the response though :D

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

    Can you please elaborate, how it can be done?

    → Reply