FarmerAbdulAlim's blog

SPOJ Problem-Flibonakki
By FarmerAbdulAlim, 11 years ago, In English

Problem Link

I cannot optimize this code anymore. Please let me know how to optimize.

Thanks in advance. My Code

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it
  • I have not solved it. But, if were in your situation I would try following ideas to get rid of TLE:-
  • Implement matrix mult(matrix &x,matrix &y) function in matrix bigmod(matrix b,LL p) function
  • r.mat[i][j]=sum%mod; can be replaced with while(r.mat[i][j]>=mod)r.mat[i][j]-=mod;
  • i would try to avoid long long data type and use some explicit cast when needed.
  • if that's also not enough i would try fastIO(use getchar() to take input).
  • Also read the comments after the problem statement. It might be helpful for you.
→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

In constant optimisation problems, especially in those which have enormous input data, it is good to write your own function for scanning integers. Below is the procedure i have used in many problems:

#define gc getchar_unlocked
inline int geti() {
  register int c = gc(), x = 0, sign = 1;
  for( ; c != '-' && (c < '0' || c > '9'); c = gc());
  if(c == '-') c = gc(), sign = -1;
  for( ; c >= '0' && c <= '9'; c = gc()) x = (x<<1) + (x<<3) + c-'0';
  return sign*x;
}
→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The most significant thing you need to optimize is storing the result of base^2,base^4,base^8.... So when calculating base^n you can just multiply the corresponding power of twos like base^7 = base * base^2 * base^4

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +60 Vote: I do not like it

Nobody has really helped you, but your post got -8 rating. Codeforces community is so awful...

In fact, if you have an N × N matrix (let's call it M), it's possible to calculate ME × V (V is a vector) in , not in . To do so, you need to precalculate M1, M2, M4, M8.... Then, if you need to calculate, for example, M13 × V, you can just use the following formula: M13 × V = M8 × (M4 × (M1 × V)).

Sorry for my pidgin English, but in Russian (my native language) I'd explain this exactly the same way.

UPD. With this idea I instantly got AC in Java in 2.7s without any additional optimizations.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Nice trick, didn't know about it before :)

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    AlexanderBolshakov , I always become happy when I learn a new thing. This is a very good idea. Got AC in 2.15s. Thanks :)

    Code

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    AFAIK, calculating from will take .
    so if we continue calculating until , won't the precalculation itself take ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, the precalculation takes . But in such problems this time is negligible, because the precalculation is performed only once, but calculation of ME × V — many times.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        i understand now. there are multiple queries, each with different value of .
        thanks for ur help! :)

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got AC with a 3x3 matrix and optimizations, but I heard that there is a way of doing with just a 2x2 matrix. Can someone tell me how to find this 2x2 matrix?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    PROBLEM: G(n) is defined as G(n) = G(n-1) + f(4n-1) , for n > 0 and G(0) = 0 f(i) is ith Fibonacci number. Given n you need to evaluate G(n) modulo 1000000007.

    MY SOLN: use/prove: G(n) = f(2n) * f(2n + 1),

    FOR EXTRA SPEED: use the following recurrences:

    f(2n) = f(n)[2*f(n+1) – f(n)],

    f(2n + 1) = f(n)^2 + f(n+1)^2

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice! Fibonacci has so many interesting properties, it doesn't stop to amaze me.

      For this problem I used the idea that G(n) = 7*G(n-1) — G(n-2) + 1 I don't know how to prove it, but it works.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Submitted in one GO without extra speed. Just tell me how u got the relations for extra speed

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Link To Solution -> Code
    Passed in 0.10 sec

    → Reply