I am working on the 2nd USACO Bronze Prolem from the Dec 2019 contest. I am unsure of how the setup works. For example, in the sample test case, the sequence is ABCDABC. The solution says that the answer is 4, because ABCD doesn’t repeat. However, if you looked at only the letter “D,” wouldn’t that also uniquely determine the position along the road (making the answer just 1)?
I tried writing my code from an interpretation that Farmer John can only see from the front (left) of the road, but that only fulfilled 4/10 test cases.
I’m not sure if I am interpreting the question correctly. Thank you!
Here’s a step-by-step approach to solving the problem:
Read the value of N, the number of farms, from the input.
Read the string of N characters representing the colors of the mailboxes from the input.
Start with K = 1 and a flag variable called found = False.
Iterate through the string of mailboxes from index 0 to N - K.
For each index i, consider the subsequence of length K starting from index i.
Check if this subsequence appears again in the string starting from index i + 1.
If it appears again, set found = True and break the loop.
If found is True, increment K by 1 and go back to step 4.
If found is False, print the value of K and exit the loop.
The printed value of K will be the smallest value that allows Farmer John to uniquely determine his position along the road based on the colors of the mailboxes.
In the given example, the input is N = 7 and the string is ‘ABCDABC’. Following the steps above, the output will be 4, indicating that the smallest value of K is 4.