Problem 1110. USC Fall 2012 ACM: Martian Pranks

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 to solve Question C, Martian Pranks, of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home\"><w:r><w:t>USC ACM Fall 2012 Contest</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>Rocks are moving between Rover pictures. This proves Life on Mars, but how Fast is that Life?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>All Rocks are bounded by a square with opposite corners (0,0) and (1,1). The camera only sees this 1x1 area. One Martian per Rock. Martians travel the minimum distance from the 1x1 edge to the initial rock position and from the final rock position to the edge to hide at velocity V. While moving a rock Marty's velocity reduces to V/2. An unmoved rock allows Marty to stay on the sideline. Note, the camera software does not track specific rocks, so an unmoved rock in Pict1 may be item 1 and this same rock may be item 4 in the second picture. Multiple rocks may occupy the same location in a picture.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Return the Minimum Martian Speed to transition from the initial Rock set to the Final rock set.</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: [Rock_locations_Pict1_Pict2,Time between pictures ]</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: [Minimum Martian Speed]</w:t></w:r><w:r><w:t>; to 2 decimal places;</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>Scoring: Cumulative Time ( msec )</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The full</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pranks.in.txt\"><w:r><w:t>USC data file</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</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: [0.3 0.6;0.4 0.5;0.5 0.5;0.95 0.2;0.6 0.5;0.9 0.4;0.5 0.5; 0.3 0.6], 3.0</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Essentially, 4 rocks in two pictures with a time between pictures of 3 seconds</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: 0.37</w:t></w:r><w:r><w:t> is quite obvious, not in the least</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This answer comes by moving [I1 F4; I2 F3; I3 F1; I4 F2] with rows two and three being of equal maximum effective distance of 1.1. My \"effective distance\" for I2 F3 is .4 + (.1)*2 + .5, where .1 is hypot(I2,F3) and multiply by 2 for speed reduction. This 1.1/3 rounds to 0.37.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pranks.zhencao.cpp.txt\"><w:r><w:t>The Winner's Pranks solution</w:t></w:r></w:hyperlink><w:r><w:t>. This solution is much tighter than my first method thus I am scoring by time. Hopefully someone can champion Matlab and produce a succinct and worthy solution. The winner solved this in 22 minutes and second place took a leisurely 65 minutes. Time Started when the page was opened.</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 to solve Question C, Martian Pranks, of the <a href="http://contest.usc.edu/index.php/Fall12/Home">USC ACM Fall 2012 Contest</a>.Rocks are moving between Rover pictures. This proves Life on Mars, but how Fast is that Life?All Rocks are bounded by a square with opposite corners (0,0) and (1,1). The camera only sees this 1x1 area. One Martian per Rock. Martians travel the minimum distance from the 1x1 edge to the initial rock position and from the final rock position to the edge to hide at velocity V. While moving a rock Marty's velocity reduces to V/2. An unmoved rock allows Marty to stay on the sideline. Note, the camera software does not track specific rocks, so an unmoved rock in Pict1 may be item 1 and this same rock may be item 4 in the second picture. Multiple rocks may occupy the same location in a picture.Return the Minimum Martian Speed to transition from the initial Rock set to the Final rock set.Input: [Rock_locations_Pict1_Pict2,Time between pictures ]Output: [Minimum Martian Speed]; to 2 decimal places;Scoring: Cumulative Time ( msec )The full <a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pranks.in.txt">USC data file</a>Example:Input: [0.3 0.6;0.4 0.5;0.5 0.5;0.95 0.2;0.6 0.5;0.9 0.4;0.5 0.5; 0.3 0.6], 3.0Essentially, 4 rocks in two pictures with a time between pictures of 3 secondsOutput: 0.37 is quite obvious, not in the leastThis answer comes by moving [I1 F4; I2 F3; I3 F1; I4 F2] with rows two and three being of equal maximum effective distance of 1.1. My "effective distance" for I2 F3 is .4 + (.1)*2 + .5, where .1 is hypot(I2,F3) and multiply by 2 for speed reduction. This 1.1/3 rounds to 0.37.<a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pranks.zhencao.cpp.txt">The Winner's Pranks solution</a>. This solution is much tighter than my first method thus I am scoring by time. Hopefully someone can champion Matlab and produce a succinct and worthy solution. The winner solved this in 22 minutes and second place took a leisurely 65 minutes. Time Started when the page was opened.

Solve

Solution Stats

9 Solutions
5 Solvers

Last Solution submitted on Jun 19, 2018

Last 200 Solutions

Problem Comments

Solution Comments

Solution 316699

1 Comment

1 Comment

Paul Berglund on 9 Sep 2013

This is (more or less) cribbed from the USC contest winner's solution.

Solution 175706

1 Comment

1 Comment

Richard Zapor on 11 Dec 2012

Very fast and very compact solution. Nice usage of complex to calculate distance between points and recursion.

Problem Recent Solvers5

Problem Tags

Problem 1110. USC Fall 2012 ACM: Martian Pranks

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author236

Problem Tags

Problem 1110. USC Fall 2012 ACM: Martian Pranks

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author236

Problem Tags

Players