JOIN Match Editorial
SRM 384
Wednesday, December 19, 2007

## Match summary

The last Single Round Match before Christmas brought together more than 850 competitors. As a present for them we prepared a problem set in which they could play a lot of games. Exactly 3 of 5 problems were mathematical games.

SRM 384 won goes to Eryx for his fantastic performance. He was able to solve complete set in 20 minutes, much faster than anyone else, with the fastest submission on Medium and the second fastest on Hard. The 2nd place goes to Petr who overtook marek.cygan in the challenge phase. So marek.cygan had to be satisfied with 3rd place.

In Division 2 more people solved Medium than Easy which was harder than usual. Only few coders were able to solve all 3 problems. The first place goes to leohoyee who was closely followed by espr1t and acsaga.

# The Problems

Prank  Used as: Division Two - Level One:
 Value 250 Submission Rate 366 / 464 (78.88%) Success Rate 294 / 366 (80.33%) High Score Asocasno for 242.97 points (4 mins 51 secs) Average Score 164.77 (for 294 correct submissions)

This problem was not as easy as usual. Coders needed to be careful about overflow and time limit, but fortunately examples often help them to find these bugs. It is easy to test if a particular previous weight is good. We just need to square its value and add apparentGain. If the result is also square, then square root of this result is possible Jane's real weight. And while difference between the squares of two consecutive integers is (x+1)^2 - x^2 = 2*x + 1, it is enough to try first 50,000 previous weights, because apparentGain (=2*x+1) was limited to 100,000.

C++ solution follows:

```#define ll long long
class Prank {
public:
vector <int> realWeight(int apparentGain) {
vector<int> ret;
for (ll i=1;i<50000;i++) {
ll sq = i*i+apparentGain;
ll candidate = (ll)round(sqrt(sq));
if (candidate*candidate == sq) ret.push_back(candidate);
}
return ret;
}
};
```

Library  Used as: Division Two - Level Two:
 Value 500 Submission Rate 348 / 464 (75.00%) Success Rate 310 / 348 (89.08%) High Score numenor for 485.74 points (4 mins 53 secs) Average Score 372.69 (for 310 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 386 / 390 (98.97%) Success Rate 368 / 386 (95.34%) High Score Im2Good for 248.40 points (2 mins 17 secs) Average Score 222.00 (for 368 correct submissions)

The problem was pretty straightforward and it caused quite high success rate in both divisions. It was sufficient to check for each record if Mr. Agent has rights to access its room and is a member of its user group. Except that you also needed to ensure to count every document only once. It can be solved by iterating over input arrays, because of the small constraints. But probably the fastest and easiest way for coding, checking and ignoring duplicates is using sets.

mystic_tc's Java code follows:

```public class Library {
public int documentAccess(String[] records, String[] documentRights, String[] roomRights) {
Set<String> groups = new HashSet<String>();
Set<String> rooms = new HashSet<String>();
Set<String> docs = new HashSet<String>();
for (String group : documentRights) groups.add(group);
for (String room : roomRights) rooms.add(room);
for (String s : records)
if (groups.contains(s.split(" "))
&& rooms.contains(s.split(" ")))
return docs.size();
}
}

```

PowerGame  Used as: Division Two - Level Three:
 Value 1000 Submission Rate 28 / 464 (6.03%) Success Rate 7 / 28 (25.00%) High Score leohoyee for 628.66 points (25 mins 13 secs) Average Score 527.59 (for 7 correct submissions)

We need to find only number of moves, because players alternate turns. So if the total number of moves is odd Alan will win and if it is even Bob will win. At the beginning we can try to solve the problem if we have only one pile of sticks. This can be solved by Dynamic Programming.

When we are calculating the number of moves the game will last if the size of the pile is x:

1. We will try all possible moves = moves to x - k^2 for all k>0
2. If it is possible, we want to move to position from which the game lasts even number of moves (from such position we win and our opponent loses). If there are more such positions we will choose the smallest one, because we want to win as fast as possible.
3. If it is possible to move only to positions from which the game lasts odd number of moves, we will lose. We want to lose as slow as possible so we will choose the maximum.
Players must play in both piles in their turns, but their strategy in particular piles does not have any reason to change. Therefore the pile with lower overall number of moves will determine the winner.

Java code follows:
```public class PowerGame {

public int numberOfMoves(int size) {
// generate possible moves
int power=2;
int[] moves = new int;
int pocet = 0;
boolean big=false;
for (int i=1;i<105&&!big;i++) {
int num=1;
for (int j=0;j<power;j++) num*=i;
if (num>size) big=true; else {
moves[pocet]=num;
pocet++;
}
}
// find length of the game in this pile
int[] length = new int[size+1];
length=0;
int INF=999998;
for (int i=1;i<=size;i++) {
int smallestEven=INF;
int largestOdd=-1;
for (int j=0;j<pocet;j++) if (i-moves[j]>=0) {
int kam = i - moves[j];
if (length[kam]%2==0) {
if (length[kam]<smallestEven) smallestEven = length[kam];
} else {
if (length[kam]>largestOdd) largestOdd=length[kam];
}
}
if (smallestEven!=INF) length[i]=smallestEven+1;
else length[i]=largestOdd+1;
}
return length[size];
}

public String winner(int size0, int size1) {
int length0 = numberOfMoves(size0);
int length1 = numberOfMoves(size1);
int minimum = length0<length1 ? length0 : length1;
String name=(minimum%2==1)?"Alan":"Bob";
return name+" will win after "+String.valueOf(minimum)+" moves";
}

}

```

SchoolTrip  Used as: Division One - Level Two:
 Value 500 Submission Rate 120 / 390 (30.77%) Success Rate 73 / 120 (60.83%) High Score Eryx for 468.45 points (7 mins 28 secs) Average Score 282.94 (for 73 correct submissions)

Low constraints indicated that almost any correct solution will run in time. There were different types of solutions and their main difference was how hard it was to implement them.

It is almost always good idea to start thinking about the small problem. What happens if we have only 2 students? Lets call them A, B and their probabilities of hitting other students a, b. Student A starts, so after one move with probability a he will hit student B and the game will be finished and with probability (1-a) he will be unsuccessful and it will be B`s turn. So if there is the next move, student B will hit with probability b student A and the game will be finished or we will get back to the situation at the beginning with probability (1-b). Let the result for our situation at the beginning is x we can write the following equation from the facts above:

x = 1 + a*0 + (1-a)*(1 + b*0 + (1-b)*x)
x = (1 + (1-a)) / (1 - (1-a)*(1-b))

We can create similar equation by our program also for more students. If we want to calculate result x for the inital position we will get linear equation, because if one of the students is hit we will calculate result recursively for the circles with less students, so we can look at these values as constants. If all students in a whole round were unsuccessful we will get to original position, so result is our unknown variable x. And from this linear equation we will calculate x. The students want to minimize overall time of the game, so when we are calculating result for our position, we can try throwing ball at all of the other students, calculate all results and return minimum of them.

Another very popular way to solve this problem was based on the observation that the game will last long with very small probability. So the same idea with moving between positions with the above probabilities, but after few thousand of moves we can assume that the game will be finished. For example Eryx used this approach in the fastest submission.

ChessTraining  Used as: Division One - Level Three:
 Value 1000 Submission Rate 61 / 390 (15.64%) Success Rate 24 / 61 (39.34%) High Score marek.cygan for 950.73 points (6 mins 32 secs) Average Score 638.16 (for 24 correct submissions)

While queens can move through squares containing other queens, and multiple queens can coexist on a single square, we have the same situation as if each queen has her own chessboard. So it looks like we have a game that consists of several games. Experienced topcoder can start think that Grundy numbers will be useful. If you are not familiar with Grundy numbers, you can read about them in topcoder Algorithm Games tutorial.

We would be able to calculate and combine Grundy numbers of every queen position to find out who is the winner of the game only if the rules were that the player who can not move with any of the queens is declared the loser. But we have a different situation. The game is finished after only one subgame (queen) is finished.

If there is at least one queen at positions (0,x) or (x,0) or (x,x), where x>0, the game will be finished after first move, so Alice will be the winner.
If there is no queen at these positions:

• Nobody wants to move to these positions, because he will lose in the next move.
• So the situation will be the same as if we forbid to move to these positions.
Only when there is no other move available, a player will have to move to these positions. So only if he can not move with all the queens at their chessboards (without squares (0,x), (x,0) and (x,x) ). And this reduced problem can be solved now by using the Grundy numbers. First we calculate Grundy numbers for all squares (of course, except (0,x), (x,0), (x,x)) of the chessboards, but with not allowing moves to (0,x), (x,0) and (x,x). Then if xor of these values is 0, the winner of the game will be Bob, otherwise Alice.

Java code follows:

```public class ChessTraining {

public final int UN = -3; // unknown
public final int SW = -1; // superwinning
public final int SL = -2; // superlosing

public int[][] mem;

// calculate Grundy nummber for square (x,y)
public int wtia(int x,int y) {
if (mem[x][y]!=UN) return mem[x][y];
if (x==0&&y==0) return SL;
if (x==y||x==0||y==0) return SW;
HashSet<Integer> alles = new HashSet<Integer>();
int ret=0;
while (alles.contains(ret)) ret++;
mem[x][y]=ret;
return ret;
}

public int combine(int g1,int g2) {
if (g1==SW||g2==SW) return SW;
return g1^g2;
}

public String game(int[] x, int[] y) {
int N=100;
mem = new int[N][N];
for (int i=0;i<N;i++) for (int j=0;j<N;j++) mem[i][j]=UN;
for (int i=0;i<N;i++) for (int j=0;j<N;j++) {
mem[i][j]=wtia(i,j);
}
int ret=mem[x][y];
for (int i=1;i<x.length;i++) {
ret = combine (ret,mem[x[i]][y[i]]);
}
if (ret==0) return "Bob will win";
return "Alice will win";
}

}

``` By rasto6sk
TopCoder Member 