USACO 2020 February Bronze Q2. Mad Scientist

Solution:

This algorithm essentially just takes in the two input strings as character arrays and iterates through both of them simultaneously. We keep use a variable (flip) to keep track of the number of substrings in the two arrays that aren’t equal to each other. Additionally, we also use a variable (equal) to keep track of whether or not the current substrings are equivalent to one anther. If the current characters in the same position are not equivalent, we set equal false. If the character directly after it is also not equivalent, equal is still false because they are part of the same substring. We increment flip when equal is set back to true because that only occurs when an “unequal” substring ends and the current characters are equal. If we iterate through the array and equal is still set to false, that means that there is a substring/character at the end of the arrays that aren’t equal and weren’t added to our answer, flip, so we write an additional “if” statement outside of our for loop to account for that.

import java.io.*;
import java.util.*;
public class MadScientist {public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Kattio io = new Kattio("breedflip");

// Take in input
int N = io.nextInt();
char[] a = io.next().toCharArray();
char[] b = io.next().toCharArray();

// 'flip' is the variable that stores our answer
int flip = 0;
// 'equal' keeps track of whether or not the current character/substring of 'b' equals 'a'
boolean equal = true;

// iterate through both arrays simultaneously
for (int i = 0; i < N; i++)
{
// if the current character of a does not equal the current character of 'b', we
// set 'equal' to false
if (a[i] != b[i]) equal = false;

// if the current character of 'a' equals the current character of 'b'
// and 'equal' is false, then we increment 'flip' and reset 'equal' to true
if (a[i] == b[i] && !equal)
{
flip++;
equal = true;
}
}

// if we finish iterating through the array and 'equal' still has the value false,
// then that means that the last substring of 'b' does not equal the corresponding portion of
// 'a' so we do this if statement to account for that edge case since the arrays were traversed
// through before we incremented flip again
if (!equal) flip++;

io.close();
}
static class Kattio extends PrintWriter {
private StringTokenizer st;

// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName + ".out"));
}

// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
return st.nextToken();
} catch (Exception e) { }
return null;
}

public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}

Hope this editorial helped you! If so, it would be greatly appreciated if you pressed the clap button on this article. If any clarification is needed or if you have any suggestions for improvement, feel free to drop a comment below.

More from Annie Zhang

Hi! I'm Annie, a high school sophomore and coding enthusiast.