JOIN
 Match Editorial
SRM 241
Wednesday, May 4, 2005

Match summary

In Division 1, pparys took home his first SRM victory, solving all three problems correctly. bladerunner and Petr took the second and third slots. venco, Ruberik and misof rounded out the set of coders who successfully got all three.

In division 2, dplass was first, followed by matthew0028 who failed systests on his easy. As an interesting note, had his easy passed, he would still have been second place, but by a margin of less than 1 point. haixiashi made a good entrance to TopCoder with a third place finish, which catapaulted him into division 1 for next time.

The Problems

BlackjackWinner
Used as: Division Two - Level One:
 Value 250 Submission Rate 174 / 186 (93.55%) Success Rate 45 / 174 (25.86%) High Score HoldMeDown for 239.94 points (5 mins 51 secs) Average Score 192.17 (for 45 correct submissions)

This problem, given a certain value of bet will return one of four values: -bet, 0, bet, or bet * 3 / 2. The trick is to frame the if statements in the right order. Notice from the constraints that bet is always even, so rounding isn't an issue here.

```public int winnings(int bet, int dealer, int dealerBlackjack, int player, int blackjack) {
if (player > 21 || player < dealer && dealer ≤ 21)
return -bet;
if (dealerBlackjack == 1 && blackjack == 1)
return 0;
if (dealerBlackjack == 1 && blackjack == 0)
return -bet;
if (blackjack == 1 && dealerBlackjack == 0)
return bet * 3 / 2;
if (dealer > 21 || player > dealer)
return bet;
return 0;
}
```
ReportAccess
Used as: Division Two - Level Two:
 Value 500 Submission Rate 147 / 186 (79.03%) Success Rate 68 / 147 (46.26%) High Score Onko for 477.24 points (6 mins 15 secs) Average Score 375.30 (for 68 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 184 / 186 (98.92%) Success Rate 153 / 184 (83.15%) High Score sjelkjd for 248.16 points (2 mins 27 secs) Average Score 221.08 (for 153 correct submissions)

This problem was not especially difficult, and was rather straightforward. The point here was to see (hopefully) a quick way to write a solution. The initial thought might be to split out the permissions for each user into an array, split out the required permissions into an array, and compare, for each user, whether or not their permissions include all of the necessary ones. This is a fine solution, but could take a little while to code (relatively speaking).

The next thought might be to do a simple string search for each required permission within the permission string for each user. However, this by itself could fail in the case where the report requires permission for "system", and the user only has permission on "systemadmin". Instead, we need to search for a string that can't be a substring of something else.

We do this by padding each user's permission string with spaces on each end. We can then search for each required permission, padded with a space at the front and back, to ensure that it won't be a substring of another permission. The final requirement is to sort the resulting list of allowed users, which is handled trivially by the API for your language of choice.

```public String[] whoCanSee(String[] userNames, String[] allowedData, String[] reportData) {
int c = 0;
for (int i = 0; i < userNames.length; i++) {
allowedData[i] = " " + allowedData[i] + " ";
b[i] = true;
for (int j = 0; j < reportData.length; j++)
if (allowedData[i].indexOf(" " + reportData[j] + " ") == -1)
b[i] = false;
if (b[i]) c++;
}
String[] ret = new String[c];
c = 0;
for (int i = 0; i < userNames.length; i++)
if (b[i]) {
c++;
}
Arrays.sort(ret);
return ret;
}
```
AirTravel
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 35 / 186 (18.82%) Success Rate 14 / 35 (40.00%) High Score dplass for 750.01 points (17 mins 41 secs) Average Score 536.47 (for 14 correct submissions)

That we are given the distance formula is a big help here, as most people probably don't have it memorized. (I sure didn't.) Furthermore, deriving it can be a bit of a time consuming, and certainly math-intense exercise. Of course, looking for the appropriate online resources is always a good option, too. In any case, the first step is to calculate the distances between each pair of airports that we are allowed to travel, and store them in an array, where d[i][j] is the distance from airport i to airport j. Note the need to convert degrees to radians when using the trig functions. If we are not allowed to travel from airport i to airport j, we use a suitably high "infinity" value, like 999999, as our distance.

Next, we loop over our aiports, and essentially determine if the distance from airport i to airport j can be made shorter by travelling through airport k on the way. We execute this loop as many times as there are airports, to allow for the possibility that we travel through all of the airports. Notice here that if travel from i to j is not allowed, then travelling through k will only be better if travel from i to k and k to j are both allowed; this is due to our use of an infinity value.

Finally, we check our "best" distance from origin to destination, and return -1 if it's our infinity value (meaning we can't make that trip), or the value.

```double[][] d;

double mul = 3.14159265358979323 / 180;

public double cdist(double lat1, double lon1, double lat2, double lon2) {
return 4000 * Math.acos(Math.sin(lat1 * mul)
* Math.sin(lat2 * mul) + Math.cos(lat1 * mul)
* Math.cos(lat2 * mul) * Math.cos(lon1 * mul - lon2 * mul));
}

public double shortestTrip(int[] latitude, int[] longitude, String[] canTravel, int origin, int destination) {
d = new double[latitude.length][latitude.length];
for (int i = 0; i < latitude.length; i++) for (int j = 0; j < latitude.length; j++)
if (i == j) d[i][j] = 0; else d[i][j] = 999999;
for (int i = 0; i < canTravel.length; i++) {
String[] s = canTravel[i].split(" ");
for (int j = 0; j < s.length; j++) {
int k = Integer.parseInt(s[j]);
if (i != k) {
double t = cdist(latitude[i], longitude[i], latitude[k], longitude[k]);
System.out.println(i+" "+k+" "+t);
d[i][k] = Math.min(d[i][k], t);
}
}
}

for (int n = latitude.length - 2; n ≥ 0; n--)
for (int i = n; i < latitude.length; i++)
for (int j = 0; j < latitude.length; j++)
for (int k = 0; k < latitude.length; k++)
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
if (d[origin][destination] == 999999) return -1;
return d[origin][destination];
}
```
BrokenCalculator
Used as: Division One - Level Two:
 Value 500 Submission Rate 119 / 186 (63.98%) Success Rate 63 / 119 (52.94%) High Score tmyklebu for 427.23 points (12 mins 9 secs) Average Score 269.78 (for 63 correct submissions)

This problem, at first glance, might appear like a straightforward Breadth First Search, but upon digging in a little further, it's obvious a little more thought is needed.

The first thing to do is determine what numbers we can type in without using any operators. If our target is within this set, we return 1, 2, or 3 as appropriate.

Otherwise, we start keeping track of the fewest keys needed to get to every number from 0 to 999. Since our target will require an operator key after entering some number, we initialize those values we can reach to 2, 3, or 4, and the remainder to a suitable infinity value.

Next, we set up a queue for which values we will search, and populate it with all the values we can reach without operators. Then, we take numbers out of the queue one at a time, try each of the [up to four] operations on them, and add them back to the queue if the resultant number has been reached in less steps than our previous best. We continue this until the queue is empty. Note that after performing an operation, we will need to either press the equals key to see our result, or press another operator to continue our calculation. Hence, we always add 1 more key press after performing the operation.

Once the queue is empty, if our best result for the target is our infinity value, then it can't be reached, and return -1. Else, return the best result.

```// fewest keystrokes to get to target values
int[] best = new int[1000];

// fewest keystrokes not involving any operators
int[] bestnop = new int[1000];

// queue
int[] q = new int[1000000];
int p = 0;
int r = 0;

// add a value to the queue
{
q[p] = i;
p++;
}

// pull next value from queue
int get()
{
r++;
return q[r - 1];
}

// is there anything in the queue?
boolean full()
{
return (p > r);
}
public int fewestKeys(int[] keys, String operators, int target) {
// which operations can we do
boolean plus = (operators.indexOf("+") > -1);
boolean sub = (operators.indexOf("-") > -1);
boolean mul = (operators.indexOf("*") > -1);
boolean div = (operators.indexOf("/") > -1);

// initialize our infinity values
for (int i = 0; i < 1000; i++)
{
best[i] = 999999;
bestnop[i] = 999999;
}

// everything we can type with three numbers
for (int i = 0; i < keys.length; i++)
for (int j = 0; j < keys.length; j++)
for (int k = 0; k < keys.length; k++)
{
bestnop[keys[i] * 100 + keys[j] * 10 + keys[k]] = 3;
best[keys[i] * 100 + keys[j] * 10 + keys[k]] = 3;
add(keys[i] * 100 + keys[j] * 10 + keys[k]);
}

// ...with two numbers
for (int i = 0; i < keys.length; i++)
for (int j = 0; j < keys.length; j++)
{
bestnop[keys[i] * 10 + keys[j]] = 2;
best[keys[i] * 10 + keys[j]] = 2;
}

// ... with one number
for (int i = 0; i < keys.length; i++)
{
bestnop[keys[i]] = 1;
best[keys[i]] = 1;
}

// if we don't need any operators, no need to continue
if (best[target] < 999999) return best[target];

// we know we have to perform an operation, so add that keypress
for (int i = 0; i < 1000; i++)
if (best[i] < 999999) best[i]++;

// while there's more searching to do...
while (full())
{
// get next value to search
int n = get();

// try each allowed operation using each number we can reach without operators
// ... lather, rinse, repeat
for (int i = 0; i < 1000; i++)
if (bestnop[i] < 999999)
{
if (plus && n + i < 1000)
{
int t = best[n] + bestnop[i] + 1;
if (t < best[n + i])
{
best[n + i] = t;
}
}
if (sub && n - i ≥ 0)
{
int t = best[n] + bestnop[i] + 1;
if (t < best[n - i])
{
best[n - i] = t;
}
}
if (mul && n * i < 1000)
{
int t = best[n] + bestnop[i] + 1;
if (t < best[n * i])
{
best[n * i] = t;
}
}
if (div && i > 0)
{
int t = best[n] + bestnop[i] + 1;
if (t < best[n / i])
{
best[n / i] = t;
}
}
}
}

// is it impossible?
if (best[target] == 999999) return -1;

// otherwise return the result
return best[target];
}
```
PatternCutting
Used as: Division One - Level Three:
 Value 1000 Submission Rate 23 / 186 (12.37%) Success Rate 9 / 23 (39.13%) High Score pparys for 607.02 points (26 mins 50 secs) Average Score 493.02 (for 9 correct submissions)

The nature of this problem, especially given the tight constraint on the size of the paper, is that most people could do this very easily by hand. However, teaching a computer to do it is the real challenge here.

My solution works like this: first, figure out the four rotations of the pattern, and store them somehow. Then, setup an imaginary piece of paper, which is all there. Next, start from the upper-left, traversing left-to-right, top to bottom, trying to cut out a pattern at each location, rotated in each of the four orientations. Every time this is possible, cut it from our paper, recurse (starting at the next position), then put the pattern back into the paper to try the next rotation/position.

We simply keep track of the highest counts as we go, and return the best result. But, given 36 squares in the sheet of paper, that's 36 * 4 cutouts to try, and recursing after each attempt will clearly give us way too long of a run time. So, we need to optimize things a bit.

I introduced several optimizations in my solution. First, note that if the pattern is a 1x1 square or a 1x2 square, these are the two cases that return the largest number of cutouts, and are very easy results to calculate right up front.

Now, as we are cutting out from our pattern, we can do another big optimization: bailing out when we know that we can't improve our best result. For instance, if the paper has 36 squares, and the pattern uses 5 squares, we know, with certainty, that our result can never be more than 7. So, if we find a way to make 7 cutouts, we can return that result and look no more. Similarly, if we're at row 2, column 1 on this 6x6 sheet, we know that we only have 30 more squares to look at, so we can't possibly cut out more than 6 more squares. In my solution, I use the variable localMax to indicate this.

Similarly, when recursing, we pass in the best result we have found so far from that point, passed as the parameter min. So, for instance, if my recursion has yielded that it's possible to cut out 5 of a pattern from where I am already, I know that further recursive calls need not consider cases where it's no longer possible to cut out more than 5, since they cannot possibly improve my result. After all this is done, the recursive function simply returns the best result.

```// the sheet we cut from
public boolean[][] b;

// size of our paper
public int mx, my;

// the four rotations
public String[][] p;

// number of blocks in the pattern
public int c;

// cut out a pattern, rotated, at a given position
public void cut(int x, int y, int r) {
for (int i = 0; i < p[r].length; i++)
for (int j = 0; j < p[r][i].length(); j++)
if (p[r][i].charAt(j) == 'X') b[x + j][y + i] = true;
}

// paste the pattern back in
public void paste(int x, int y, int r) {
for (int i = 0; i < p[r].length; i++)
for (int j = 0; j < p[r][i].length(); j++)
if (p[r][i].charAt(j) == 'X') b[x + j][y + i] = false;
}

// can we cut the pattern out from here?
public boolean canCut(int x, int y, int r) {
if (x + p[r][0].length() > mx) return false;
if (y + p[r].length > my) return false;
for (int i = 0; i < p[r].length; i++)
for (int j = 0; j < p[r][i].length(); j++)
if (p[r][i].charAt(j) == 'X' && b[x + j][y + i]) return false;
return true;
}

// Determine the most cuttings we can do, starting at (x, y),
//  knowing that we don't care about results less than min
public int partialMax(int x, int y, int min) {
int best = 0;
while (y < my) {
int maxRemain = (my - y - 1) * mx + (mx - x);
maxRemain /= c;
if (min > maxRemain) return best;
if (best > maxRemain) return best;
int localbest = best;
for (int r = 0; r < 4; r++)
if (canCut(x, y, r)) {
cut(x, y, r);
x++; if (x ≥ mx) { x = 0; y++; }
localbest = Math.max(localbest, 1 + partialMax(x, y, localbest));
x--; if (x < 0) { x = mx - 1; y--; }
paste(x, y, r);
}
best = Math.max(best, localbest);
x++; if (x ≥ mx) { x = 0; y++; }
}
return best;
}

public int getMax(int width, int height, String[] pattern) {
// Deal with the trivial cases that could cause a timeout
if (pattern.length * pattern[0].length() == 2)
return (height * width / 2);
if (pattern.length * pattern[0].length() == 1)
return height * width;

// Determine the size of paper, and number of blocks in our pattern
c = 0;
for (int i = 0; i < pattern.length; i++) for (int j = 0; j < pattern[i].length(); j++)
if (pattern[i].charAt(j) == 'X') c++;
my = height;
mx = width;

// create our virtual paper
b = new boolean[width][height];

// and our pattern rotations
p = new String[4][];
p[0] = pattern;
p[2] = new String[pattern.length];
for (int i = 0; i < pattern.length; i++) {
p[2][i] = "";
for (int j = 0; j < pattern[0].length(); j++)
p[2][i] += pattern[pattern.length - 1 - i].charAt(pattern[0].length() - 1 - j);
}
p[1] = new String[pattern[0].length()];
for (int i = 0; i < pattern[0].length(); i++) {
p[1][i] = "";
for (int j = 0; j < pattern.length; j++)
p[1][i] += pattern[j].charAt(pattern[j].length() - i - 1);
}
p[3] = new String[pattern[0].length()];
for (int i = 0; i < pattern[0].length(); i++) {
p[3][i] = "";
for (int j = 0; j < pattern.length; j++)
p[3][i] += pattern[pattern.length - 1 - j].charAt(i);
}

// start our search-cutting from the upper left
return partialMax(0, 0, 0);
}
```
By timmac
TopCoder Member