Tobby_And_Friends's blog

By Tobby_And_Friends, history, 7 years ago, In English

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.

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

Good day to you,

well try to develop the attribute-by-attribute thinking.

One attribute
Two attributes
Three attributes
Four attributes

Good Luck & Have Nice Day!

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

    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.

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

      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