Category Archives: DP + bitmask
12063 – Zeros and Ones
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;
public class ZerosAndOnes {
private static long[][][] dp;
private static int k;
private static int n;
private static int[] pow;
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int tt = Integer.parseInt(buf.readLine());
StringBuilder ans = new StringBuilder("");
for (int t = 1; t <= tt; t++) {
StringTokenizer str = new StringTokenizer(buf.readLine());
n = Integer.parseInt(str.nextToken());
k = Integer.parseInt(str.nextToken());
if (k == 0){
ans.append("Case " + t + ": 0\n");
continue;
}
pow = new int[64];
pow[0] = 1 % k;
for (int i = 1; i < 64; i++)
pow[i] = (pow[i - 1] * 2) % k;
dp = new long[n][n + 1][k];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
Arrays.fill(dp[i][j], -1);
long tot = go(1, 1, 0, pow[n - 1]);
ans.append("Case " + t + ": " + tot + "\n");
}
System.out.print(ans);
}
private static long go(int index, int c1, int c0, int rem) {
if (index == n && c1 == c0 && rem == 0)
return 1;
else if (index == n)
return 0;
else if (dp[index][c1][rem] != -1)
return dp[index][c1][rem];
else {
long tot = 0;
int nextRem = pow[index - 1];
nextRem += rem;
nextRem %= k;
tot += go(index + 1, c1 + 1, c0, nextRem);
tot += go(index + 1, c1, c0 + 1, rem);
return dp[index][c1][rem] = tot;
}
}
}
11472 – Beautiful Numbers
package DP_bitmask;
import java.util.Arrays;
import java.util.Scanner;
public class BeautifulNumbers {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
int m = sc.nextInt();
if (m < n)
System.out.println(0);
else {
long[][][] dp = new long[m][(1 << n) + 1][21];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
Arrays.fill(dp[i][j], -1);
long sum = 0;
sum += find(1, 0, 0, dp, true) % 1000000007;
for (int i = 1; i < n; i++)
sum += find(1, 1 << i, i, dp, false) % 1000000007;
System.out.println(sum % 1000000007);
}
}
}
static int n;
private static long find(int place, int bitmask, int prev, long[][][] dp,
boolean leading) {
if (prev == -1 || prev == n)
return 0;
if (place == dp.length && bitmask == (1 << n) - 1)
return 1;
if (place == dp.length)
return 0;
if (dp[place][bitmask][prev] != -1)
return dp[place][bitmask][prev];
else {
long sum = 0;
if (prev == 0 && leading) {
sum += find(place + 1, bitmask, 0, dp, true) % 1000000007;
for (int i = 1; i < n; i++)
sum += find(place + 1, 1 << i, i, dp, false) % 1000000007;
} else {
sum += find(place + 1, bitmask | (1 << (prev + 1)), prev + 1,
dp, false) % 1000000007;
sum += find(place + 1, bitmask | (1 << (prev - 1)), prev - 1,
dp, false) % 1000000007;
}
return dp[place][bitmask][prev] = sum % 1000000007;
}
}
}
10651 – Pebble Solitaire
package DP_bitmask;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class PebbleSolitaire {
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int t = Integer.parseInt(buf.readLine());
while (t-- > 0) {
char[] p = buf.readLine().toCharArray();
int bitmask = 0;
for (int i = 0; i < 12; i++)
if (p[i] == 'o')
bitmask |= (1 << (11 - i));
int[] dp = new int[(1 << 12) + 1];
Arrays.fill(dp, -1);
int min = find(bitmask, dp);
System.out.println(min);
}
}
private static int find(int bitmask, int[] dp) {
int x = check(bitmask);
if (x != -1)
return x;
else if (dp[bitmask] != -1)
return dp[bitmask];
else {
int min = 12;
for (int i = 0; i < 11; i++) {
if ((bitmask & (1 << i)) != 0
&& (bitmask & (1 << (i + 1))) != 0) {
if (i == 0) {
if ((bitmask & (1 << i + 2)) == 0) {
min = Math
.min(min,
find((((bitmask | (1 << (i + 2)))) & (~(1 << i)))
& (~(1 << (i + 1))), dp));
}
} else if (i == 10) {
if ((bitmask & (1 << i - 1)) == 0) {
min = Math
.min(min,
find((((bitmask | (1 << (i - 1)))) & (~(1 << i)))
& (~(1 << (i + 1))), dp));
}
} else {
if ((bitmask & (1 << i - 1)) == 0) {
int y = bitmask;
y |= (1 << (i - 1));
y &= ~(1 << i);
y &= ~(1 << (i + 1));
min = Math.min(min, find(y, dp));
}
if ((bitmask & (1 << i + 2)) == 0) {
int y = bitmask;
y |= (1 << (i + 2));
y &= ~(1 << i);
y &= ~(1 << (i + 1));
min = Math.min(min, find(y, dp));
}
}
}
}
return dp[bitmask] = min;
}
}
private static int check(int bitmask) {
int count = 0;
for (int i = 0; i < 11; i++) {
if ((bitmask & (1 << i)) == 0)
count++;
if ((bitmask & (1 << i)) != 0 && ((bitmask & (1 << (i + 1))) != 0))
return -1;
}
if ((bitmask & (1 << 11)) == 0)
count++;
return 12 - count;
}
}
10911 – Forming Quiz Teams
I got the same idea as competitive programming but instead of bitwise shifts i would have used just an array of zeros and ones but i learned how to use it 🙂
package DP_bitmask;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.Arrays;
class FormingQuizTeams {
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int test = 1;
while (true) {
int n = Integer.parseInt(buf.readLine());
if (n == 0)
break;
int[][] points = new int[2 * n][2];
double[] dp = new double[(int) (Math.pow(2, 2 * n) + 1)];
Arrays.fill(dp, -1);
for (int i = 0; i < 2 * n; i++) {
String[] line = buf.readLine().split(" ");
int x = Integer.parseInt(line[1]);
int y = Integer.parseInt(line[2]);
points[i][0] = x;
points[i][1] = y;
}
double min = find(0, points, dp, 2 * n);
BigDecimal bd = new BigDecimal(min);
bd = bd.setScale(2, BigDecimal.ROUND_HALF_UP);
System.out.println("Case " + (test++) + ": " + bd);
}
}
private static double find(int i, int[][] points, double[] dp, int m) {
if (i == (1 << m) - 1)
return 0;
if (dp[i] != -1)
return dp[i];
else {
double min = Double.MAX_VALUE;
for (int j = 0; j < m; j++)
if ((i & (1 << j)) == 0) {
for (int k = j + 1; k < m; k++)
if ((i & (1 << k)) == 0) {
double x = calc(j, k, points);
min = Math.min(
min,
x
+ find(i | (1 << k) | (1 << j),
points, dp, m));
}
}
return dp[i] = min;
}
}
private static double calc(int j, int k, int[][] points) {
return Math.sqrt((points[j][0] - points[k][0])
* (points[j][0] - points[k][0]) + (points[j][1] - points[k][1])
* (points[j][1] - points[k][1]));
}
}
algorithmcafe 