I am stuck in this problem for a particular steps. Let me describe what my approach to solve this problem.
I take two list for both ^ and _ characters position. So both list are sorted. For each value from _ list i did binary search to find out the nearest position value from ^ character list. For example if list for ^ is : 1 3 4 5. and list for _ is : 2 5 6 Output For 2 value from the _ list is: 1 and 3[using binary search] from ^ list. So for next _ characters position 1 and 3 cant be used again and i need to mark them.Here is my problem if i mark them and erase them from the ^ list i am getting TLE. Is there any efficient way to mark them and doing binary search again?
Thanks in advance.
Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4917
I think that set from STL does what you want. You can use lower_bound and upper_bound to search and erase to remove the used elements. Each of those operations are executed in O(logN) I guess, please someone correct me if I'm wrong.
Set Reference
But your approach will lead to WA, try the following testcases:
2
^_^_^^^_^
^_^_____^^^^^^^
Output
Case 1: 2
Case 2: 1
Jury's answer:
Case 1: 3
Case 2: 2
I think this problem is meant to be solved in O(N), you can find the solution passing by each element of the string once.
If you want to see, this is the code I used: Don't click me