Unable to understand solution for ques: CHN08

general
1

My code gives the correct result but shows a “TLE” on submission in Codechef. So, I tried seeing the successful solutions in Java. However, I am unable to understand the logic here. (How it provides correct answer for n>3, just the switch case bit.)
I post the successful solution here. Please help me with it. As most successful solutions have this logic I am not posting the contributor’s name:

import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int t,i,n,a,b,res;
		InputStreamReader in = new InputStreamReader(System.in);
		BufferedReader buffer = new BufferedReader(in);
		t = Integer.parseInt(buffer.readLine().trim());
		int MOD = 1000000000 + 7;
		String line;
		while(t-->0)
		{
		    res = 0;
		    line = buffer.readLine();
		    String myStr[] = line.trim().split("\\s+");
		    a = Integer.parseInt(myStr[0]);
		    b = Integer.parseInt(myStr[1]);
		    n = Integer.parseInt(myStr[2]);
		    n = n-1;
            n %= 6;
            //System.out.println("n%6: "+n);
		    switch(n)
		    {
		        case 0:
		            res = a;
		            break;
		        case 1:
		            res = b;
		            break;
		        case 2:
		            res = b-a;
		            break;
		        case 3:
		            res = -a;
		            break;
		        case 4:
		            res = -b;
		            break;
		        case 5:
		            res = a-b;
		            break;
		        default:
		            break;
		    }
		    res = res%MOD;
		    if(res>=0)
		        System.out.println(res);
		    else
		        System.out.println(MOD+res);
		 }
	}
}
2

Give some more thought to the question. Try to use pen-paper and manually find values of f(1) to f(13). You will see a nice pattern.

Just change the equation from f(x) = f(x-1) + f(x+1). to f(x+1)=f(x)-f(x-1)

1 Like
3

Its a periodic function. If i recall correctly, f(x+6)=f(x) is the property which holds here.

Had it not been there, then yes, matrix exp would be a general solution. Since OP asked about logic of the above code only, i didnt go much into matrix exp.