DP

Pages: 12
A function is defined as
f(n+2) = 2*f(n+1) - f(n) + 2 , if n is even
f(n+2) = 3*f(n), if n is odd
f(1) = 1 ,f(2) = 1
n > 0
Help me code this function by recursion or dp or matrix exponential?
And can we solve without using recursion or dp??
if n can be equal upto 10 power 5
Last edited on
Looks like you've made a typo writing the definition - you've got two cases for odd n. I've guessed at what you meant.

First, let q = n + 2 to obtain a more workable definition - this is the tricky part:
f(q) = 2*f(q - 1) - f(q - 2) + 2 if q - 2 is odd
f(q) = 3*f(q - 2) if q - 2 is even
f(0) = f(1) = 1;


Then transcribe:
1
2
3
4
5
6
7
8
int f(int q)
{
  if (q <= 1) return 1;
  
  return (is_odd(q - 2)) 
    ? 2 * f(q - 1) - f(q - 2) + 2
    : 3 * f(q - 2); 
}
Last edited on
see again the question, edited it

Last edited on
Like so.
1
2
3
4
5
6
int func(int n) {
  if ( n == 0 ) return 1;
  if ( n == 1 ) return 1;
  if ....  // make your own tests here
    return func(n-1);  // make your own expressions here
}


First subtract 2 from your expressions to get f(n) on the left hand side.
How can i account for the large inputs?
for n = 99 or n = 459?
Last edited on
> for n = 99 or n = 459?
You have all those n-1 and n-2 in your recursive calls.

Eventually, you'll whittle down the value of n to either 0 or 1, and you'll get the trivial answer of 1 returned.


One function call spawns two ... leading to exponential growth. (Unless you use memoisation to avoid that).)

Are you sure that you want to do this by (function) recursion?

Just use an array and a for loop.

Actually, if f(n+2)=3.f(n) for n odd, then it will grow pretty quickly anyway for odd numbers.
Last edited on
how to do dp in this?? can you help me?
or just an array and a for loop??
for loop will also take time
how to use tabulation or memoization in this?
Last edited on
@counter strike,

IF that is your correct recursion relation then you can WRITE DOWN THE EXACT ANSWER EXPLICITLY; you don't actually need to use any of the methods you suggest.

However,
(1) You have changed your post several times, so I'm holding fire.
(2) If n is 100000 then the answer is
(350000+1)/2

and you aren't going to be able to store that in anything except a (VERY) big integer. (EDIT: revised value later, after the OP changed the question).

I don't think you have told us the whole problem. Is there a modulo operation involved?


Just in case you change it again, this is your current problem:
A function is defined as
f(n+2) = 2*f(n+1) - f(n) + 2 , if n is even
f(n+2) = 3*f(n), if n is odd
f(0) = 1 ,f(1) = 1
n > 0

and here are the f(n) values for smallish n to check the exact result against that obtained by recursion:
n, f(by recursion), f(exact)
0  1  1
1  1  1
2  3  3
3  3  3
4  5  5
5  9  9
6  15  15
7  27  27
8  41  41
9  81  81
10  123  123
11  243  243
12  365  365
13  729  729
14  1095  1095
15  2187  2187
16  3281  3281
17  6561  6561
18  9843  9843
19  19683  19683
20  29525  29525
21  59049  59049
22  88575  88575
23  177147  177147
24  265721  265721
25  531441  531441
26  797163  797163
27  1594323  1594323
28  2391485  2391485
29  4782969  4782969
30  7174455  7174455
31  14348907  14348907
32  21523361  21523361
33  43046721  43046721
34  64570083  64570083
35  129140163  129140163
36  193710245  193710245
37  387420489  387420489
38  581130735  581130735
39  1162261467  1162261467
40  1743392201  1743392201


EDIT: Sadly the OP has decided to change his initial values.
Last edited on
A function is defined as
f(n+2) = 2*f(n+1) - f(n) + 2 , if n is even
f(n+2) = 3*f(n), if n is odd
f(1) = 1 ,f(2) = 1
You have to answer multiple queries. In each query, you are given two integers L and R and you are required to determine the value of

(f(L) + f(L+1) + ... + f(R-1) + f(R))\ modulo\ P
You have to answer multiple queries. In each query, you are given two integers L and R and you are required to determine the value of
(f(L) + f(L+1) + ... + f(R-1) + f(R))\ modulo\ P
and P = 1000000007

Input Format

First line: Two integers T and, P where T represents the number of queries
Each of the next T lines: Two integers L and R.
L and R<= 10 POWER 18
p <= 10 power 9

Sample input
3 100000007
3 4
4 4
10 99
Sample output
As 3 is odd, f(3) = 3 * f(1) = 3 * 1 = 3

As 4 is even, f(4) = 2*f(3) - f(2) + 2 = 2*3 - 1 + 2 = 7

So, when L is 3, R is 4 and P is 100000007, answer is (3 + 7)%100000007 = 10

Similarly, when L is 4, R is 4 and P is 100000007, answer is (7) %100000007 = 7

This is the coding question that i am working on?
Last edited on
Your answer for f(4) is wrong (because your answer for f(2) is wrong).

EDIT: Now you've changed the question ... yet again!!!
Last edited on
sorry , sir it was a typo not intentional
f(1) =1 and f(2) =1 , then how can i do it for large numbers?
Last edited on
f(1) =1 and f(2) =1 , hen how can i do it for large numbers?


Well, in your previous statement (which wasn't the whole problem, was it?) you had
f(0) =1 and f(1) =1


So the whole set of values I got were then wrong ..ggrrr!

Anyway, try again:
work out the EXACT solution for f(n) (easy for odd numbers; requires a bit of double thinking for even numbers - that's a hint!).
Then work out the EXACT solution for the sum f(L) + ... + f(R) (sums of geometric progressions will help).

The modulo operation will only be involved in computing large powers of 3.


In future:
(1) write down the question accurately;
(2) write down the whole question.


Here are your re-computed f(n) values for small n:
n, f(by recursion), f(exact)
1  1  1
2  1  1
3  3  3
4  7  7
5  9  9
6  13  13
7  27  27
8  43  43
9  81  81
10  121  121
11  243  243
12  367  367
13  729  729
14  1093  1093
15  2187  2187
16  3283  3283
17  6561  6561
18  9841  9841
19  19683  19683
20  29527  29527
21  59049  59049
22  88573  88573
23  177147  177147
24  265723  265723
25  531441  531441
26  797161  797161
27  1594323  1594323
28  2391487  2391487
29  4782969  4782969
30  7174453  7174453
31  14348907  14348907
32  21523363  21523363
33  43046721  43046721
34  64570081  64570081
35  129140163  129140163
36  193710247  193710247
37  387420489  387420489
38  581130733  581130733
39  1162261467  1162261467
40  1743392203  1743392203


Revise f(100000) to (350000+5)/2
Last edited on
using bit manipulation for the power
So which particular Codechef example did that come from? (It doesn't appear to be a live competition).
Yeah, I got bored with the shifting sands.
@lastchance it is giving overflow for n= 50, how to do it?
Read the question.

Use the modulo operator, %.
although i tried in java but logic remains same
import java.util.*;
public class Main
{
static boolean is_even(long q){
if(q%2==0){
return true;
}
else{
return false;
}
}

static long f(long q)
{
if (q <= 2) return 1;

return (is_even(q - 2))
? 2 * f(q - 1) - f(q - 2) + 2
: 3 * f(q - 2);
}

public static void main(String[] args) {

long y = f(10);
long z= f(99);
long x = (y+z)%1000000007;

System.out.println(x);
}
}
it gives answer of 70282652 but answer is 26030209
Last edited on
You have to use % during the iterations themselves, not just on the final result. In other words, you have to plan your logic such that an overflow can't happen in the first place.

<Edit: I did not report you, but no I'm not giving help through PM. I don't even like these challenges. It's up to you to figure out how to correctly iterate without overflowing.>
Last edited on
Pages: 12