mogers's blog

Help in problem 'Emoticons' from Dhaka 2015 preliminary
By mogers, history, 9 years ago, In English

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
  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Auto comment: topic has been updated by mogers (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ah.. I was missing the "notUsed" part. Thanks a lot!

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I thought this kind of approach would not work. Thanks for pointing it out!

    → Reply