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
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:
Then transcribe:
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:
|
|
Last edited on
Like so.
First subtract 2 from your expressions to get f(n) on the left hand side.
|
|
First subtract 2 from your expressions to get f(n) on the left hand side.
> 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.
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.
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?
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
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:
and here are the f(n) values for smallish n to check the exact result against that obtained by recursion:
EDIT: Sadly the OP has decided to change his initial values.
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?
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!!!
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?
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
So which particular Codechef example did that come from? (It doesn't appear to be a live competition).
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
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.>
<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