Hi everyone,
I saw this question on Quora about Problem E — Emoticons from Dhaka Preliminary Round 2015 (problemset). The statement is as follows:
Given a string S (|S| <= 105) of characters '^' or '_', find the number of disjoint '^_^' subsequences. Disjoint means that we can't use the same character in 2 subsequences. For example, if S is ^^__^^ then the answer is 2. However, for S equal to _^^ the answer is 0.
My approach was to process the string left to right and keep count of the number of sequences "^" and "^_" seen so far. When we see a "^", then we can form "^_^" if there is any "^_" subsequence before or keep it as an unmatched "^" to form a "^_" subsequence later.
I think the intended solution is a greedy algorithm, but I couldn't find a greedy approach that works in all cases. Any thoughts?
Sample input (number of tests <= 5000 but number of characters in a input file <= 2.1 * 106)
7
_^^_^^_
^__^__^
______
^^__^^
^_^^__^
^_^_^^
^_^_^_^^^^_^_^
Sample output
1
1
0
2
2
2
4
Auto comment: topic has been updated by mogers (previous revision, new revision, compare).
Someone already asked about a similar problem, here: link.
You're right, a greedy algorithm is enough. Reading your approach I think you just need to consider, when reading an '^', the matcheds "^_^" that can have the second '^' replaced by it and have the second '^' matched with a previously not used '_'.
I think this code explains it better: UVA 13029
Ah.. I was missing the "notUsed" part. Thanks a lot!
Hello mogers, long ago at Quora, you said it wasn't possible to solve this problem using binary search. This problem can indeed be solved using Binary search. But yeah, obviously a greedy O(n) solution is far better than my O(nlogn) approach. However I am going to explain the idea.
We'll binary search on the answer. Say, now x = (lo+hi+1)/2. We will at first check if there are enough "^_" pairs in the string. Whatever be the answer, we will need x pairs of "^_". So we will greedily take the first x "^_" pairs from the string and mark them as taken. Then we will try to take x "^" which are not still taken and try to match them with the "^_" pairs. If we can do that, we will say it is possible to make at least x "^_^" and change the value of lo or hi accordingly. You can check my code here.
I thought this kind of approach would not work. Thanks for pointing it out!