Submit | All submissions | Best solutions | Back to list |
STC02 - Antisymmetry |
Byteasar studies certain strings of zeroes and ones. Let S be such a string. By Sr we will denote the reversed (i.e., "read backwards") string S, and by SI we will denote the string obtained from S by changing all the zeroes to ones and ones to zeroes.
Byteasar is interested in antisymmetry, while all things symmetric bore him. Antisymmetry however is not a mere lack of symmetry. We will say that a (nonempty) string S is antisymmetric if, for every position i in S, the i-th last character is different than the i-th (first) character. In particular, a string S consisting of zeroes and ones is antisymmetric if and only if S=SIr. For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not.
In a given string consisting of zeroes and ones we would like to determine the number of contiguous nonempty antisymmetric fragments. Different fragments corresponding to the same substrings should be counted multiple times.
Input
The first line of the standard input contains an integer N (1 <= N <= 500000) that denotes the length of the string. The second line gives a string of 0 and/or 1 of length N. There are no spaces in the string.
Output
The first and only line of the standard output should contain a single integer, namely the number of contiguous (non empty) fragments of the given string that are antisymmetric.
Example
For the input data:
8 11001011
the correct result is:
7
Antisymmetric fragments are: 01 (occurs twice), 10 (also twice), 0101, 1100, and 001011.
Added by: | Sergey Kulik |
Date: | 2013-08-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | POI XVII |
hide comments
2021-10-15 15:58:14
Yeaah this can be solved with Manacher algo.Just change a bit. And if you get WA on test 61, you may wrong in each possible case, so check your code carefully. |
|
2017-08-29 16:41:15
Looks similar to palindromes and Manacher algorithm So I am trying to adapt Manacher algorithm for this task |
|
2017-01-08 17:18:13
WA on test 61!!!!!!! T_T |
|
2014-07-24 19:23:47 savvi
60 testcases!! |
|
2013-08-19 20:07:56 :D
Hint (feel free to delete if you think it's a spoiler): This can be solved in O(N). |
|
2013-08-16 07:32:45 Amit Jain
very optimized dp fails as well,gives tle.. no clue,what to do Last edit: 2013-08-16 07:33:07 |
|
2013-08-15 21:35:52 (Tjandra Satria Gunawan)(曾毅昆)
Very nice problem (test case is strong) :-) Would be better if the cluster is set to pyramid. |