patternjavaMinor
Finding the largest not-necessarily contiguous alternating binary string after inverting any sub-string from a given string
Viewed 0 times
afterthenecessarilycontiguousanysubgivenlargestinvertingbinary
Problem
I'm having problems solving this problem within the time limit.
Alternative Thinking
http://codeforces.com/contest/603/problem/A
Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.
However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while {1, 0, 0} and {0, 1, 0, 1, 1} are not.
Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.
Input
The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).
The following line contains a binary string of length n representing Kevin's results on the USAICO.
Output
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.
My Code
A little explanation: I try every substring and invert that, then I find the longest alternating substring by taking every first occuring 0 and 1. 'f' is the value 0 or 1 which I'm finding, which alternates. I try f=0 and 1 both for index=0
Alternative Thinking
http://codeforces.com/contest/603/problem/A
Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.
However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while {1, 0, 0} and {0, 1, 0, 1, 1} are not.
Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.
Input
The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).
The following line contains a binary string of length n representing Kevin's results on the USAICO.
Output
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.
My Code
A little explanation: I try every substring and invert that, then I find the longest alternating substring by taking every first occuring 0 and 1. 'f' is the value 0 or 1 which I'm finding, which alternates. I try f=0 and 1 both for index=0
Solution
The score is equal to the number of edges, that is transitions from 0 to 1 and from 1 to 0. After flipping number of edges inside the flipped range remains unchanged. Flipping may add two extra edges on the range boundaries; for that you need to find two occurrences of
For example,
Of course there are some corner cases to be considered.
11 or 00 and make the range to flip just one digit in each.For example,
100101001
^^^^^
101010101Of course there are some corner cases to be considered.
Code Snippets
100101001
^^^^^
101010101Context
StackExchange Code Review Q#112633, answer score: 4
Revisions (0)
No revisions yet.