USACO Guide: Secret Cow Code

The Problem

The problem text is shown below (USACO Page):

Problem Text (


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.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());

        // 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));


    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);
            return charAt((index - 1) % (totalLength / 2), totalLength / 2);


This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below:

Successful test cases