Problem link: http://www.spoj.com/problems/ADACABAA/
If there were only only 2 attributes of the vegetables I would have been able to solve the problem. I would have simply sorted in descending order the vegetables according to it's first attribute. And as for the second attribute I could have easily found the answer using a BIT/Fenwick tree. But I am not able to figure how to solve this problem with 4 attributes of the vegetables. Any help is really appreciated.
Good day to you,
well try to develop the attribute-by-attribute thinking.
Then it is simply only the biggest one
Sort them by first attribute (lets say bigger first). Then as you can see (and as you said) — if you process them one by one and simply keep maximum. If the current element is lesser than maximum, then you know it has both attributes worst than "something" and you can erase this element.
The first step is very similar to first step — sort them. Now you always know that actual element is worst in first elements in first attribute. Now additianally to previous hint, we have to build a data structure — maximum-fenwick is enought for this — which can say "maximum on range". Here for each element you update this data structure on index "attribute2" by value "attribute3". As you can see, now if you find element in range (atribute2+1,INFINITY) which is greater than attribute3, you can also erase this element.
As in thinking, the step from three to four is not that hard (even I admit that is might not be that naicu on implementation site). Simply "find" some data structure (which I let you for homework, not to spoil the whole problem), which could do the job as previous data structure BUT in 2D (so you could index by attribute2 and attribute3 and the value might be attribute4).
Good Luck & Have Nice Day!
Hello Morass.I have been trying this question for a while and have put in efforts in thinking as well as searching for a suitable data structure which could solve the problem in 2D.A 2D BIT/segment tree could have been used but the constraints won't allow that.Are you sure that this problem is to be solved with a some what less popular data structure or do we have to use a variation of a well known technique like SQRT decomp?Would appreciate your help as i have been stuck with many problems on SPOJ which reduce to similar tasks of searching in a 2D NXN space with N being 10^5.
Good day to you,
I'm pretty sure it could work for this problem (but not sure for the others? since it might have big overhead). 2D Fenwick works in logarithmic time but the problem is it requires N2 space. Anyway as you can see it requires only O(log(N)2) space per query so if you will "somehow" store only those elements it access, it will be O(Q * log(N)2) space, and the time will be multiplied by the "time" of your structure... so just make it sparse by "sufficient" data structure ;-) I guess properly used hashing could work.
Wish you a good Luck