Problem 42774. GJam March 2016 IOW: Clock Dance
This Challenge is derived from GJam March 2016 Annual I/O for Women Dance Around the Clock. 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].
Input: [D K N] , 4<=D<=1E8, 1<=K<=D, 1<=N<=1E8
Output: [KCW KCCW] , KCW is dancer to left of Kth dancer after N moves
Examples: [m] [v]
[8 3 1] creates v=[6 4] [8 4 2] creates v=[1 7] [6 6 1] creates v=[5 3]
Google Code Jam 2016 Open Qualifier: April 8, 2016
Contest Theory: The small case was D<10 and N<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 <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.
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers10
Suggested Problems
-
Back to basics 11 - Max Integer
782 Solvers
-
1105 Solvers
-
Find a subset that divides the vector into equal halves
387 Solvers
-
Find out missing number from a vector of 9 elements
295 Solvers
-
484 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!