Problem 2291. GJam 2014 Qualifier: Deceitful War (Small)

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2974486/dashboard#s=p3\"><w:r><w:t>GJam 2014 Qualifier Deceitful War</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>My condensed summary of the problem statement.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two players, A and B, they are each given N masses. All masses are unique. Player A plays first on each comparison and states a Mass. Player B then plays a Mass. The player with the higher mass wins a point after they are compared on a scale. These masses then disappear. This repeats for all N masses. There are no constraints on the order of pieces played.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Unsurprisingly when A truthfully states masses player B consistently wins.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Player A, discouraged, decides to cheat. After the masses are provided player A asks B get A a drink and while B is away A looks at B's masses. Player A now plays pieces but does not necessarily honestly state the mass values. All scale comparisons must be valid based on B's strategy and A's stated mass. Player A now achieves more wins.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Part one is determine the best possible score for A when playing deceitfully.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Part two is determine the best possible score if player A did not look and is honest.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[A: 0.5 0.1 0.9 B 0.6 0.4 0.3 Deceitful Wins 2, Optimal Honest 1\n\nA 0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899\nB 0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458\nDeceitful A Wins 8\nOptimal Honest A Wins 4]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> A,B vectors of length N (Small has N&lt;=10, Large(future challenge N&lt;=1000)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> Deceitful Wins, Optimal Honest Wins</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Note:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In the contest period there were 30 Matlab solutions, of which I was not one as I glitched on the easy Deceitful algorithm thinking my Honest algorithm was in error.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.go-hero.net/jam/14/solutions/0/4/MATLAB\"><w:r><w:t>GJam Deceitful Solutions</w:t></w:r></w:hyperlink><w:r><w:t>. My post contest full GJam is in the test suite. About 11000 out of 28000 entrants solved this puzzle.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2974486/dashboard#s=p3">GJam 2014 Qualifier Deceitful War</a>.My condensed summary of the problem statement.Given two players, A and B, they are each given N masses. All masses are unique. Player A plays first on each comparison and states a Mass. Player B then plays a Mass. The player with the higher mass wins a point after they are compared on a scale. These masses then disappear. This repeats for all N masses. There are no constraints on the order of pieces played.Unsurprisingly when A truthfully states masses player B consistently wins.Player A, discouraged, decides to cheat. After the masses are provided player A asks B get A a drink and while B is away A looks at B's masses. Player A now plays pieces but does not necessarily honestly state the mass values. All scale comparisons must be valid based on B's strategy and A's stated mass. Player A now achieves more wins.Part one is determine the best possible score for A when playing deceitfully.Part two is determine the best possible score if player A did not look and is honest.Examples:<pre class="language-matlab">A: 0.5 0.1 0.9 B 0.6 0.4 0.3 Deceitful Wins 2, Optimal Honest 1
</pre><pre class="language-matlab">A 0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
B 0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458
Deceitful A Wins 8
Optimal Honest A Wins 4
</pre>Input: A,B vectors of length N (Small has N&lt;=10, Large(future challenge N&lt;=1000)Output: Deceitful Wins, Optimal Honest WinsNote:In the contest period there were 30 Matlab solutions, of which I was not one as I glitched on the easy Deceitful algorithm thinking my Honest algorithm was in error. <a href = "http://www.go-hero.net/jam/14/solutions/0/4/MATLAB">GJam Deceitful Solutions</a>. My post contest full GJam is in the test suite. About 11000 out of 28000 entrants solved this puzzle.

This Challenge is derived from <http://code.google.com/codejam/contest/2974486/dashboard#s=p3 GJam 2014 Qualifier Deceitful War>.

My condensed summary of the problem statement.

Given two players, A and B, they are each given N masses. All masses are unique. Player A plays first on each comparison and states a Mass. Player B then plays a Mass. The player with the higher mass wins a point after they are compared on a scale. These masses then disappear. This repeats for all N masses. There are no constraints on the order of pieces played.

Unsurprisingly when A truthfully states masses player B consistently wins.

Player A, discouraged, decides to cheat. After the masses are provided player A asks B get A a drink and while B is away A looks at B's masses. Player A now plays pieces but does not necessarily honestly state the mass values. All scale comparisons must be valid based on B's strategy and A's stated mass. Player A now achieves more wins.

Part one is determine the best possible score for A when playing deceitfully.

Part two is determine the best possible score if player A did not look and is honest.

*Examples:*

A: 0.5 0.1 0.9  B 0.6 0.4 0.3  Deceitful Wins 2, Optimal Honest 1
  
  A 0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
  B 0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458
  Deceitful A Wins 8
  Optimal Honest A Wins 4

*Input:* A,B vectors of length N (Small has N<=10, Large(future challenge N<=1000)

*Output:* Deceitful Wins, Optimal Honest Wins

*Note:*

In the contest period there were 30 Matlab solutions, of which I was not one as I glitched on the easy Deceitful algorithm thinking my Honest algorithm was in error. <http://www.go-hero.net/jam/14/solutions/0/4/MATLAB GJam Deceitful Solutions>. My post contest full GJam is in the test suite. About 11000 out of 28000 entrants solved this puzzle.

Solve

Solution Stats

20 Solutions
8 Solvers

Last Solution submitted on Jul 08, 2021

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Michael C. on 2 May 2014

I actually had one of the 30 matlab solutions you mentioned. Did you have much luck in round1A? Sadly, I did not.

Solution Comments

Show comments

Problem Recent Solvers8

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 2291. GJam 2014 Qualifier: Deceitful War (Small)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers8

Suggested Problems

More from this Author294

Problem Tags

Community Treasure Hunt

Problem 2291. GJam 2014 Qualifier: Deceitful War (Small)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers8

Suggested Problems

More from this Author294

Problem Tags

Community Treasure Hunt

Players