CCC 2014 - Problem S1: Party Invite

The problem:

You are hosting a party and do not have room to invite all of your friends. You use the following unemotional mathematical method to determine which friends to invite.

Number your friends 1, 2, ... , K and place them in a list in this order. Then perform m rounds. In each round, use a number to determine which friends to remove from the ordered list.

The rounds will use numbers r₁, r₂, ... , r_m. In round i remove all the remaining people in positions that are multiples of r_i (that is, r_i, 2r_i, 3r_i, ...) The beginning of the list is position 1.

Output the numbers of the friends that remain after this removal process.

Input Specification
The first line of input contains the integer K (1 ≤ K ≤ 100). The second line of input contains the integer m (1 ≤ m ≤ 10), which is the number of rounds of removal. The next m lines each contain one integer. The ith of these lines (1 ≤ i ≤ m) contains r_i ( 2 ≤ r_i ≤ 100) indicating that every person at a position which is multiple of r_i should be removed.

Output Specification
The output is the integers assigned to friends who were not removed. One integer is printed per line in increasing sorted order.

Sample Input
10
2
2
3

Output for Sample Input
1
3
7
9

Explanation of Output for Sample Input
Initially, our list of invitees is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. There will be two rounds of removals. After the first round of removals, we remove the even positions (i.e., every second position), which causes our list of invitees to be 1, 3, 5, 7, 9. After the second round of removals, we remove every 3rd remaining invitee: thus, we keep 1 and 3, remove 5 and keep 7 and 9, which leaves us with an invitee list of 1, 3, 7, 9.

My solution (in Java):

import java.util.ArrayList;
import java.util.Scanner;
import java.io.File;

public class CCC_Problem_S1_Party_Invite {
    
    public static void main(String[] args) {
    
        try {
            Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\ccc_2014\\stage_1\\test_data\\s1\\s1.1.in"));
            
            // get all the input
            int k = Integer.parseInt(file.nextLine());
            int m = Integer.parseInt(file.nextLine());
            ArrayList<Integer> rs = new ArrayList<Integer>(); // contains all m number of rs
            for (int i = 0; i < m; i++) {
                rs.add(Integer.parseInt(file.nextLine()));
            }

            // populate the party by default with values 1 to k
            ArrayList<Integer> party = new ArrayList<Integer>();
            for (int i = 1; i <= k; i++) {
                party.add(i);
            }
            
            for (int r : rs) { // every round
            
                // each time you remove an element, the array shifts over,
                // so when removing the next element, you have to move over by the shift value
                int shift = 0; 
                
                for (int i = r - 1; (i-shift) < party.size(); i += r) { // for every rth element in the party
                    party.remove(i-shift); // remove that index (accounting for the shift too)
                    shift++; // shift increases because an item has been removed
                }
            }
            
            // print out the resultant party
            for (int i : party) {
                System.out.println(i);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

DOWNLOAD as .java

If you have trouble understanding the core algorithm which is this:

for (int r : rs) { // every round

    // each time you remove an element, the array shifts over,
    // so when removing the next element, you have to move over by the shift value
    int shift = 0; 
    
    for (int i = r - 1; (i-shift) < party.size(); i += r) { // for every rth element in the party
        party.remove(i-shift); // remove that index (accounting for the shift too)
        shift++; // shift increases because an item has been removed
    }
}

Then you can use the following algorithm instead. The above simply removes the people from the party. The below creates a new array to represent the people who were not removed from the party list.

for (int r : rs) { // every round

    // party discluding the people eliminated
    ArrayList<Integer> newParty = new ArrayList<Integer>();
            
    for (int i = 0; i < party.size(); i++) { // every person
        if ((i+1) % r != 0) { // not a multiple of r
            newParty.add(party.get(i)); // so not eliminated
        }
    }
    // copy the new party back into the old one
    party = new ArrayList<Integer>(); // reset party
    for (int i : newParty) {
        party.add(i);
    }
}

Test cases (as .in files):

Using their test cases:

10
2
2
3

And the output to that is:

1
3
7
9

And that is exactly the expected output

DOWNLOAD as .in

4
1
3

And the output to that is:

1
2
4

And that is exactly the expected output

DOWNLOAD as .in

100
5
10
3
2
5
2

And the output to that is:

1
7
17
24
34
41
51
57
67
74
84
91

And that is exactly the expected output

DOWNLOAD as .in

16
4
2
2
2
2

And the output to that is:

1

And that is exactly the expected output

DOWNLOAD as .in

20
10
20
19
18
17
16
15
14
13
12
3

And the output to that is:

1
2
4
5
7
8
10
11

And that is exactly the expected output

DOWNLOAD as .in