Cody

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

94.44% Correct | 5.56% Incorrect
Last solution submitted on Nov 10, 2018