## 10328 - Coin Toss

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
My WA code gives the same output. Some more I/O -

Input:

Code: Select all

``````100 1
100 2
100 100
100 50
100 99
50 1
89 88
1 1
22 11
45 40
58 7
``````
Output:

Code: Select all

``````1267650600228229401496703205375
1267650599300856709303624206200
1
29273397577908224
3
1125899906842623
3
1
13312
112
55279115543405360
``````
BTW, I'm using a slightly different recurrence. My recurrence is :

Code: Select all

``````s[i] = 2^i ; [0<= i <k]
s[i] = s[i-1] + s[i-2] + .... + s[i-k]; [k<= i <= n]
final result = 2^n - s[n];
``````

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
Got AC now. Had a mistake in my bigint.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
to Sanny:
The input/output you posted... are they correct.
My code produces the same answer but gets WA..

input

Code: Select all

``````50 12
16 1
100 21
100 22
100 23
100 24
99 67
``````
output

Code: Select all

``````5491234246656
65535
24480620377468758850551808
12089228436375214101387520
5969064303308861289264288
2946755075273927119863799
73014444032
``````
Can someone confirm whether the above output is correct for the corresponding input.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
Yes, my previous and your current i/o all are correct. I had a mistake in my subtraction code.

Regards
Sanny

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm

### Re: 10328 - Coin Toss

I wrote a recursive relation as follow :
toss(n, c, m) = toss(n-1, c+1, max(c+1,m)) + toss(n-1,0,m)
n = number of tosses left
c = consecutive heads
m = max number of consecutive heads that have occurred till now

I wrote a dp solution for this problem and have checked the answers on http://www.udebug.com/UVa/10328. The solution is correct, but I get TLE on the judge
The max runtime of the solution would be n * c * m which is 10^6 operations at max. I cannot understand why I get TLE ?

I have attached my code below :

Code: Select all

``````import java.util.Scanner;
import java.math.BigInteger;

class Main {
public static int k;
public static BigInteger[][][] memo = new BigInteger[110][110][110];
public static BigInteger minusOne = BigInteger.ZERO.subtract(BigInteger.ONE);

public static BigInteger toss(int n, int c, int m) {
if (n == 0) {
if (m >= k) {
return BigInteger.ONE;
} else {
return BigInteger.ZERO;
}
}
if (!minusOne.equals(memo[n][c][m])) {
return memo[n][c][m];
}
BigInteger ans = BigInteger.ZERO;
ans = ans.add(toss(n - 1, c + 1, Math.max(c + 1, m)));
ans = ans.add(toss(n - 1, 0, m));
memo[n][c][m] = ans;
return ans;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n;
while (sc.hasNextInt()) {
n = sc.nextInt();
k = sc.nextInt();
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int l = 0; l <= n; l++) {
memo[i][j][l] = minusOne;
}
}
}
System.out.println(toss(n, 0, 0));
}
}
}
``````