USACO Guide: Secret Cow Code
The Problem
The problem text is shown below (USACO Page):
Explanation
I implemented a recursive algorithm for my solution: in order to find what character lies in index N after M duplications, my code looks back to the index in duplication M-1 that, after a right-shifted duplication, would end up in index N. The process repeats, stepping backwards until the original message is reached, and the character within the message that, after M duplications, would end up in index N is returned. The comments within my code explain more of the specifics.
My Solution
import java.io.*;
import java.util.*;
public class SecretCowCode {
private static String fileNamePrefix = "cowcode";
private static String message;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(fileNamePrefix + ".in"));
StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
// Read in data
message = stringTokenizer.nextToken();
long desiredIndex = Long.parseLong(stringTokenizer.nextToken());
reader.close();
// Find the total length of the message after the right number of duplications for the desiredIndex to exist
// This length is the length of the message times the smallest power of 2 required to be >= desiredIndex
long lengthOfTotalMessage = message.length();
while (lengthOfTotalMessage < desiredIndex)
lengthOfTotalMessage *= 2;
// The problem counts characters starting from 1, but strings are 0-indexed
desiredIndex -= 1;
PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileNamePrefix + ".out")));
// Begin recursion with the desired index and the length of the message
writer.println(charAt(desiredIndex, lengthOfTotalMessage));
writer.close();
}
private static char charAt(long index, long totalLength) {
// Base case: the original string has been reached (no more duplications to step back through)
if (index < message.length())
return message.charAt((int) index); // Can be casted to int because if this is true index is less than 30
// The totalLength is halved either way (the length of the string doubles with each duplication)
// The new index to check, however, may have to be recalculated, accounting for wrapping
if (index < totalLength / 2)
return charAt(index, totalLength / 2);
else
return charAt((index - 1) % (totalLength / 2), totalLength / 2);
}
}
Results
This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below: