Monday, June 30, 2014

PeopleCircle

Problem:

TopCoder Problem Statement - PeopleCircle

Overview:

Determine the starting arrangement of a number of males and females sitting around a circle, given the number of females, and the value of i, where the ith person is removed each round.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 147
04: Division: 2
05: Level: 2
06: Points: 600
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1225
08:  */
09: 
10: public class PeopleCircle {
11: 
12:     private char[] circle;
13: 
14:     private int numAdded = 0;
15: 
16:     public String order(int numMales, int numFemales, int K) {
17: 
18:         // Creates a new array large enough to hold all males and females.
19:         circle = new char[numMales + numFemales];
20: 
21:         /*
22:           Initialize the circle to have numMales. This is the problem's
23:           ending condition.  We'll work backwards from here.
24:          */
25:         for (int i = 0; i < numMales; i++) {
26:             circle[i] = 'M';
27:         }
28: 
29:         /*
30:        Set the initial positions to be just after the number of males.  When
31:         problem description has finished, the circle will have all males,
32:         the last female will have just been removed.
33:         */
34:         int position = numMales;
35:         numAdded = 0;
36: 
37:         // Check for the case where there were no females to start with.
38:         if (numFemales == 0) {
39:             return new String(circle);
40:         }
41: 
42:         /*
43:         Count back and insert females until all have been added.
44:          */
45:         while (numAdded < numFemales) {
46:             insertFemale(position);
47:             numAdded++;
48:             position = position - K + 1;
49: 
50:             // Loop around to the back of the array
51:             while (position < 0) {
52:                 position += numMales + numAdded;
53:             }
54:         }
55: 
56:         /*
57:         Construct the return string by taking the elements to the right
58:         of the current positions, and then adding the elements from the
59:         beginning of the circle up to the current position.
60:          */
61:         String s1 = new String(circle).substring(position);
62:         String s2 = new String(circle).substring(0, position);
63:         return s1 + s2;
64:     }
65: 
66:     /*
67:     Inserts a female ('F') at the given positions.
68:     Shifts everything to the right of pos one spot further to the right
69:     creating a space to insert the new character.
70:      */
71:     private void insertFemale(int pos) {
72: 
73:         /*
74:         Works backward from the end of the array shifting everything
75:         over to the right.
76:          */
77:         for (int i = circle.length - 1; i > pos; i--) {
78:             circle[i] = circle[i - 1];
79:         }
80: 
81:         circle[pos] = 'F';
82:     }
83: }
Notes:

This problem requires you to start from the end state and work backwards to reconstruct what the beginning must have looked like. We know from the problem that it started as some point and removed the Kth person. This repeated numFemale times until all the females are gone. So the first hint is that on every move a female is removed, the number of males remains constant.

Lines 19 through 27 create an array large enough to hold all participants, and then inserts the number of males starting at the head of the array.

Now, we reverse the process. Instead of counting ahead and removing a female, we count back and insert a female. Line 48 handles counting back, and the insertFemale() method takes care of inserting the 'F' at the given position and shifting everything beyond that point one spot to the right.

We must be careful because the size of the circle array is not the number of people currently in the circle at that point. Lines 51-53 detect when we've gone in front of the beginning of the array, and set us back to the end based on the number of people.

Finally, we won't necessary end up at the start of the array. So, to construct the return string, we need to concatenate everything to the right of our current position, with everything from the beginning of the the array up to our current position.

|--A-------------B----------|
^

For some clarity, if our final position is at the ^, then the return string would be B + A.

No comments:

Post a Comment