CherryTree's blog

Solution to The Black Box problem @ hackerrank w8
By CherryTree, 10 years ago, In English

...Is here. It is always nice to hear other's approaches as well.

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

»
10 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

There is a another solution using Interval Tree.

let's T[v] == 1 if number v is inside the black box, otherwise T[v] == 0

Using array T we can construct interval tree.
Each node will contain basis vectors of existing numbers in it's range.

Initially Array T is filled with 0.
Adding number v, means T[v] = 1
Deleting number v, means T[v] = 0
After each operation we need to update only log(n) nodes.

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

    Can you try to explain a little bit more in detail? I read the article above but I'm having some troubles understanding your solution (and quite honestly the article's) since I'm not familiar with that greedy that solves the static problem. But well, could you provide some more detailed explanation of yours?

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

I've sent stupid solution and got almost all points (131.71)

Idea is: have a set with current basis and set of others.
Light operations:
Add, delete from others

Heavy operation:
delete from basis.(We should check if there are any element in others that we can add to basis — deleted element. It's O(others_size) but to make it a bit random (More random elements go to current basis, so it's harder to remove them and not element from others) I support an iterator to the set of others and check all element of others in order [iter, end), then [begin, iter), not [begin, end) but I am not sure if it helped at all (probably just check from begin to end will work too)

That a thing why I don't really like contests with not full solutions getting points.

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

    I have similar solution (n*30*30) and got AC. Idea is to keep basis with most long-living elements.

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

      Am I right that your solution is basically offline and you precalculated for each element when it'll be deleted?

      PS: I don't see you in top of scoreboard. Did you sent it after the end of contest?

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

        Yes, my solution is offline. Yes, during the contest I had bug =)

        → Reply