EvbCFfp1XB

problem and my answer.

February 2013

problem TopCoder SRM569 DIV1 TheDevice

how to solve Simple Search, Iteration

source code

public class TheDevice {
public int minimumAdditional(String[] plates) {
int max = 0;
int n = plates.length;
int m = plates[0].length();
for (int j = 0; j < m; j++) {
int zero = 0;
int one = 0;
for (int i = 0; i < n; i++) {
if (plates[i].charAt(j) == '0') {
zero++;
} else {
one++;
}
}
int c = 0;
if (zero <= 1) {
c += 1 - zero;
}
if (one <= 2) {
c += 2 - one;
}
max = Math.max(max, c);
}
return max;
}
}

problem TopCoder SRM569 DIV2 MegaFactorialDiv2

how to solve Dynamic Programming

source code

public class MegaFactorialDiv2 {
private static final int modulus = 1000000009;

public int countDivisors(int N, int K) {
long[][] dp = new long[N + 2][K + 2];
dp[N][K] = 1;
for (int i = N; i >= 1; i--) {
for (int j = K; j >= 1; j--) {
dp[i][j - 1] += dp[i][j];
dp[i][j - 1] %= modulus;
dp[i - 1][j] += dp[i][j];
dp[i - 1][j] %= modulus;
}
}

long[] primeCount = new long[dp.length];
for (int i = 0; i < dp.length; i++) {
primeCount[i] = dp[i][0];
}

long[] primeCount2 = new long[dp.length];
for (int i = 2; i < primeCount2.length; i++) {
int c = 0;
int a = i;
for (int d = 2; a > 1; d++) {
while (a % d == 0) {
primeCount2[d] += primeCount[i];
primeCount2[d] %= modulus;
a /= d;
c++;
}
}
if (c > 1) {
primeCount2[i] = 0;
}
}

long count = 1;
for (int i = 2; i < primeCount2.length; i++) {
count *= primeCount2[i] + 1;
count %= modulus;
}

return (int) count;
}
}

This is a template of debug function.

source code

    private static final boolean DEBUG = true;
private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}
private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}
${imp:import(java.util.Arrays)}

problem TopCoder SRM569 DIV2 MegaFactorialDiv2

how to solve Simple Math

source code

public class MegaFactorialDiv2 {
private static final int modulus = 1000000009;

public int countDivisors(int N, int K) {
long[] primeCount = new long[1000];
for (int i = N, j = 0; i >= 2; i--, j++) {
long c = modC(j + (K - 1), j, modulus);
int a = i;
for (int div = 2; a > 1; div++) {
while (a % div == 0) {
primeCount[div] += c;
primeCount[div] %= modulus;
a /= div;
}
}
}

long count = 1;
for (int i = 0; i < primeCount.length; i++) {
if (primeCount[i] == 0) {
continue;
}
count *= primeCount[i] + 1;
count %= modulus;
}
return (int) count;
}

private static long modC(long n, long k, long modulus) {
k = Math.min(k, n - k);
long numerator = 1;
long denominator = 1;
for (long i = 0; i < k; i++) {
numerator = (numerator * (n - i)) % modulus;
denominator = (denominator * (i + 1)) % modulus;
}
return modDivide(numerator, denominator, modulus);
}

private static long modPow(long base, long exponent, long modulus) {
long pow = 1;
while (exponent > 0) {
if ((exponent % 2) == 1) {
pow = (pow * base) % modulus;
}
base = (base * base) % modulus;
exponent /= 2;
}
return pow;
}

// By Fermat's little theorem
private static long modInverse(long x, long modulus) {
if (!isPrime(modulus)) {
throw new IllegalArgumentException();
}
return modPow(x, modulus - 2, modulus);
}

private static boolean isPrime(long n) {
if (n == 2) {
return true;
}
if (n % 2 == 0) {
return false;
}
int L = (int) (Math.sqrt(n)) + 1;
for (int i = 3; i <= L; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static long modDivide(long numerator, long denominator, long modulus) {
return modMultiply(numerator, modInverse(denominator, modulus), modulus);
}

private static long modMultiply(long a, long b, long modulus) {
a %= modulus;
b %= modulus;
return (a * b) % modulus;
}
}

This is a template of modular arithmetic.

source code

    private static long modFactorial(long n, long modulo) {
long factorial = 1;
for (long i = 2; i <= n; i++) {
factorial = modMultiply(factorial, i, modulo);
}
return factorial;
}

private static long modC(long n, long k, long modulo) {
k = Math.min(k, n - k);
long numerator = 1;
long denominator = 1;
for (long i = 0; i < k; i++) {
numerator = (numerator * (n - i)) % modulo;
denominator = (denominator * (i + 1)) % modulo;
}
return modDivide(numerator, denominator, modulo);
}

private static long modP(long n, long k, long modulo) {
if (k > n) {
throw new IllegalArgumentException("k must not be greater than n. k=" + k + ",n=" + n);
}
long p = 1;
for (long i = 0; i < k; i++) {
p = modMultiply(p, n - i, modulo);
}
return p;
}

private static long modPow(long base, long exponent, long modulo) {
long pow = 1;
while (exponent > 0) {
if ((exponent & 1L) == 1L) {
pow = (pow * base) % modulo;
}
base = (base * base) % modulo;
exponent >>= 1;
}
return pow;
}

// By Fermat's little theorem
private static long modInverse(long x, long modulo) {
if (!isPrime(modulo)) {
throw new IllegalArgumentException("modulo is not prime.");
}
return modPow(x, modulo - 2, modulo);
}

private static boolean isPrime(long n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
if ((n & 1) == 0) {
return false;
}
long sqrtN = (long) Math.sqrt(n);
for (int i = 3; i <= sqrtN; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static long modDivide(long numerator, long denominator, long modulo) {
return modMultiply(numerator, modInverse(denominator, modulo), modulo);
}

private static long modMultiply(long a, long b, long modulo) {
a %= modulo;
b %= modulo;
return (a * b) % modulo;
}

private static long modSubtract(long a, long b, long modulo) {
a %= modulo;
b %= modulo;
return (a - b + modulo) % modulo;
}

private static long modAdd(long a, long b, long modulo) {
a %= modulo;
b %= modulo;
return (a + b) % modulo;
}


このページのトップヘ