10328 - Coin Toss

[Sanny]

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]

Got AC now. Had a mistake in my bigint.

[sohel]

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]

Yes, my previous and your current i/o all are correct. I had a mistake in my subtraction code.


Regards
Sanny

[predicate]

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));
    }
  }
}