rpthegreat's blog

Find the value of f(T) for big value T
By rpthegreat, 7 years ago, In English

I am trying to solve a problem which is described below,

Given value of f(0) and k , which are integers.

I need to find value of f( T ). where T<=10^10 (10 power 10)

Recursive function is,

f(n) = 2*f(n-1) , if 4*f(n-1) <=k 

k - ( 2*f(n-1) )      ,  if 4*f(n-1) > k

If i solve by brute force then it will give me TLE. The code will run 10^10(10 power 10) time in worst case that gives me Time Limit Exceed. I need more efficient solution for this problem. Please help me. I don't know the correct algorithm.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rpthegreat (previous revision, new revision, compare).

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

Auto comment: topic has been updated by rpthegreat (previous revision, new revision, compare).

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

What are the constrainsts of k and f0?

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

    f0 <= 10 power 9

    k <= 2*(10 power 9)

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

      If k = 1 and f(0) = 109, the answer is very large. Do you need to find it modulo a prime? If not, you probably missed some inequality, like 2f(0) ≤ k.

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

        Sir , If 4*(f(n-1) >k ) then f(n)= k-(2*f(n-1) ) sorry for typing mistakes

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

        yes 2f(0)<=k

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

          In this case all f(n) are between 0 and k / 2. . .

          You need to use fast exponentiation to find . Use the inequality 0 ≤ f(n) ≤ k / 2 to find the sign ( ± ).

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

Why don't you give link to the problem?

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

    I have not problem link because it is assigned by my senior friend. so problem is on my notebook. But if you have doubt regarding problem statement then please comment below.

    → Reply
»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

u can print a value table in ur own computer,about every 100000 print one f(i),then u only need to calculate 100000 times in worst case.(u can adjust the interval 2 satisfy the limit of problem)

→ Reply