NeverSayNever's blog

Approach to solve a problem
By NeverSayNever, 10 years ago, In English

https://www.hackerrank.com/contests/101sep14/challenges/jim-and-the-skyscrapers

Firstly I know the solution that is mentioned in the editorial. I thought whether this problem can be solved without using any such data structure or can i used simple set and finally i clicked to a solution.

Solution is very simple i can sort these element using vector pair and then i can use a set to find out the element which is greater than me using upper_bound and bigger than me but this solution giving this verdict TLE for some files. what is the reason for this. I think my solution's complexity is O(nlog(n)). Can anyone help me in verifying the complexity of my solution. Thanx in advance.

here is my code link here .

Please do have a look.

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

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

I haven't looked at your code, but maybe all solutions are intended to fail. There is cool O(n) solution

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

    no author has O(nlog(n)) solution and most importantly i check that file on which my code is producing TLE that file contain only 50,000 numbers.

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

Try changing line 111 to:

set <int> :: itr it = s.lower_bound(arr[i].sd);

std::set has it's own lower_bound and upper_bound implementations

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

Btw, there is an easy stack-based linear solution.

→ Reply