Match Editorial

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

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;
    }
};

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)

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(" ")[2]) 
                && rooms.contains(s.split(" ")[1]))
                    docs.add(s.split(" ")[0]);
        return docs.size();
    }
}

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.

public class PowerGame {

 public int numberOfMoves(int size) {
    // generate possible moves 
    int power=2;
    int[] moves = new int[105];
    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]=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";
 } 

}

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.

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.

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>();
    for (int i=0;i<x;i++) alles.add(wtia(i,y));
    for (int i=0;i<y;i++) alles.add(wtia(x,i));
    for (int i=1;i<=x&&i<=y;i++) alles.add(wtia(x-i,y-i));
    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[0]][y[0]];
    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";
 }

}