Contest Delta – Editorial (Part 2)

At the Contest Delta, three exercises stood out among the others in difficulty, and I decided to make a separate post to talk about them, because their solutions are more complex. The first part of the editorial can be found here: [link].

The exercises are:
Fibonacci Again! [link];
How Many Substrings? [link];
Entangled Ropes [link];

All of them were written by the same person, Gabriel Dalalio, and a great amount of what I am going to write here it was him who taught me.

Click at the link below to see the editorial.

Fibonacci Again! [link]
With an attractive name, this exercise called many contestants attention, who became frustrated when they realized that the solution was more complex than expected.

A naive approach would be to solve the exercise by the proposed formula: Fib( Fib(N) )%M, resulting in an Overflow thanks to the great value of Fib(N), without speaking of the necessary time to calculate Fib( Fib(N) ).

An observation that can be made regarding the Fibonacci numbers module M, is that they enter in a sort of cycle, known as the Pisano Period [link].

For example, be M = 4, the common Fibonacci sequence, and in module M, are like this:
                   0  1  2  3  4  5  6  7   8   9   10  11  12
Common Fibonacci:  0  1  1  2  3  5  8  13  21  34  55  89  144
Fibonacci Mod 4 :  0  1  1  2  3  1  0  1   1   2   3   1   0
Pisano Period   : [________________][_____________________][…

The cycle length varies according to the value of M. At the example above, the cycle has length 6.

That means that, be C the length of the cycle, we have:
Fib(K)%M = Fib(K%C)%M

To find out the length of the cycle, the iterative solution is enough. Just generate the Fibonacci values until you find a value X > 1, such that Fib(X)%M = Fib(X+1)%M = 1, and then C = X-1.
At the example above, X = 7, and C = 6.

With it, we can change the initial formula to: Fib( Fib(N)%C )%M.

To finalize, calcule the two Fibonacci values. Here the iterative or recursive solution are too slow, we need a faster way. There are two solutions that cost O(lg N) time:
Fast Doubling: [link][link]
Matrix Exponentiation: [link]

How Many Substrings? – [link]
This exercise requires a more sofisticated way to count the number of strings being formed. The total number of substrings inside a string S of size N is equal to N*(N+1)/2, however many of them may appear more than once.

Besides that, the exercise asks the number of different strings to be counted several times, and not just at the end with a fixed string S. We need a data structure that can help us at the process.

There are three candidate data structures:
Suffix Tree; Suffix Vector; and Suffix Automaton.

With some experience at one of them, it is possible to find out the number of different substrings in linear time.

Entangled Ropes[link]
The exercise asks: is the sequence alternating or not?

The problem is that there are sequences that are “disguised alternating”, as the example given by the exercise itself, where “+-++*+”, which is not alternating, has an identical output of the sequence “+*-*”, which is alternating.
To identify such “disguised alternating” sequences, it is necessary some observation and the identification of a few patterns. I am going to quote here 4 patterns that, after applied to the sequence, reveal if the sequence is alternating or not.

I recommend you to get a piece of paper and a pen so you can draw and understand why these patterns work:

1- The subsequence “+-“ doesn’t affect the answer in any way. Notice that the children 1 and 2 change their places twice, and the position of the ropes goes back to the state it was before this subsequence. Notice that the subsequence “-+” is similar.
When these subsequences appear, just remove such movements.
Example: “++-” -> “+”

2- The subsequence “**” doesn’t affect the answer in any way. Notice that the children will rotate twice, and the positions of the ropes don’t change.
When this subsequence appears, just remove such movements.
Example: “+**++” -> “+++”

3- If the first movement of the entire sequence is a “*”, then all the following switch movements will not affect the answer in any way, until another “*” movement appears. Notice that the movement “*” rotate the children in a way that, when they swap, the ropes don’t change.
When the sequence starts with a “*”, just remove all the movements from the first position to the second position of “*”, inclusive.
Example: “*++++–++*++” -> “++”

4- The subsequence “+*+” has an identical outcome than the subsequence “*-*”. This may be the hardest to visualize, and initially it is hard to see the reason of this change, but it’s important so new patterns can be identified after that.
The subsequence “-*-“, in a similar way, has an identical outcome than the subsequence “*+*”.
When the subsequences above appear, just replace it by the alternative subsequence.
Example: “+*+–” -> “*-*–“

-> But, why doing all of these removals and changes?
As I said, applying these patterns reveal some “disguised alternating” sequences. If the sequence wasn’t alternating, the resulting sequence after the changes will be an empty sequence or the sequence “*”. Otherwise, the sequence is alternating.

-> Where did these patterns come from?
They come from a sophisticated theory, studied by years, and you can read more about it here:

I hope I was clear enough.

If you have any doubt, suggestion or critic, leave a comment below.
Thanks go to Gabriel Dalalio, for explaining me pratically everything I wrote here.

See ya 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.