Блог пользователя Virtual_Contestant

Binary Search way to do this problem
Автор Virtual_Contestant, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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))
→ Ответить