My C solution passes all the first 60 tests, after the 61st I get the following message:
*** Error in `/home/codewarrior/solution': free(): invalid next size (fast): 0x00000000023bc960 ***

Is your helper function recursive? Please include your solution so I can see what is happening.

I think this is quite hard for 4 kyu, but it was fun.

The other kata asks for simple recursion (top down) which calculates the same value several times, this one asks for botom-up recursion which can calculate the fibonacci element for a higher n. I think it is trying to teach something very different.

In C, the casting the long long ** act into a (long long (*)[2] ) is changing the values and I have no idea why.

It is not that it can not be solved, I wrote a working solution it is that it would make sense that if the key is in lowercase, then the encoded message would be in lowercase as well.

I agree, the way this requires the programmer to check the input is very complicated.

The tests require the encoding function to return an all uppercase encoded string. However, the decoding function according to the tests must accept a lowercase encoded string and a lowercase key. This is strange.