PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Deceitful War Solution – Google Code Jam 2014

(3 votes, average: 2.00 out of 5)

April 13, 2014 by puzzler 3 Comments

4th problem in google code jam qualification round 2014

Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets Nidentical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War.


Here is how War works:

  1. Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player’s blocks.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken the mass of the block she chose.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire.

Naomi has realized three things about War. First, she has realized that she loses a lot. Second, she has realized that there is a unique strategy that Ken can follow to maximize his points without assuming anything about Naomi’s strategy, and that Ken always uses it. Third, she has realized that she hates to lose. Naomi has decided that instead of playing War, she will play a game she calls Deceitful War. The great thing about Deceitful War is that Ken will think they’re playing War!

Here is how Deceitful War works, with differences between Deceitful War and War in bold:

  1. Each player weighs each of his or her own blocks. Naomi also weighs Ken’s blocks while he isn’t looking, so Naomi knows the weights of all blocks and Ken only knows the weights of his own blocks.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken a number, ToldNaomi, between 0.0kg and 1.0kg exclusive. Ken, who thinks they’re playing War, thinks the number Naomi just told him is ChosenNaomi.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire.

Naomi doesn’t want Ken to know that she isn’t playing War; so when she is choosing which block to play, and what mass to tell Ken, she must make sure that the balance scale won’t reveal that ChosenNaomi ≠ ToldNaomi. In other words, she must make decisions so that:

  • ChosenNaomi > ChosenKen if, and only if, ToldNaomi > ChosenKen, and
  • ToldNaomi is not equal to the mass of any of Ken’s blocks, because he knows that isn’t possible.

It might seem like Naomi won’t win any extra points by being deceitful, because Ken might discover that she wasn’t playing War; but Naomi knows Ken thinks both players are playing War, and she knows what he knows, and she knows Ken will always follow his unique optimal strategy for War, so she can always predict what he will play.

You’ll be given the masses of the blocks Naomi and Ken started with. Naomi will play Deceitful War optimally to gain the maximum number of points. Ken will play War optimally to gain the maximum number of points assuming that both players are playing War. What will Naomi’s score be? What would it have been if she had played War optimally instead?

Examples

If each player has a single block left, where Naomi has 0.5kg and Ken has 0.6kg, then Ken is guaranteed to score the point. Naomi can’t say her number is ≥ 0.6kg, or Ken will know she isn’t playing War when the balance scale shows his block was heavier.

If each player has two blocks left, where Naomi has [0.7kg, 0.2kg] and Ken has [0.8kg, 0.3kg], then Naomi could choose her 0.2kg block, and deceive Ken by telling him that she chose a block that was 0.6kg. Ken assumes Naomi is telling the truth (as in how the War game works) and will play his 0.8kg block to score a point. Ken was just deceived, but he will never realize it because the balance scale shows that his 0.8kg block is, like he expected, heavier than the block Naomi played. Now Naomi can play her 0.7kg block, tell Ken it is 0.7kg, and score a point. If Naomi had played War instead of Deceitful War, then Ken would have scored two points and Naomi would have scored zero.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of blocks each player has. Next follows a line containing N space-separated real numbers: the masses of Naomi’s blocks, in kg. Finally there will be a line containing N space-separated real numbers: the masses of Ken’s blocks, in kg.

Each of the masses given to Ken and Naomi will be represented as a 0, followed by a decimal point, followed by 1-5 digits. Even though all the numbers in the input have 1-5 digits after the decimal point, Ken and Naomi don’t know that; so Naomi can still tell Ken that she played a block with mass 0.5000001kg, and Ken has no reason not to believe her.

Output

For each test case, output one line containing “Case #x: y z“, where x is the test case number (starting from 1), y is the number of points Naomi will score if she plays Deceitful War optimally, and z is the number of points Naomi will score if she plays War optimally.

Limits

1 ≤ T ≤ 50.
All the masses given to Ken and Naomi are distinct, and between 0.0 and 1.0 exclusive.

Small dataset

1 ≤ N ≤ 10.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input
4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458

Output
Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4

Solution:

Get Number of wins if played Deceitful war

Lets take the last sample input
Naomi’s weights: 0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
Ken’s weights: 0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458

sort them first
Naomi : 0.186 0.300 0.389 0.557 0.832 0.899 0.907 0.959 0.992
Ken : 0.215 0.271 0.341 0.458 0.520 0.521 0.700 0.728 0.916

At any point of time, either naomi’s block will be lighter than ken’s lightest block or heavier than ken’s lightest block

Case 1: Naomi’s lightest block is lighter than Ken’s lightest block

In this case naomi is bound to loose as all of ken’s blocks are higher than that block. So in that case she can loose it against ken’s heaviest block by telling the weight just smaller than Ken’s heaviest block OR higher than the second heaviest block.

in above example 0.186 is smaller than any of Ken’s blocks, thus Naomi will put 0.186 forward and say 0.7280001.
Ken will put 0.916 block and will win, he will not have any doubts over Naomi in this case.

Case 2: Naomi’s lightest block is heavier than Ken’s lightest block

In this case naomi can say the weight higher than the ken’s heaviest weight. ken will think that he is any way going to loose so he will compare with his lowest weight(he will save heavier weight for later)
thus naomi can easily win in this case.

ex: after Naomi looses 0.186
Naomi: 0.300 0.389 0.557 0.832 0.899 0.907 0.959 0.992
Ken : 0.215 0.271 0.341 0.458 0.520 0.521 0.700 0.728

In this case N will say 0.7280002 and put 0.300 block forward, Ken will think that he is going to loose any way so he will put 0.215 forward and he will loose. He will not have any doubt as 0.300 and 0.7280002 are both greater than 0.215.

Get number of wins if played Optimally
In this case whatever number Naomi puts forward, Ken will put block with next higher weight.
This can be solved by sorting their weights and put naomi’s weights serially, ken will also put his weight serially.

Here is the java code for Deceitful War based on above explanation

package codejam2014;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;

public class DeceitfulWar {

	public int getDeceitfulWarScore(ArrayList<Float> naomiBlocks, ArrayList<Float> kenBlocks){
		int numberOfBlocks = naomiBlocks.size();
		int kenEnd = numberOfBlocks -1;//as both has same number of blocks
		int kenPointer = 0;
		int naomiWin =0;
		
		for(int i =0; i < naomiBlocks.size(); i++){
			if(kenBlocks.get(kenPointer).compareTo(naomiBlocks.get(i)) > 0){
				kenEnd--;//Naomi bound to loose this, she will let it go with biggest of ken
				continue;
			}
			naomiWin ++;//Can win by telling a weight higher than max of ken's weight
			kenPointer++;//ken will play its lowest at this point
		}
		return naomiWin;
	}
	
	public int getWarScore(ArrayList<Float> naomiBlocks, ArrayList<Float> kenBlocks){
		int naomiWin =0;
		int kenPointer = 0;
		
		for(int i =0; i < naomiBlocks.size(); i++){
			while(kenBlocks.get(kenPointer).compareTo(naomiBlocks.get(i)) < 0){
				naomiWin++;
				kenPointer++;
				if(kenPointer >= kenBlocks.size()){
					break;
				}
			}
			kenPointer++;
			if(kenPointer >= kenBlocks.size()){
				break;
			}
		}
		return naomiWin;
	}
	
	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("small.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;
	
			File file = new File("small.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				bufReader.readLine();//ignore number of blocks input
				ArrayList<Float> naomiBlocks = getFloatList(bufReader.readLine());
				ArrayList<Float> kenBlocks = getFloatList(bufReader.readLine());
				Collections.sort(naomiBlocks);
				Collections.sort(kenBlocks);
				int deceitfulScore =  new DeceitfulWar().getDeceitfulWarScore(naomiBlocks, kenBlocks);
				String output = new DeceitfulWar().getWarScore(naomiBlocks, kenBlocks)+"";
				writer.write("Case #" + count + ": " +deceitfulScore + " "+ output+"\n");
				System.out.println("Case #" + count + ": " + deceitfulScore +" " + output);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static ArrayList<Float> getFloatList(String s) {
		ArrayList<Float> intList = new ArrayList<Float>();
		String[] strArr = s.split(" ");
		for (String str : strArr) {
			intList.add(Float.parseFloat(str.trim()));
		}
		return intList;
	}
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
Charging Chaos Solution – Google CodeJam

Checkout more Google Code jam Tags: Difficult, Solved Puzzles

Comments

  1. valaki says

    December 27, 2014 at 6:38 am

    If the weights of both player are sorted in one series, getting labelled with Ns and Ks depending whether the weight value belongs to Naomi or Ken, you only have to count from 0 up and down:
    – in War mode, counting in increasing order, add (-1) for Ns and add (+1) for Ks and track the maximum number reached during the calculation (points for Naomi)
    – in Deceitful mode, using the same rule in reversed (decreasing) order, the maximum number gives the points remain by Ken if Naomi plays optimally
    ps. you should use ‘static’ for the calculator functions, they use only arguments and not members — thus no explicit instantiation of your class is needed

    Reply
  2. I<3java says

    April 20, 2014 at 3:46 pm

    Hi, this was a very smart move on Naomi’s part and ‘deceitful war’ is a very intriguing game. The situation is very complicated…..must say your explanation is exemplary, and the java code really helped a great deal.

    Reply
    • puzzlersworld says

      April 20, 2014 at 7:17 pm

      Thanks, Glad you liked it.

      Reply

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Minesweeper Master Solution – Google Code jam 2014
  • Cookie Clicker Alpha Solution – Google Code Jam 2014
  • Charging Chaos Solution – Google CodeJam
  • Magic Trick Solution – Google Code Jam 2014
  • Deceitful War Solution – Google Code Jam 2014
  • Full Binary Tree Solution – Google Code Jam

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▼
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous