EvbCFfp1XB

problem and my answer.

May 2013

I have learned cast. Because I was not sure about the details of the cast.

source code

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class CastTest {
@Test
public void testDoubleToInt() {
for (int i = 0; i < 1e5; i++) {
double a = randomInt((int) -1e9, (int) 1e9);
assertEquals((int) a, Math.floor(a), 0);
}
{
double a = Integer.MAX_VALUE;
a *= 2;
assertEquals((int) a, Integer.MAX_VALUE);
a *= -1;
assertEquals((int) a, Integer.MIN_VALUE);
}
}

private static final int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

@Test
public void testLongToInt() {
int size = Integer.SIZE;
final long mask = (1L << size) - 1;
long a = 0;
for (int i = 0; i < 1e5; i++) {
a ^= (1L << (int) (64 * Math.random()));
long cast = (a & (1L << (size - 1))) == 0 ? a & mask : a | flip(mask);
assertEquals((int) a, cast);
assertEquals(toBinaryString((int) a), toBinaryString(a).substring(64 - size, 64));
}
}

@Test
public void testLongToShort() {
int size = Short.SIZE;
final long mask = (1L << size) - 1;
long a = 0;
for (int i = 0; i < 1e5; i++) {
a ^= (1L << (int) (64 * Math.random()));
long cast = (a & (1L << (size - 1))) == 0 ? a & mask : a | flip(mask);
assertEquals((short) a, cast);
assertEquals(toBinaryString((short) a), toBinaryString(a).substring(64 - size, 64));
}
}

@Test
public void testLongToByte() {
int size = Byte.SIZE;
final long mask = (1L << size) - 1;
long a = 0;
for (int i = 0; i < 1e5; i++) {
a ^= (1L << (int) (64 * Math.random()));
long cast = (a & (1L << (size - 1))) == 0 ? a & mask : a | flip(mask);
assertEquals((byte) a, cast);
assertEquals(toBinaryString((byte) a), toBinaryString(a).substring(64 - size, 64));
}
}

private static final long flip(long mask) {
return -1L ^ mask;
}

private static final String toBinaryString(byte a) {
StringBuilder binary = new StringBuilder();
for (int i = 7; i >= 0; i--) {
binary.append(((a >> i) & 1) == 0 ? "0" : "1");
}
return binary.toString();
}

private static final String toBinaryString(short a) {
StringBuilder binary = new StringBuilder();
for (int i = 15; i >= 0; i--) {
binary.append(((a >> i) & 1) == 0 ? "0" : "1");
}
return binary.toString();
}

private static final String toBinaryString(int a) {
StringBuilder binary = new StringBuilder();
for (int i = 31; i >= 0; i--) {
binary.append(((a >> i) & 1) == 0 ? "0" : "1");
}
return binary.toString();
}

private static final String toBinaryString(long a) {
StringBuilder binary = new StringBuilder();
for (int i = 63; i >= 0; i--) {
binary.append(((a >> i) & 1L) == 0 ? "0" : "1");
}
return binary.toString();
}
}


I have learned XorShift by OgieKako,hama_du,wleiteandtomerun.

source code

import static org.junit.Assert.assertEquals;

import java.util.Random;

import org.junit.Test;

public final class XorShift {
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;
private int w = 88675123;

/**
* Returns the next pseudorandom {@code int} value, greater than or equal to {@code Integer.MIN_VALUE} and less than or equal to {@code Integer.MAX_VALUE}.
*
* @return the next pseudorandom
*/
public final int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

/**
* Returns the next pseudorandom {@code double} value, greater than or equal to {@code 0.0} and less than {@code 1.0}.
*
* @return the next pseudorandom
*/
public final double nextDouble() {
return (double) (nextInt() + (1L << 31)) / (1L << 32);
}

/**
* Returns the next pseudorandom {@code long} value.
*
* @return the next pseudorandom
*/
public final long nextLong() {
return ((long) nextInt() << 32) ^ (((long) nextInt() << 32) >>> 32);
}

@Test
public void testLong() {
XorShift xs = new XorShift();
// for (int i = 0; i < 1e6; i++)
{
long nextLong = xs.nextLong();
System.out.format("%d\n", nextLong);
}
}

@Test
public void testMax() {
XorShift xs = new XorShift();
xs.x = -1044973;
xs.y = -96493;
xs.z = 1670;
xs.w = 59770;
assertEquals(Integer.MAX_VALUE, xs.nextInt());
xs.x = -1044973;
xs.y = -96493;
xs.z = 1670;
xs.w = 59770;
assertEquals(1.0, xs.nextDouble(), 1e-9);
}

@Test
public void testMin() {
XorShift xs = new XorShift();
xs.x = -1044908;
xs.y = 25266;
xs.z = 13753;
xs.w = -183547;
assertEquals(Integer.MIN_VALUE, xs.nextInt());
xs.x = -1044908;
xs.y = 25266;
xs.z = 13753;
xs.w = -183547;
assertEquals(0, xs.nextDouble(), 0);
}

@Test
public void test() {
System.out.format("%f %f\n", timeXorShift(), timeRandom());
assertEquals(true, timeXorShift() < timeRandom());
}

private double timeRandom() {
Random random = new Random();
long start = System.nanoTime();
for (int i = 0; i < 1e6; i++) {
random.nextDouble();
}
return (System.nanoTime() - start) / 1e9;
}

private double timeXorShift() {
XorShift random = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < 1e6; i++) {
random.nextDouble();
}
return (System.nanoTime() - start) / 1e9;
}
}


I have learned BitSet by farnetto's code.

source code

import java.util.Arrays;
import java.util.BitSet;

import org.junit.Test;

public class BitSetExample {
@Test
public void test() {
final int n = 10;
debug("2", getMultiple(n, 2));
debug("3", getMultiple(n, 3));
{
BitSet two = getMultiple(n, 2);
two.or(getMultiple(n, 3));
debug("or", two);
}
{
BitSet two = getMultiple(n, 2);
two.and(getMultiple(n, 3));
debug("and", two);
}
{
BitSet two = getMultiple(n, 2);
two.xor(getMultiple(n, 3));
debug("xor", two);
}
{
BitSet two = getMultiple(n, 2);
two.andNot(getMultiple(n, 3));
debug("andNot", two);
}
{
BitSet three = getMultiple(n, 3);
three.andNot(getMultiple(n, 2));
debug("andNot", three);
}
{
debug("intersects", getMultiple(n, 2).intersects(getMultiple(n, 3)));
}
{
debug("cardinality", getMultiple(n, 2).cardinality());
debug("cardinality", getMultiple(n, 3).cardinality());
}
}

private BitSet getMultiple(int n, int m) {
BitSet multiple = new BitSet();
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
multiple.set(i);
}
}
return multiple;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

}



truth table
a = 0011
b = 0101
a ^ b = 0110

properties

(a ^ b) == (b ^ a)
proof
a = 0011
b = 0101
a ^ b = 0110
b ^ a = 0110

(a ^ 0) == a
proof
a = 01
0 = 00
a ^ 0 = 01

(a ^ a) == 0
proof
a = 01
a ^ a = 00

((a ^ b) ^ c) == (a ^ (b ^ c))
proof
a = 00001111
b = 00110011
c = 01010101
a ^ b = 00111100
(a ^ b) ^ c = 01101001
b ^ c = 01100110
a ^ (b ^ c) = 01101001


source code

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class XorTest {
@Test
public void test() {
{
System.out.format("truth table\n");
int a = 0 * 8 + 0 * 4 + 1 * 2 + 1 * 1;
int b = 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1;
System.out.format("a = %s\n", toBinaryString(a).substring(32 - 4, 32));
System.out.format("b = %s\n", toBinaryString(b).substring(32 - 4, 32));
System.out.format("a ^ b = %s\n", toBinaryString(a ^ b).substring(32 - 4, 32));
System.out.format("\n");
}
System.out.format("properties\n");
System.out.format("\n");
{
System.out.format("(a ^ b) == (b ^ a)\n");
System.out.format("proof\n");
int a = 0 * 8 + 0 * 4 + 1 * 2 + 1 * 1;
int b = 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1;
System.out.format("a = %s\n", toBinaryString(a).substring(32 - 4, 32));
System.out.format("b = %s\n", toBinaryString(b).substring(32 - 4, 32));
System.out.format("a ^ b = %s\n", toBinaryString(a ^ b).substring(32 - 4, 32));
System.out.format("b ^ a = %s\n", toBinaryString(b ^ a).substring(32 - 4, 32));
System.out.format("\n");
assertEquals(a ^ b, b ^ a);
}
{
System.out.format("(a ^ 0) == a\n");
System.out.format("proof\n");
int a = 0 * 2 + 1 * 1;
System.out.format("a = %s\n", toBinaryString(a).substring(32 - 2, 32));
System.out.format("0 = %s\n", toBinaryString(0).substring(32 - 2, 32));
System.out.format("a ^ 0 = %s\n", toBinaryString(a ^ 0).substring(32 - 2, 32));
System.out.format("\n");
assertEquals(a ^ 0, a);
}
{
System.out.format("(a ^ a) == 0\n");
System.out.format("proof\n");
int a = 0 * 2 + 1 * 1;
System.out.format("a = %s\n", toBinaryString(a).substring(32 - 2, 32));
System.out.format("a ^ a = %s\n", toBinaryString(a ^ a).substring(32 - 2, 32));
System.out.format("\n");
assertEquals(a ^ a, 0);
}
{
System.out.format("((a ^ b) ^ c) == (a ^ (b ^ c))\n");
System.out.format("proof\n");
int a = 0 * 128 + 0 * 64 + 0 * 32 + 0 * 16 + 1 * 8 + 1 * 4 + 1 * 2 + 1 * 1;
int b = 0 * 128 + 0 * 64 + 1 * 32 + 1 * 16 + 0 * 8 + 0 * 4 + 1 * 2 + 1 * 1;
int c = 0 * 128 + 1 * 64 + 0 * 32 + 1 * 16 + 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1;
System.out.format("a = %s\n", toBinaryString(a).substring(32 - 8, 32));
System.out.format("b = %s\n", toBinaryString(b).substring(32 - 8, 32));
System.out.format("c = %s\n", toBinaryString(c).substring(32 - 8, 32));
System.out.format("a ^ b = %s\n", toBinaryString(a ^ b).substring(32 - 8, 32));
System.out.format("(a ^ b) ^ c = %s\n", toBinaryString((a ^ b) ^ c).substring(32 - 8, 32));
System.out.format("b ^ c = %s\n", toBinaryString(b ^ c).substring(32 - 8, 32));
System.out.format("a ^ (b ^ c) = %s\n", toBinaryString(a ^ (b ^ c)).substring(32 - 8, 32));
System.out.format("\n");
assertEquals((a ^ b) ^ c, a ^ (b ^ c));
}
}

private static final String toBinaryString(int a) {
StringBuilder binary = new StringBuilder();
for (int i = 31; i >= 0; i--) {
binary.append(((a >> i) & 1) == 0 ? "0" : "1");
}
return binary.toString();
}
}

problem TopCoder SRM579 Div2 Level3 MarblePositioning

how to solve In the contest, There is not plenty of time to solve.

source code

public class MarblePositioning {
private int[] radius;
private int n;

public double totalWidth(int[] radius) {
this.radius = radius;
this.n = radius.length;
return dfs(0, new int[n], new boolean[n], new double[n]);
}

private double dfs(int i, int[] index, boolean[] used, double[] center) {
if (i >= n) {
return center[n - 1];
}
double min = 1e100;
for (int j = 0; j < used.length; j++) {
if (used[j]) {
continue;
}
used[j] = true;
index[i] = j;
center[i] = getMaxCenter(i, index, center);
min = Math.min(min, dfs(i + 1, index, used, center));
used[j] = false;
}
return min;
}

private double getMaxCenter(int i, int[] index, double[] center) {
double max = 0;
for (int k = 0; k < i; k++) {
max = Math.max(max, center[k] + distance(radius[index[k]], radius[index[i]]));
}
return max;
}

private double distance(int a, int b) {
long c = a + b;
long d = a - b;
return Math.sqrt(c * c - d * d);
}
}

このページのトップヘ