CareerCup

This is my interpretation of the problem. Suppose pizza has 1 2 3 4 5 6 where n=2. If you eat piece 6, then you have to immediately discard its 2 neighbors and so the pizza now becomes 2 3 4, so you would pick piece 4 in the 2nd iteration, resulting in 10 total. But if you were to eat piece 5 originally, you would end up with 1 2 3, at which point you would pick 3, resulting in 8 total.

I re-read the problem statement again. It says "every time we eat and discard there are new neighbors being formed per piece. "So I am no sure if my interpretation in previous comment is correct, because not all pieces will have new neighbors each time we eat according to my understanding.

@Sunny, your understanding is correct and the example you gave is absolutely fine.

In this case, the time complexity is almost (n!) which is too large. For example, when n is greater than 12, your solution cannot give the answer within a few seconds. If n is 100, we can never get the result. I hope someone can come up with a better solution.

@Eugene.Yarovoi

Please ask me where you are not clear. I am also taking a stab at it using DP.

Well, DP is not needed. A killer solution with greedy-like strategy would work. I am posting my solution as a separate another comment.

The example 9 10 9 7 1 1 is not solvable by a greedy algorithm.
Greedy algorithm will choose 10, then 7, then 1, which adds up to 18. However, a better choice is to choose 9, 9, and 1, which adds up to 19.

The example is good but if my interpretation of this "3n pieces" problem is correct, then with the greedy approach you would first pick 10, which makes the 2 adjacent 9s disappear. The array is now 7 11, so you would pick 7 and now the array is empty. So total is 17.

If you first pick the 9 in front, the array will now be 9 7 1, so you would again pick 9, so the total in this case is 18.

I re-read the problem statement, and you're right. I missed that detail.
I'm glad my example still holds though!

After poking around at this for a while I'm convinced the only way to do it is a brute force search, but there might be a sneaky DP solution I'm missing.

Here's a counter-example:
0 9 8 0 0 5 7 6 0 0 4 0

The greedy approach will pick 9 7 4 0 = 20 whereas the optimal answer should be 9 6 5 4 = 24

@Sunny.

Good one.Killer solution is not working lol. DP is the way to go. Thanks for the counter example.

I wonder if DP can get the job done. I tried a recursive brute-force with memoization of subproblems. The numbers of subproblems are varying at each level...not sure how that can be captured using DP. The total number of subproblems that need be searched for an input of size 3n using brute-force is n!*3^n .However using memoization, that number can be reduced as the following examples illustrate.

Input(Size 36):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0
Output:
Time taken in secs=284
Maxsize = 72
No. of subproblems of size(3): 936
No. of subproblems of size(6): 18018
No. of subproblems of size(9): 97240
No. of subproblems of size(12): 226746
No. of subproblems of size(15): 279072
No. of subproblems of size(18): 201894
No. of subproblems of size(21): 91080
No. of subproblems of size(24): 26325
No. of subproblems of size(27): 4872
No. of subproblems of size(30): 558
No. of subproblems of size(33): 36
No. of subproblems of size(36): 1

Input(Size 39):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8
Output:
Time taken in secs=1149
Maxsize = 81
No. of subproblems of size(3): 1183
No. of subproblems of size(6): 28392
No. of subproblems of size(9): 189618
No. of subproblems of size(12): 545870
No. of subproblems of size(15): 831402
No. of subproblems of size(18): 749892
No. of subproblems of size(21): 427570
No. of subproblems of size(24): 159705
No. of subproblems of size(27): 39585
No. of subproblems of size(30): 6448
No. of subproblems of size(33): 663
No. of subproblems of size(36): 39
No. of subproblems of size(39): 1

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;

/**
 * @author Murali Mohan
 *
 */
class PizzaPiece {
	int size, index, leftNeighbor, rightNeighbor;
	boolean isTaken = false;
	PizzaPiece(int size, int index) {
		this.size = size;
		this.index = index;
	}
}

public class PizzaPiecesDP {

	static List<PizzaPiece> pieces 		= new ArrayList<PizzaPiece>();
	static List<PizzaPiece> selectedPieces = new ArrayList<PizzaPiece>();
	static Map<String, Integer>[] pieceSubsets;
	
	public static String getKey(int chosenPizzaIndex, List<PizzaPiece> pizzaPieces) {

		Collections.sort(pizzaPieces, new Comparator<PizzaPiece>() {
			 public int compare(PizzaPiece piece1, PizzaPiece piece2) {
			       return piece1.index - piece2.index;
			    }
		});
		
		StringBuffer key = new StringBuffer();
		for (int i = 0; i < pizzaPieces.size(); i++) {
			if (!pizzaPieces.get(i).isTaken) {
				key.append(":" + pizzaPieces.get(i).index);
			}
		}
		return key.toString();
	}
	
	public static int computeMaxSubset(List<PizzaPiece> pizzaPieces, int startIndex, int remSize) {
	
		//System.out.println("Begin: startIndex=" + startIndex + " remSize=" + remSize);
		int max = 0, maxIndex = -1;
		String key = "";
		Integer remOptSize;
		
		if (remSize == 3) {
			
			key = getKey(startIndex, pizzaPieces);
			remOptSize = pieceSubsets[0].get(key);
			if (remOptSize == null) {

				if (!pizzaPieces.get(startIndex).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).isTaken) {					
					max = Math.max(pizzaPieces.get(startIndex).size, Math.max(pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).size, pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).size));
					pieceSubsets[0].put(key, max);
				} else {
					System.out.println("WARN: Something's wrong!");
				}
			} else {
				max = remOptSize;
			}
		} else {

			int i = startIndex;
			for (int j = 0; j < remSize; j++) {

				key = getKey(i, pizzaPieces);
				remOptSize = pieceSubsets[((remSize - 3) / 3)].get(key);
				
				if (remOptSize != null) {
					max = remOptSize;
				} else {
					int previous = pizzaPieces.get(i).leftNeighbor;
					int next = pizzaPieces.get(i).rightNeighbor;
					
					pizzaPieces.get(previous).isTaken = true;
					pizzaPieces.get(i).isTaken = true;
					pizzaPieces.get(next).isTaken = true;
					
					PizzaPiece secondLeft = pizzaPieces.get(pizzaPieces.get(previous).leftNeighbor);
					PizzaPiece secondRight = pizzaPieces.get(pizzaPieces.get(next).rightNeighbor);
					secondLeft.rightNeighbor = secondRight.index;
					secondRight.leftNeighbor = secondLeft.index;
					
					remOptSize = computeMaxSubset(pizzaPieces, secondRight.index, remSize - 3);
					
					if (max < remOptSize + pizzaPieces.get(i).size) {
						max = remOptSize + pizzaPieces.get(i).size;
						maxIndex = i;
					}
					
					pizzaPieces.get(previous).isTaken = false;
					pizzaPieces.get(i).isTaken = false;
					pizzaPieces.get(next).isTaken = false;
					
					secondLeft.rightNeighbor = previous;
					secondRight.leftNeighbor = next;
				}
				
				i = pizzaPieces.get(i).rightNeighbor;
			}
			pieceSubsets[((remSize - 3) / 3)].put(key, max);
		}
		//System.out.println("End: startIndex=" + startIndex + " remSize=" + remSize + " max=" + max + " maxIndex = " + maxIndex + " size = " + ((maxIndex == -1) ? 3 : pizzaPieces.get(maxIndex).size) + " key = " + key + " keysize = " + key.split(":").length);		
		return max;
	}
	
	public static void main(String[] args) {
				
		System.out.println("Input 3n pizza sizes separated by space. Enter twice to start execution");
		Scanner scanner 	= new Scanner(System.in);
		Pattern delimiters 	= Pattern.compile(System.getProperty("line.separator")+"|\\s");
		scanner.useDelimiter(delimiters);

		int piecesNumber = 0;
		while (scanner.hasNextInt()) {
			PizzaPiece piece = new PizzaPiece(scanner.nextInt(), piecesNumber++);
			piece.rightNeighbor = 0;
			if (piecesNumber > 1) {
				piece.leftNeighbor =  (piecesNumber - 2);
				pieces.get(piecesNumber - 2).rightNeighbor = piecesNumber - 1; 
			}			 
			pieces.add(piece);
		} ;
		
		pieces.get(0).leftNeighbor = pieces.size() - 1; 
		if (piecesNumber % 3 != 0) {
			throw new RuntimeException("# of pizza pieces is not a multiple of 3");
		}
		
		pieceSubsets = new HashMap[piecesNumber / 3];
		for (int i = 0; i < piecesNumber / 3; i++) {
			pieceSubsets[i] = new HashMap<String, Integer>();
		}
		
		long startTime = System.currentTimeMillis();
		int maxSize = computeMaxSubset(pieces, 0, pieces.size());
		long elapsedTime = (System.currentTimeMillis() - startTime)/1000;
		System.out.println("Time taken in secs=" + elapsedTime);
		
		System.out.println("Maxsize = " + maxSize);
		
		for (int i = 0; i < pieceSubsets.length; i++) {
			System.out.println("No. of subproblems of size(" + ((i+1) * 3 ) + "): " + pieceSubsets[i].size() /*+ ", "+ pieceSubsets[i].toString() */);
		}
	}	
}

Does anyone have any involved ideas using Branch and Bound or so?

Try {1,2,3,4,5,6} and {1,2,3,4,5,6,7,8,9}. The code would return a volume that's larger than the real answer. The reason is that the DP solution tries to add every other element, so it's eliminating 2 (not 3) slices each time.