cjtoribio's blog

By cjtoribio, history, 6 months ago, In English,

Motivation & Problem

Recently saw this problem. For some this problem might seem like a segment tree problem and it is indeed one. However this problem and others where segment tree does not apply can be solved using another approach. I will rephrase the problem in a simpler way. We want a data structure capable of doing three main update-operations and some sort of query. The three modify operations are:

add: Add an element to the set.

remove: Remove an element from the set.

updateAll: This one normally changes in this case subtract X from ALL the elements. For this technique it is completely required that the update is done to ALL the values in the set equally.

And also for this problem in particular we may need one query:

getMin: Give me the smallest number in the set.

Observing this operations we want to handle, SegmentTree seems legit except for the remove, but we can wave it around by assigning INF to the position we want to remove. However if we don't have the updateAll then we can just use a MULTISET. And in fact if the remove is only to the minimum element then we can use a HEAP. However the four operations without any "workaround" can only be managed by a DynamicSegmentTree which in fact exists but is like using a bazooka to kill a simple mosquito.

Interface of the Data Structure

struct VeniceSet {
	void add(int);
	void remove(int);
	void updateAll(int); 
	int getMin(); // custom for this problem
	int size();
};

Usage of this methods

So imaging we have this four operations, how can we tackle this problem with it. Well i will illustrate it with a simple code in C++ which i hope is self explanatory.

VeniceSet mySet;
for (int i = 0; i < N; ++i) {
	mySet.add(V[i]);
	mySet.updateAll(T[i]); // decrease all by T[i]
	int total = T[i] * mySet.size(); // we subtracted T[i] from all elements
	
	// in fact some elements were already less than T[i]. So we probbaly are counting 
	// more than what we really subtracted. So we look for all those elements
	while (mySet.getMin() < 0) {
		// get the negative number which we really did not subtracted T[i]
		int toLow = mySet.getMin(); 
		
		// remove from total the amount we over counted
		total -= abs(toLow);
		
		// remove it from the set since I will never be able to substract from it again
		mySet.remove(toLow);
	}
	cout << total << endl;
}
cout << endl;

Implementation of the Technique

As the title says I don't call it a data structure itself but this is a technique almost always backed up by a data structure. And now I am going to explain why I call it Venice technique. Imagine you have an empty land and the government can make queries of the following type: * Make a building with A floors. * Remove a building with B floors. * Remove C floors from all the buildings. (A lot of buildings can be vanished) * Which is the smallest standing building. (Obviously buildings which are already banished don't count)

The operations 1,2 and 4 seems very easy with a set, but the 3 is very cost effective probably O(N) so you might need a lot of workers. But what if instead of removing C floors we just fill the streets with enough water (as in venice) to cover up the first C floors of all the buildings :O. Well that seems like cheating but at least those floor are now vanished :). So in order to do that we apart from the SET we can maintain a global variable which is the water level. so in fact if we have an element and want to know the number of floors it has we can just do height - water_level and in fact after water level is for example 80. If we want to make a building of 3 floors we must make it of 83 floors so that it can tough the land. So the implementation of this technique might look like this.

struct VeniceSet {
	multiset<int> S;
	int water_level = 0;
	void add(int v) {
		S.insert(v + water_level);
	}
	void remove(int v) {
		S.erase(S.find(v + water_level));
	}
	void updateAll(int v) {
		water_level += v;
	}
	int getMin() {
		return *S.begin() - water_level;
	}
	int size() {
		return S.size();
	}
};

Variations

Trick With Trie

Probably you have seen a problem of having a set of numbers and handle queries such as what is the greatest XOR than can be achieved by using one number of the set and the given number. This can be handled with a BinaryTrie. However if we add the operation XOR all the numbers in the set this would be very heavy. But if we maintain a global water_level that would XOR any number in and any number out, then it would virtually be XORING all the numbers in the set. Don't have an example problem yet, but I know I have used it, so any is welcome.

So as my experience is, this technique is a lightweight modification that can be applied to all DataStructures that support (add, remove and query) and only need the operation (updateAll).

Other Approaches For This Problem

Binary Search: This is very fast and simple, however is an offline solution. (Not apply for other operations such as sort)

Event Processing: Easy to code and fast but still offline and does not apply for other operations such as XOR.

Dynamic Segment Tree: A little slow in practice, same complexity in theory, and requires heavy code. This is online but requires heavy code. (Dynamic means can insert and delete nodes from the segment tree). Does not apply to other variations of the problem such as XOR.

Implicit Segment Tree: Relativly easy to code, but theoretical complexity of Nlog(MAXVAL) and still requires this technique to work. (Does not apply to other variations such as XOR)

Example Problems

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

»
6 months ago, # |
  Vote: I like it +73 Vote: I do not like it

Great article, but I usually use Pasha Technique.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Mmmh really good to know, could you describe it a little bit or point at some code using it? Is just to know all other approaches and point it out in the article. Thanks.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    What's Pasha Technique?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Wish I could upvote twice

»
6 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

Great article! Surely helps gray coders like me become better at problem solving. :p

EDIT: I was being purely honest with the comment. No need to downvote.

»
6 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Shouldn't the correct code be like this?

void remove(int v) { S.erase(S.find(v + waterlevel)); }
int getMin() { return *S.begin() - waterlevel; }

Otherwise you sometimes need to handle the water_level manually (min, remove), and sometimes not (add), which would be really strange.

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

Auto comment: topic has been updated by cjtoribio (previous revision, new revision, compare).

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

Nice analogy. It would be useful some links to problems using this technique or data structures using it too ... anybody ???

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You may try the following: BDOI16E

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

      Hmm the problem seems interesting. I'm still trying to find a solution applying the technique. Can you give some hint ?? Thanks for the link!!!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Hint
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's what i was using to solve it, and not sure if i over-killed too. I was thinking in a simpler solution (like using the technique discussed here only or something). Thanks !!!

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

Cool. Trick

»
6 months ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

Coulda simply used bitset LOL xD lulz

UPD: Sorry, at first I thought this was a troll post. I didn't intend to offend anybody.

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

I also did a similar thing during the contest.
I used a dynamic segment tree but instead of performing lazy propagation for update all I used similar technique of maintaining a level.
Link to my submission : http://codeforces.com/contest/948/submission/36168355
In the code anss contains the current level.

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

But you can't remove buildings in civ, not even when playing Venice.

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

In the trie variation, what is the benefit of keeping the XOR of all numbers in the set???

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

    You dont have a XOR of all the numbers in the set you just have a lazy XOR that you want to apply to all the elements in the set. Instead of applying to the numbers you apply to each query you are asked, as we does with the ADD.

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

Nice tutorial! GOOD JOB!!!

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I've used this before but never knew it had a name.

http://codeforces.com/problemset/problem/893/D

Venice technique + prefix sums

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

    I made the name up. Definitely a lot of tricks have no name and that is why it is hard to find articles about it :(. That is why I wanted to come with one in case people want to adopt that name or at least put another one.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +69 Vote: I do not like it

      What if some simple tricks, like "let's store one variable with global shift", don't need any names and articles, because it's very intuitive for specific task, and one sentence can fully describe this trick?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        It adds an element of humor. E.g. the Trump technique would be related to tweeting

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

D. Vitya and Strange Lesson

An example problem for Trie variation.

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

What is Event Processing? When I google it, I can't find any information related to competitive programming.

»
6 months ago, # |
  Vote: I like it -13 Vote: I do not like it

গুদ জব।

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

Can you please share your codes for the example problems using this technique.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    This is my code for the problem suggested by mahmud2690 BDOI16E. It combines two techniques as discussed above.

    code
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    This is my code for the other problem suggested by Omar_Elawady. Although the hardest part is getting the mex.

    Solution