Wednesday, December 19, 2007 Match summaryThe 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 ProblemsPrankUsed as: Division Two  Level One:
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.
#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: Used as: Division One  Level One:
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.
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(); } }PowerGame Used as: Division Two  Level Three:
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:
Java code follows: 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 (imoves[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:
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 (1a) 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 (1b). Let the result for our situation at the beginning is x we can write the following equation from the facts above: 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. ChessTrainingUsed as: Division One  Level Three:
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.
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==yx==0y==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(xi,yi)); int ret=0; while (alles.contains(ret)) ret++; mem[x][y]=ret; return ret; } public int combine(int g1,int g2) { if (g1==SWg2==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"; } } 
