Tobby_And_Friends's blog

Data Structure problem (SPOJ PATULJCI — Snow White and the N dwarfs)
By Tobby_And_Friends, history, 8 years ago, In English

Problem link: http://www.spoj.com/problems/PATULJCI/

Solution link: http://ideone.com/NqSI3j

Verdict: TLE

I tried to use Mo's algorithm and segment tree to solve the problem. How do I further optimize my solution? Any help is really appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You need O((n + q) log n) to get AC, or something very close to that.

Try to only use one segment tree, that gives you any "dominant color" in an interval, for which you then check if it appears enough times in the interval. The solution is completely online.

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

    How to use segment tree in this case?

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

      Notice that in a node of the segtree, its dominating color, if there is one, has to be a doninating color of one or both of its children. Then, you can store in each node the dominating color. To merge nodes, you can query the number of each dominating color in both nodes, and see if they can be dominating in the new node. You can do this with order statistic tree or BIT and get O(log^2 n) time per query.

      To get log n time, I think you can have your segtree store the 2 colors with most number of occurrences, and the number of times they occur. Now observe that a dominating color on the new interval has to be among the colors in the top 2 for each node, so you can check all of those colors using segtree values.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Oh, sorry! My bad :)

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

        About the log n approach, I don't think storing the 2 colors that appear the most is enough. For example, every color on a segment may appear only once. But the general idea seems correct, thanks for the anawer.

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

          Yea the number of times each one appears should also be stored

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

An alternate solution is by using persistent segment trees. At a node if we have two subtrees with sum of frequencies as S1 and S2, our answer either exists in the subtree with greater sum or doesn't exist. This gets AC in O((N + Q) * logN).

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

There is a solution with but I describe the one.

Let occ(x, L, R) as a function that returns the number of i's such that L ≤ i < R and ai = x. It's easy to implement, for each color like x, keep a vector of indexes that ai = x then answer is lower_bound(vec[x].begin(), vec[x].end(), R) - lower_bound(vec[x].begin(), vec[x].end(), L).

Now use segment tree. Consider a node for segment [L, R), keep the color that appears in [L, R) strictly more than (R - L) / 2 in that range, if there is no color satisfies the condition, save -1 there.

It's easy to merge two nodes:

node merge(node L, node R){
    node ans;
    ans.l = a.l, ans.r = b.r;
    for(auto candidate : {a.ans, b.ans})
	if(occ(candidate, ans.l, ans.r) > (ans.r - ans.l) / 2)
	    ans.ans = candidate;
    return ans;
}

Here is my code : Link.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This problem can also be solved with a randomised algorithm. You can see my solution here. The details can be found out in the editorial of this problem on codechef which is a harder version of the above problem with point updates as well.

→ Reply