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

89.47% Correct | 10.53% Incorrect
Last Solution submitted on Jun 12, 2020

Solution Comments

Show comments

Problem Recent Solvers10

Suggested Problems

More from this Author294

Problem Tags

Community Treasure Hunt

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

Start Hunting!