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

19 Solutions
8 Solvers

Last Solution submitted on Jan 21, 2019

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.

Problem Recent Solvers8

Problem Tags

Community Treasure Hunt

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

Start Hunting!