Tanmoy1228's blog

Spoj Problem: Election Posters(Segment Tree Or BIT type)
By Tanmoy1228, history, 10 years ago, In English

can anyone give me any idea for this problem.

Problem: Election Posters

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

Comments Comments (19)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You should use a segment tree with lazy propagation. After all updates are done, query every point to see which poster is there.

It's only necessary to check points that are either endpoints or posters or at distance 1 from some endpoint, so you can safely compress the coordinates first and then use a segment tree of size 217.

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

    Hi, could you explain how to implement that segment tree? What does it store? How to make the updates? I'm a newbie in lazy propagation

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

      It stores the index of the last poster painted on that range. It propagates downwards, just copying its last update value to the children.

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

    What do you mean by compressing the coordinates ?

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

      Consider an array. Compressing it means assigning each element a number starting from 1 based on how many elements are smaller. For example, the array [12, 57, 4, 25] would become [2, 4, 1, 3] after compression and [7, 5, 1, 16, 5] would become [3, 2, 1, 4, 2].

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

        well yes i'm familiar with the concept what i did not get here was how compression works when we have the beginning and end of every range ?

        If you would kindly explain how to apply compression here that would be really appreciated

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

          It's the same, just consider all points that are either endpoints or posters or at distance 1 from some endpoint, and apply the compression as I explained above. Then you just replace original values with compressed ones.

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

Hi, I used a sweep line aproach. For each poster consider its begin and end in a vector, then sort by coordinate (if two are equal first the begin). Now store the current posters in a set by index (order in the input), when you find a begin in the vector add the index, otherwise delete it from de set (O(logN). In each step you could ask wich is the greater index in the set ( if the current coordinate is different from the previous one ) using iterators (for C++, I dont know other languages) and add it to other set. The answer will be the final size of this new set.

I hope you understand my explanation, send me a MP if you continue having problems to send you me AC code

PD: Sorry for my english

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


1. Compress input numbers. Let's say M is the greatest number now.
2. Keep a set which contains free positions. Initially it contains all numbers from 1 to M.
3. Process the posters in reverse order. If there is a number between ai and bi in the set (you can check this with set.lower_bound() function), then this poster is not entirely covered by the posters after it. In this case, remove all numbers that are between ai and bi from the set.

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

    That's a really nice solution.

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

    We wish to process each position between 1 and M in constant time, so you solution works because we either do nothing to a postion or delete it only once. But how do I peform this deletion operation? If I were to use set.erase in the interval from ai to bi it would run in linear time which is not good enough.

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

this problem can be solved without segment tree or bit, create your own Doubly linked list and process posters in reverse order , more hint : each node of your Doubly linked list should hold two value (l,r) , left and right ;-)

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

    To use doubly linked list, you should calculate the node to start painting / the node to end painting in less then O(n). How is it possible?

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

There are numerous solution known for this problem, but I personally think this is the best solution. It is an improvement to sparik's solution.

First, compress the coordinate / reverse the query.

Now consider this recursive function :

void paint(int s, int e, int x){
if(s == e) return;
if(!painted[s]) painted[s] = x;
paint(s+1, e, x);

This function is obvious but slow.

Now it can be optimized using simillar mechanism to disjoint sets. First, initialize nxt[i] = i;

int paint(int s, int e, int x){
if(s >= e) return s;
if(!painted[s]) painted[s] = x;
return nxt[s] = paint(nxt[s]+1, e, x);

This program runs in O(nlgn), but in practice it is roughly linear. http://codeforces.net/blog/entry/21476#comments

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

    For each query we will be visiting the unmarked indices , plus some others to update its nxt value. How do we actually come up with O(logn) for it ?

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

I have solved it using sets
Do like this
1.Compress the coordinates
For example : Map (12,3,13,14) to (2,1,3,4) , (13,6,23,25,11) to (3,1,4,5,2)
2. Initialize a set inserted with all elements from min value(1) to max_value of coordinate obtained input (After compressing).
3.Now start from the last coordinates suppose (x,y):
a.find lower_bound of first coordinate of x(it)
b.find upper_bound of last coordinate of y(jt)
if(it != jt)
count += 1
4.print count
(count is number the posters visible on the wall)
Here is link to solution : http://ideone.com/AibFQ7

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

    Your solution gives 4 as the output for this case but it should be 5(Actually you haven't properly compressed the co-ordinates). 1 6 1 3 4 6 6 7 8 10 1 2 3 4

    → Reply