0
$\begingroup$

There are given $n$ balls. Their indexes: $\{1,...,n\}$.
Initially all of them are painted in $green$. (other possible color in my problem is $red$).
It is possible to paint interval of balls in color $red$ or $green$, for example $paint([a,b], green)$ - ball in given interval will be paint in green.

What's more, there are given $m\ge n$ operations of painting. After executing all $m$ painting our task is answer to question: What is color of ball $i$, where $i\in \{1,...,n\}$.

I can solve it by simple simulation coloring - I use BST interval tree. Hence, I get $O(m\lg n)$.

I am think about faster solution. It is my problem, indeed. It is easy to see that good idea is process operations in reverse order (from $m$ to $1$). Have you any idea ?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Related question. $\endgroup$ – Raphael♦ Sep 18 '15 at 21:11
  • $\begingroup$ When I use your link I get $O(m \sqrt{n} \log(n))$. It is worse than $O(m\lg n)$ $\endgroup$ – M.Swe Sep 19 '15 at 10:53
  • 2
    $\begingroup$ $\mathcal{O}(m \log n)$ seems pretty good already, I assume you could prove this as a lower bound in a comparison model. I guess if you're after practical performance, you should consider the option of using a static tree (sometimes called segment tree) instead of a BST. Theoretically, it might be possible to achieve something like $\mathcal{O}(m \log \log n)$ using y-fast tries or vEB trees, but I can't imagine these being useful in practice $\endgroup$ – Niklas B. Sep 19 '15 at 12:01
  • $\begingroup$ I'm confused. What is the input? Are the inputs $n,m,i$? So you only need to answer the question for a single $i$? If so, it seems that this problem can be solved in $O(m)$ time: each time you receive an operation, you simply check whether $i$ is in the interval or not and update its color as needed. If that's not what you intended, please update the question to clarify. $\endgroup$ – D.W.♦ Sep 20 '15 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.