Help in problem 'Emoticons' from Dhaka 2015 preliminary
Разница между en1 и en2, 270 символ(ов) изменены
Hi everyone,↵

I saw [this question](https://www.quora.com/How-do-I-approach-Problem-E-EMOTICONS-in-this-problem-set-This-problem-set-is-of-ACM-ICPC-Dhaka-Regionals-2015-preliminary) on Quora about Problem E — Emoticons from Dhaka Preliminary Round 2015 ([problemset](https://www.dropbox.com/sh/27ziov8qdk06cmw/AABfHiKjqsIi1Ac9xwnpf5tQa/icpc_dpr_2015_problem_set.pdf?dl=0)). The statement is as follows:↵

Given a string S (|S| <= $10^5$) 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 * $10^6$)↵

~~~~~↵
7↵
_^^_^^_↵
^__^__^↵
______↵
^^__^^↵
^_^^__^↵
^_^_^^↵
^_^_^_^^^^_^_^↵
~~~~~↵

**Sample output**↵

~~~~~↵
1↵
1↵
0↵
2↵
2↵
2↵
4↵
~~~~~↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский mogers 2016-01-15 21:55:40 270
en1 Английский mogers 2016-01-15 21:53:21 1131 Initial revision (published)