I recently came across a beautiful problem from the Romanian national olympiad from 2005. It has a beautiful intended solution but i will provide another you might have tried if you couldn't find it.
A sequence is called circular if its elements consist of only 'A' and 'B', it has size n (n >= 1) and the element next to the last is considered to be the first. A consequence of such a sequence is that there are precisely n contiguous subsequences (from now on whenever we mention subsequence we mean a contigous one) of any size, for example for "ABBA" the 4 subsequences of size 3 are in order "ABB", "BBA", "BAA", "AAB".
A sequence is called special if it satisfies the property of the circular sequence defined above and furthermore ANY two subsequences of equal size differ in the number of characters 'A' by at most 1. For example "AABB" is not special because there exist "AA" and "BB", "ABABAABAAB" is not special either because of "AABAA" and "BABAB", but "ABA" and "AABABAAB" satisfy the property.
Your task is given a circular sequence to determine whether it satisfies the special property. Consider as examples the 4 sequences given above. A first step towards a solution is to observe that the sequence must consist of concatenations of "nAB" and "n+1AB" where "nAB" means n chars of 'A' and one 'B' (or "nBA" but we will consider just "nAB" from now on). We can consider a second sequence where every occurence of "nAB" in the original seq. is marked with 'A' and "n+1AB" is considered 'B'. For example "AABAAABAABAABAAAB" becomes "ABAAB". The key observation (and likely difficult to spot) is that the initial sequence is special if and only if the second one is special, thus we can simplify the sequence until we reach a trivial case. This approach takes O(n) steps.
But suppose we didn't figure that. Intuitively we notice that the 'B's should be evenly distributed across the subsequence, meaning the spaces between consecutive 'B's must not differ by much. Thus we can actually 'measure' how much the 'B's differ from their supposed positions, let me show you what i mean by taking an example, say ABAAB. By the way, we can simplify the problem by doubling the sequence and thus becomes ABAABABAAB and only take subsequences of size n (here n=6) into consideration. There are 4 'B's and 10 total characters, therefore we should expect a new 'B' every 10/4 = 2.5 indices. There are 'B's on positions 2, 5, 7 and 10, with their respective supposed values being 2.5, 5, 7.5 and 10. We measure the most 'behind' and most 'ahead' 'B' and conclude that 2 and 7 are 0.5 behind while 5 and 10 are 0 ahead. The cool thing is that if the difference between ahead and behind is less that 1 then the sequence is special. here 0.5-0 = 0.5 thus is special. In case you didn't completely understand let me take an example that fails, like BBAABAA. doubling it gets BBAABAABBAABAA with a total of 6 'B's and 14 characters. Again, we're expecting a new 'B' every 14/6 = 2.33 indices. Below are the positions of B and their supposed values.
1 — 2.33 (+1.33)
2 — 4.66 (+2.66)
5 — 7 (+2)
8 — 9.33 (+1.33)
9 — 11.66 (+2.66)
12 — 14 (+2)
The most behind one is +1.33 and ahead is 2.66, and since 2.66-1.33 > 1 we can conclude that the sequence is indeed not special.
This solution might not be obvious either but it does start with a decent intuition, one that 'B's should be evenly spread out, and if they aren't then there must be a counter-example. I must admit i wasn't expecting this to work but receiving 100 points on the judge must mean it's provable. In the title i mentioned it's a hard problem, perhaps it might not seem so to you, i just assumed it is due to the fact that only one person got 100 points onsite from the total of ~125 participants in that year. I really hope you found the problem and solutions as interesting as i did, and perhaps new techniques to keep in mind in the future when solving. Thank you very much for reading if you did and if you want to test your source code here is a judge (unfortunately in romanian but you should be able to manage if you translate the page)
