Virtual_Contestant's blog

Binary Search way to do this problem
By Virtual_Contestant, history, 4 years ago, In English

I have solved this problem but I wonder how to do this using binary search i do have one idea but i am a bit lazy to implement that because i also think that might TLE. Can you guys please help me in this. https://codeforces.com/contest/1203/problem/D2

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Well, I think you can BinarySearch on the length of the subsequence that you want to remove. Then it's easy to check whether it's possible or not (it can be done in O(length(s))), you can do it like this:


int cur = 0;
int lst = -1;
bool hap = false;
for (int i = 0; i < s.size(); i++) {
 if (s[i] == t[cur] && (lst == -1 || i — lst > BinarySearch-Value) && !hap) {
  cur++;
  lst = i;
  hap = true;
 }
}
if (cur == t.size() — 1) // It is possible
else // It is not possible

It won't get TLE because its time complexity is O(len(s) log len(s))
→ Reply