Problem 42774. GJam March 2016 IOW: Clock Dance

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/8274486/dashboard#s=p1\"><w:r><w:t>GJam March 2016 Annual I/O for Women Dance Around the Clock</w:t></w:r></w:hyperlink><w:r><w:t>. This is a mix of the small and large data sets.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The GJam story goes that D even dancers are arranged clockwise 1:D. Who is adjacent to dancer K after N pair swaps. The odd move swaps positions 1/2,3/4,..D-1/D. The even move swaps positions D/1, 2/3,...D-2/D-1. D=8 [1:8] becomes [2 1 4 3 6 5 8 7] after the first swap. After second swap we see [7 4 1 6 3 8 5 2].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t></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> [D K N] , 4&lt;=D&lt;=1E8, 1&lt;=K&lt;=D, 1&lt;=N&lt;=1E8</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> [KCW KCCW] , KCW is dancer to left of Kth dancer after N moves</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:r><w:t> [m] [v]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[8 3 1] creates v=[6 4]\n[8 4 2] creates v=[1 7]\n[6 6 1] creates v=[5 3]]]></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></w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam\"><w:r><w:rPr><w:b/></w:rPr><w:t>Google Code Jam 2016 Open Qualifier: April 8, 2016</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>Contest Theory:</w:t></w:r><w:r><w:t> The small case was D&lt;10 and N&lt;10. This could be done brute force in the 5 minutes of entry submission allowed. However, this is clearly a case of modulo math so might as well solve the unbounded case of D/N &lt;1E8. The number being assigned as 1:D leads to confusion as mod maps to 0:D-1. Suggest offset the K dancer number by 1 for processing and then correct for the final answer. Mod is fun as mod(-1,8) yields a useful 7. Quick observation is for offsetted K vector [0:D-1] the Evens move CW and the Odds move CCW. One method used 5 mod calls to solve.</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/8274486/dashboard#s=p1">GJam March 2016 Annual I/O for Women Dance Around the Clock</a>. This is a mix of the small and large data sets.The GJam story goes that D even dancers are arranged clockwise 1:D. Who is adjacent to dancer K after N pair swaps. The odd move swaps positions 1/2,3/4,..D-1/D. The even move swaps positions D/1, 2/3,...D-2/D-1. D=8 [1:8] becomes [2 1 4 3 6 5 8 7] after the first swap. After second swap we see [7 4 1 6 3 8 5 2].<img src = "http://code.google.com/codejam/contest/images/?image=dance_around_the_clock.png&p=5733344260128768&c=8274486">Input: [D K N] , 4&lt;=D&lt;=1E8, 1&lt;=K&lt;=D, 1&lt;=N&lt;=1E8Output: [KCW KCCW] , KCW is dancer to left of Kth dancer after N movesExamples: [m] [v]<pre class="language-matlab">[8 3 1] creates v=[6 4]
[8 4 2] creates v=[1 7]
[6 6 1] creates v=[5 3]
</pre><a href = "http://code.google.com/codejam">Google Code Jam 2016 Open Qualifier: April 8, 2016</a>Contest Theory: The small case was D&lt;10 and N&lt;10. This could be done brute force in the 5 minutes of entry submission allowed. However, this is clearly a case of modulo math so might as well solve the unbounded case of D/N &lt;1E8. The number being assigned as 1:D leads to confusion as mod maps to 0:D-1. Suggest offset the K dancer number by 1 for processing and then correct for the final answer. Mod is fun as mod(-1,8) yields a useful 7. Quick observation is for offsetted K vector [0:D-1] the Evens move CW and the Odds move CCW. One method used 5 mod calls to solve.

Solve

Solution Stats

19 Solutions
17 Solvers

Last Solution submitted on Jun 12, 2020

Last 200 Solutions

Problem Recent Solvers17

Problem Tags

gjam mod

Problem 42774. GJam March 2016 IOW: Clock Dance

Solution Stats

Last 200 Solutions

Problem Recent Solvers17

Suggested Problems

More from this Author236

Problem Tags

Problem 42774. GJam March 2016 IOW: Clock Dance

Solution Stats

Last 200 Solutions

Problem Recent Solvers17

Suggested Problems

More from this Author236

Problem Tags

Players