CHN08 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

Author: ???
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza

PREREQUISITES:

Modulo, recurrences, pattern matching

PROBLEM:

A function f on integers is defined:

  • f(1) = A, f(2) = B.
  • For all integers x \ge 2, f(x) = f(x-1) + f(x+1).

Find f(N) \bmod (10^9 + 7).

QUICK EXPLANATION:

f is periodic with period 6, so f(N) is equal to f(N \bmod 6). (Just define f(0) = A-B.)

EXPLANATION:

At first glance, this problem seems to require standard techniques in solving general linear recurrences. While those techniques will work, they are quite overkill for this problem. Simple pattern spotting will do :slight_smile: (This solution is much faster to code and very easy to find, so you’ll probably be able to get AC earlier with it. The few minutes you save is sometimes significant.)

The key is to simply compute the first few terms. As an example, let’s say A = 11 and B = 9. Since f(x+1) = f(x) - f(x-1) (a rearrangement of the above), we have:

  • f(\,\,3) = f(\,\,2) - f(\,\,1) = -2
  • f(\,\,4) = f(\,\,3) - f(\,\,2) = -11
  • f(\,\,5) = f(\,\,4) - f(\,\,3) = -9
  • f(\,\,6) = f(\,\,5) - f(\,\,4) = 2
  • f(\,\,7) = f(\,\,6) - f(\,\,5) = 11
  • f(\,\,8) = f(\,\,7) - f(\,\,6) = 9
  • f(\,\,9) = f(\,\,8) - f(\,\,7) = -2
  • f(10) = f(\,\,9) - f(\,\,8) = -11
  • f(11) = f(10) - f(\,\,9) = -9
  • f(12) = f(11) - f(10) = 2
  • …

At this point, you might notice that the sequence repeats every 6 terms. Once you notice this, you might think to try to prove it rigorously before coding it. Though proving it is simple, you don’t have to do it; you just pray to the god of pattern matching and hope that this pattern will go on forever (or you trust your instinct). Though this doesn’t always work, with experience and intuition, you’ll eventually learn which of the unproven statements / observations you make may actually be true.

Note: Don’t forget to ensure that f(N) \bmod (10^9 + 7) is positive! Also, f(N) can be < -(10^9 + 7), so adding (10^9 + 7) just once isn’t enough to make f(N) positive.

Proving it

But as just mentioned, proving it is simple. Let’s first generalize the observation above, by actually using variables A and B:

  • f(3) = f(2) - f(1) = B - A
  • f(4) = f(3) - f(2) = -A
  • f(5) = f(4) - f(3) = -B
  • f(6) = f(5) - f(4) = A - B
  • f(7) = f(6) - f(5) = A
  • f(8) = f(7) - f(6) = B
  • f(9) = f(8) - f(7) = B - A
  • f(10) = f(9) - f(8) = -A
  • f(11) = f(10) - f(9) = -B
  • f(12) = f(11) - f(10) = A - B
  • …

Let’s now prove that this pattern will go on forever:

Claim: For n \ge 1, f(n) = f(n+6).

Proof:

Clearly, this is true for n = 1 and n = 2 (because f(1) = f(7) = A and f(2) = f(8) = B). Now, assume n > 2. Assume by induction that it is true for all 1 \le n' < n. So it must be true for n-2 and n-1. Then:

\begin{aligned} f(n) &= f(n-1) - f(n-2) \\\ &= f((n-1)+6) - f((n-2)+6) \\\ &= f(n+5) - f(n+4) \\\ &= f(n+6) \end{aligned}

This proves the claim.

End of proof

The general idea is that because each term f(n) depends only on the previous two terms (f(n-2), f(n-1)), once two consecutive terms repeat, the whole function will repeat forever. In our case, since (A,B) repeated, we’re sure that the following sequence will just repeat previous terms after that.

This also works even if f(n) is not a linear recurrence! If f(n) = g(f(n-2), f(n-1)) for some function g, then regardless of the nature of g, as long as you find a repeat of the pair (f(n-2),f(n-1)), the function f will repeat after that point. This also works if f was a recurrence that depended on more than two previous terms, say k \ge 2, though this time you’ll need to keep track of a k-tuple of values instead of a pair.

More properties

Let’s analyze f more deeply. Using generating functions, we can actually find a neat formula for f. (though it doesn’t necessarily yield any algorithmic improvements, it is interesting nonetheless.) It will also explain why every three terms almost repeats, except that you have to flip the sign first. To make things cleaner, in the following we’ll write f_n as a synonym of f(n). We’ll also define f(0) = A - B, so the recurrence still holds.

Let F(x) = f_0 + f_1x + f_2x^2 + f_3x^3 + \ldots. Then:

\begin{array}{rrrrrrr} F(x) = & f_0 &+ f_1x &+ f_2x^2 &+ f_3x^3 &+ f_4x^4 &+ \ldots \\\ xF(x) = & & f_0x &+ f_1x^2 &+ f_2x^3 &+ f_3x^4 &+ \ldots \\\ x^2F(x) = & & & f_0x^2 &+ f_1x^3 &+ f_2x^4 &+ \ldots \\\ \end{array}

Now, consider F(x) - xF(x) + x^2F(x), by adding like terms together. Since f_n = f_{n-1} - f_{n-2}, almost all terms will cancel out. The only nonzero terms are the constant and linear term. Thus, we have:

\begin{aligned} F(x) - xF(x) + x^2F(x) &= f_0 + f_1x \\\ (1 - x + x^2)F(x) &= f_0 + f_1x \\\ F(x) &= \frac{f_0 + f_1x}{1 - x + x^2} \\\ F(x) &= \frac{A-B + Ax}{1 - x + x^2} \end{aligned}

Now, let’s try to factorize 1 - x + x^2. It has two roots: \dfrac{1 \pm \sqrt{3}i}{2}. Let us use the symbol \psi and \bar{\psi} for \dfrac{1 + \sqrt{3}i}{2} and \dfrac{1 - \sqrt{3}i}{2}, respectively (\bar{x} denotes complex conjugation). Thus, 1 - x + x^2 must be equal to (x - \psi)(x - \bar{\psi}). But since \psi\bar{\psi} = 1, we get:

\begin{aligned} 1 - x + x^2 &= (x - \psi)(x - \bar{\psi}) \\\ &= \psi\bar{\psi}(x - \psi)(x - \bar{\psi}) \\\ &= (\bar{\psi}x - \bar{\psi}\psi)(\psi x - \psi\bar{\psi}) \\\ &= (\bar{\psi}x - 1)(\psi x - 1) \\\ &= (1 - \psi x)(1 - \bar{\psi}x) \end{aligned}

Note that \psi and \bar{\psi} are both primitive 6 th roots of unity, so \psi^6 = \bar{\psi}^6 = 1. (verify)

Back to F(x), we get:

\begin{aligned} F(x) &= \frac{A-B + Ax}{1 - x + x^2} \\\ F(x) &= \frac{A-B + Ax}{(1 - \psi x)(1 - \bar{\psi}x)} \end{aligned}

At this point, let’s use the method of partial fractions, to obtain

F(x) = \frac{C}{1 - \psi x} + \frac{D}{1 - \bar{\psi}x}

where C and D are constants that we don’t know yet. This form is very useful to us because of the equality:

\frac{1}{1 - rx} = 1 + rx + r^2x^2 + r^3x^3 + \ldots

which means that the coefficient of x^n in F(x) is just C\psi^n + D\bar{\psi}^n, giving us a formula for f(n). Right away, this tells us that f(n) is periodic with period 6, because \psi and \bar{\psi} are both primitive 6 th roots of unity. It also explains why f(n) = -f(n+3): It’s because \psi^3 = \bar{\psi}^3 = -1.

To compute C and D, simply add the two fractions together and equate coefficients:

\begin{aligned} F(x) &= \frac{C}{1 - \psi x} + \frac{D}{1 - \bar{\psi}x} \\\ F(x) &= \frac{(C + D) - (C\bar{\psi} + D\psi)x}{(1 - \psi x)(1 - \bar{\psi}x)} \end{aligned}

Thus, we get C + D = A - B and C\bar{\psi} + D\psi = A. By solving this system, we get

D = -\frac{A(\psi-2)+B(\psi+1)}{3}
C = -\frac{A(\bar{\psi}-2)+B(\bar{\psi}+1)}{3}

This gives us the following formula for f(n):

f(n) = -\frac{1}{3}\left[\left(A(\psi-2)+B(\psi+1)\right)\psi^n + \left(A(\bar{\psi}-2)+B(\bar{\psi}+1)\right)\bar{\psi}^n\right]

In general, for any periodic sequence g(n) with period k, g always has some formula that looks like:

g(n) = a_0 + a_1\omega_k^n + a_2\omega_k^{2n} + a_3\omega_k^{3n} + \ldots + a_{k-1}\omega_k^{(k-1)n}

where \omega_k is a primitive k th root of unity (so \{1, \omega_k, \omega_k^2, \ldots, \omega_k^{k-1}\} is the complete set of k th roots of unity).

Time Complexity:

O(1)

AUTHOR’S AND TESTER’S SOLUTIONS:

[setter][333]
[tester][444]
[editorialist][555]

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.

2

Why is my answer not working? I have implemented what you just said and the test cases work fine:

#include <iostream>
using namespace std;
int main(){
    int i;
    cin >> i;
    int a,b,N;
    for (int j = 0; j< i; j++){
        cin >> a;
        cin >> b;
        cin >> N;
        N=(N+6%6+6)%6;
        if (N==0){
            cout << (a-b+1000000007)%1000000007 << endl;
        }
        if (N==1){
            cout << (a+1000000007)%1000000007 << endl;
        }
        if (N==2){
            cout << (b+1000000007)%1000000007 << endl;
        }
        if (N==3){
            cout << (b-a+1000000007)%1000000007 << endl;
        }
        if (N==4){
            cout << (1000000007-a)%1000000007 << endl;
        }
        if (N==5){
            cout << (1000000007-b)%1000000007 << endl;
        }
    }
    return 0;
}
3

Whats wrong with this code?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define all(a) a.begin(),a.end()
#define t int t; cin>>t; while(t--)
#define show(a) for(i=0;i<a.size();i++) cout<<a[i]<<" ";
#define s(n) scanf("%d",&n);
#define ss(n,m) int n,m;scanf("%d%d",&n,&m);
#define p printf
#define u(i,a,b) for(i=a;i<b;i++)
#define d(i,a,b) for(i=a;i>b;i--)
#define mod 1000000007
#define in vi a(n);u(i,0,n) s(a[i])
#define pb push_back
int main()
{
   int n;
   t
   {
       ss(a,b)
       s(n) n=n%6;
       vi A{a-b,a,b,b-a,-a,-b};
       p("%d\n",(mod+A[n])%mod);
   }
}
4

@savage_coder

Overflow is being savage to you. Try changing data type to long long int and see.

Also, (mod + A[n]) need not necessarily positive always. make it (mod + A[n]%mod)%mod and see.

5

Help me,please;what’s wrong with the code?

#include<iostream>
using namespace std;
long long int f(long long int index[],int n) {
	const  long long int m = 1'000'000'007;
	auto  x = index[n % 6];
	return (x%m + m) % m;
}
int main() {
	int n,a, b, c;
	cin >> n;
	while (n--) {
		cin >> a >> b >> c;
		long long int arr[] = { a,b,b - a,-a,-b,a - b };
		cout << f(arr, c-1);
	}
	
}
6

I would appreciate if anyone could help me to show me the problem with my code. I got the wrong answer but I think my logic is correct.

code link

7

This solution worked CodeChef: Practical coding for everyone. If anyone wants some help … see my code it worked fine.

8

I answer my own question: OVERFLOW!

9

Thanks @vijju123 that worked :slight_smile: