3
\$\begingroup\$

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 for the string for which we are calculating the score. e.g. the score for 10011101001100001 will be calculated by 10011101001100001, i.e. 9.

import java.util.Scanner;

public class Problem_A {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        sc.nextLine();
        final String str = sc.nextLine();
        sc.close();
        int maxScore = score(str);
        for (int i = 0; i < n-1; i++) {
            for (int j = i + 1; j < n; j++) {
                String str2 = invert(str, i, j);
                int score = score(str2);
                if (score > maxScore) {
                    maxScore = score;
                }
            }
        }
        System.out.println(maxScore);
    }

    private static int score(String str) {
        char[] chArr = str.toCharArray();
        int finalScore = 0;
        for (int f = 0; f < 2; f++) {
            int fval = f;
            int score = 0;
            for (int i = 0; i < chArr.length; i++) {
                if (chArr[i] - '0' == f) {
                    score++;
                    f = 1 - f;
                }
            }
            if (score > finalScore) {
                finalScore = score;
            }
            f = fval;
        }
        return finalScore;
    }

    private static String invert(String str, int i, int j) {
        char[] chArr = str.toCharArray();
        for (int k = i; k <= j; k++) {
            chArr[k] = (char) (1 - chArr[k] + 2 * '0');
        }
        return new String(chArr);
    }
}
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

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 11 or 00 and make the range to flip just one digit in each.

For example,

    100101001
      ^^^^^
    101010101

Of course there are some corner cases to be considered.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.