USACO Bronze 2019 December - Where Am I?

Authors: Ananth Kashyap, Brad Ma, David Guo

Appears In

Bronze - (Optional) Introduction to Sets & Maps

Explanation

We go through all possible substring lengths $k$ starting from $1$ . For each length, we use a map to track how many times each substring of length $k$ appears.

If all substrings of that length appear only once, we know we've found our answer and print $k$ . This works because once we find a length where all substrings are unique, we don't need to check for longer lengths.

Implementation

Time Complexity: $\mathcal{O}(N^3)$

C++

#include <bits/stdc++.h>
using namespace std;

void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);

Java

import java.io.*;
import java.util.*;

public class WhereAmI {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("whereami");
		int n = io.nextInt();
		String s = io.next();

		// try each length starting from the smallest one

Python

file_in = open("whereami.in")
data = file_in.read().strip().split("\n")
n = int(data[0])
mailboxes = data[1]

# Set the answer initially to n, as we know n is always a possible answer
ans = n

# We can iterate through lengths of sequences to find the smallest length
for l in range(1, n + 1):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!