Tuesday, September 18, 2007 Match summary
The Division I coders got a relatively easy set today, so speed did matter a lot. The easy problem was a pretty straightforward one, which most coders solved within a few minutes. The medium problem looked like simple brute force, but a few tricky corner cases made the problem slightly harder. The hard problem seemed to be really easy, but after a clarification came a couple of coders had to resubmit it and lost a lot of points. Because it was a close race, the challenge phase was quite important for the final score. Although tomekkulczynski was one of the people who had to resubmit the hard problem, he won the match because of his 5 successful challenges. Within a range of 50 points, ACRush and myprasanna (a new redranked Indian) became 2nd and 3rd. The ProblemsSerialNumbersUsed as: Division Two  Level One:
This was mainly a problem that needed a careful implementation of the steps described in the problem statement. To do the sorting, we could use the standard libraries with our own compare function, or we could write our own sorting algorithm, for example Bubble sort. The compare function should implement the steps descibed in the problem statement, using your own function to add the digits in a string. An example solution could look like: boolean isSmaller(String a, String b) { if (a.length() != b.length()) return a.length() > b.length(); if (sumOfDigits(a) != sumOfDigits(b)) return sumOfDigits(b) < sumOfDigits(a); return a.compareTo(b) > 0; } int sumOfDigits(String x) { int s = 0; for(int i = 0; i < x.length(); i++) if(x.charAt(i) > '0' && x.charAt(i) <= '9') s += x.charAt(i)  '0'; return s; }ChangingSounds Used as: Division Two  Level Two: Used as: Division One  Level One:
The key to this problem is that it is a typical dynamic programming problem. To solve it you should make a 2dimensional boolean array where element i, j indicates if you are able to play song i with sound level j. Initially, you set 0, beginLevel to true, and then iterate through all songs and sound levels where for each song i you update the values at i+1. See the solution below for this approach. public int maxFinal(int[] changeIntervals, int beginLevel, int maxLevel) { boolean[][] canHave = new boolean[changeIntervals.length+1][maxLevel+1]; for(int i = 0; i <= changeIntervals.length; i++) Arrays.fill(canHave[i], false); canHave[0][beginLevel] = true; for(int i = 0; i < changeIntervals.length; i++) { for(int j = 0; j <= maxLevel; j++) { if(canHave[i][j]) { if(j + changeIntervals[i] <= maxLevel) canHave[i+1][j + changeIntervals[i]] = true; if(j  changeIntervals[i] >= 0) canHave[i+1][j  changeIntervals[i]] = true; } } } int max = 1; for(int j = 0; j <= maxLevel; j++) if(canHave[changeIntervals.length][j]) max = j; return max; }PickGuitars Used as: Division Two  Level Three:
Before one can solve this problem, some insights about the problem are needed. The first thing is that, as soon as we picked the first guitar, we no longer have a circle, but we can think about the guitars as if they were in a line. Used as: Division One  Level Two:
With a constraint of a maximum of 10 guitars, this problem looked quite easy for a Div 1 medium problem. Because 2^10 = 1024 easily runs within the time limit, we can brute force all possible combinations of guitars we might want to buy. To do this, we use bitmasks (see this article for more information about bitmasks). For each bitmask, we do the following:
Before you do the brute force search, sort all guitars by name (and of course sort guitarSongs accordingly). Now, instead of using the rightmost bit to represent the first guitar in the list, we use the leftmost bit to represent it. This way, we are sure that if 2 bitmasks have the same number of bits, the greatest of the 2 will represent the list of guitars that comes first alphabetically. So in the loop there is no need to check for the alphabetically first items, we just check if either the number of songs is bigger then the best so far, or the number of songs is the same and the number of guitars is smaller or equal then the best so far. Because we try the bitmasks in increasing order, we are sure that we find the alphabetically first solution this way.
LateForConcert
While this problem could look like an adaption of a shortest path algorithm at first, it turned out that there is a much easier solution to the problem. If we think about it, a state can be defined as 4 integers: (x, y, timeLeft, lastmove). We know that x and y can both be 49 at most, timeLeft can be 100 at most, and, because we can only make 4 different moves, lastmove will be between 0 and 3. So, if we make a 4dimensional double table, it has a worst case size of 50*50*101*4 = 1010000, which is small enough to stay within time limits and memory bounds. for(int d = 0; d < 4; d++) if(d == inv[m]) continue; // To make sure we do not go back switch(cityMap[y].charAt(x)) { case 'X': case 'C': continue; case '.': case 'Y': if(x+dirx[d] > 0 && x+dirx[d] < width && y+diry[d] > 0 && y+diry[d] < height) table[x+dirx[d]][y+diry[d]][t1][d] = Math.min( table[x+dirx[d]][y+diry[d]][t1][d], table[x][y][t][d]); case 'S': if(x+dirx[d] > 0 && x+dirx[d] < width && y+diry[d] > 0 && y+diry[d] < height) table[x+dirx[d]][y+diry[d]][t1][d] = Math.min( table[x+dirx[d]][y+diry[d]][t1][d], table[x][y][t][d] + speedingTicket); case 'T': if(x+dirx[d] > 0 && x+dirx[d] < width && y+diry[d] > 0 && y+diry[d] < height) { table[x+dirx[d]][y+diry[d]][t1][d] = Math.min( table[x+dirx[d]][y+diry[d]][t1][d], table[x][y][t][d] + redLight); if(t > 2) table[x+dirx[d]][y+diry[d]][t2][d] = Math.min( table[x+dirx[d]][y+diry[d]][t2][d], table[x][y][t][d]); } } }Now, if we have updated all states, we can find the final answer by taking the lowest answer in the table for the concert hall position where timeLeft = 0, looking at all 4 directions (we don't care which way we entered the concert hall). If the smallest is INF, we couldn't reach the concert hall and we return 1. Otherwise, we return the lowest answer we've found. 
