With the Code Jam 2013 qualification starting soon, I decided to look at one of the past rounds. With 2011 I found one, in which I did not put too much time and effort in.
Candy Splitting. If you’re unfamiliar with the puzzle, read the problem first.
I managed to solve the the small input set, but couldn’t compute the large one in time. This usually indicates an issues with the chosen complexity to solve the puzzle, so let’s start evaluation where it went wrong.
My 2011 solution for the small
package com.unitedcoders.examples.codejam.q2011;
public static void main(String[] args) throws FileNotFoundException {
in = new Scanner(new FileReader(infile));
out = new PrintWriter(outfile);
int cases = in.nextInt();
int solution = -1;
for (int j = 1; j <= cases; j++) {
solution = -1;
int candyPieces = in.nextInt();
List candy = new ArrayList(candyPieces);
for (int i = 0; i < candyPieces; i++) {
candy.add(in.nextInt());
}
List<List> sets = powerSet(candy);
Iterator it = sets.iterator();
List staple1 = null;
while (it.hasNext()) {
List staple2 = new ArrayList();
staple1 = (List) it.next();
if (staple1.size() == candy.size()) {
continue;
}
for (int k : candy) {
staple2.add(k);
}
for (int k : staple1) {
if (staple2.contains(k)) {
staple2.remove((Object) k);
}
}
if (sumPatrick(staple1) == sumPatrick(staple2)) {
if (sumSeam(staple1) > solution) {
solution = sumSeam(staple1);
}
}
}
System.out.println("Case #" + j + ": " + ((solution == -1) ? "NO" : solution));
out.println("Case #" + j + ": " + ((solution == -1) ? "NO" : solution));
}
in.close();
out.close();
}
As you might have figured out, this is a correct implementation for the small dataset, but it does not scale.
What is wrong?
When we look at the code, we see that we’re creating a power set to evaluate all possible groups. This introduces a time complexity of O(n^2). And of course, with large dataset containing up to 1000 candy pieces, that’s nothing we can compute in time.
With a bit of thinking of course, you’ll find a way to solve this without “brute force”. There is a good explanation on how to solve this problem on the contest analysis page.
With that knowledge, we can try to solve the big dataset.
Candy Splitting – a solution that scales
public static void main(String[] args) throws FileNotFoundException {
in = new Scanner(new FileReader(infile));
out = new PrintWriter(outfile);
int cases = in.nextInt();
for (int j = 1; j <= cases; j++) {
int candyPieces = in.nextInt();
List candy = new ArrayList(candyPieces);
for (int i = 0; i < candyPieces; i++) {
candy.add(in.nextInt());
}
int xorResult = candy.get(0);
for (int k = 1; k < candy.size(); k++) {
xorResult = xorResult ^ candy.get(k);
}
// there is a solution if xor == 0
String result = "NO";
if (xorResult == 0) {
candy.remove(Collections.min(candy));
result = String.valueOf(sumList(candy));
}
System.out.println("Case #" + j + ": " + result);
out.println("Case #" + j + ": " + result);
}
in.close();
out.close();
}
public static int sumList(List candy) {
int sum = 0;
for (int i : candy) {
sum += i;
}
return sum;
}
Why does this work?
I just want to improve the description on the contest analysis page a bit.
If the bitwise or of all numbers is 0, and you take away any number, the xor of the remaining numbers will be the same number. Because when you add it back, it will be all zeros again.
Let’s visualize this with the second example, 3 5 6
011 011 101 011
101 101 110 110
110 --- --- ---
--- 110 011 101
000 we removed 110 011 101
--- --- ---
000 000 000
Therefore, we can give away the smallest candy and Patrick will see the piles as equal value.
The code can be found on github.
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014