A.K.Goharshady's blog

By A.K.Goharshady, 6 years ago, In English,
This post is written to help my friend , Iman , complete this one.
Problem A: Triangle (code)
For each of the possible combinations of three sticks , we can make a triangle if sum of the lengths of the smaller two is greater than the length of the third and we can make a segment in case of equality.

Problem B: President's office (code)
For each cell of president's desk , we check all its neighbors and add their colors to a set. easy as pie!

Problem C: Alice,Bob and chocolate (code)
This one can be solved easily by simulation. see the code.

Problem E: Exposition
I solved this one in O(nlgn) time using a segment-tree and keeping track of minimum and maximum element in each segment. Adding a number is O(lgn) because we need to update minimum and maximum for the log2n  segments containing that number. For each start point we query the tree to find the maximal endpoint. This is again O(lgn) and is done O(n) times so we have a total complexity of O(nlgn) fitting perfectly in the time limit. 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

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

The solution to Problem E should have a complexity of O(n*lgn*lgn), since an query (O(lgn) time) is made for each loop within the binary search (O(lgn) time).

  • »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It can be solve in O(NlogN) if you use two pointers and query in the segment tree each step, The two pointers is O(N) and in each operation we query on the segment tree giving an O(NlogN) solution better than the O(N(logN)^2) of the binary search. However both solutions work good and one more thing the solution with binary search can be done in O(NlogN) if you do the search with the query and no the query for every step of the search. Think about that last solution.

    UPDATE: I get an O(n) solution no segment tree

8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Problem C can be solved by simply taking the prefix and suffix sums and then comparing them.