
Match Editorial 
SRM 124Thursday, December 12, 2002
The Problems
MakeTeam
Used as: DivisionII, Level 1:
Value

250 points 
Submission Rate

177 / 206 (85.92%) 
Success Rate

112 / 177 (63.28%) 
High Score

Johnfd for 236.31 points

This problem was pretty simple. Mostly just a matter of following instructions. First, you should check if a
team can be formed. If not, return "NO TEAM", otherwise, find the person with the shortest name,
remove him, and find the person with the longest name (in java):
if(n>names.length)return "NO TEAM";
if(n==names.length)return names[names.length1];
String shortest = names[0];
for(int i = 0; i<n; i++)
if(names[i].length()<=shortest.length())
shortest = names[i];
String longest = shortest;
for(int i = n; i<names.length; i++)
if(names[i].length()>longest.length())
longest = names[i];
if(longest.length()>shortest.length())return longest;
return shortest;
Patterns
Used as: DivisionII, Level 2:
Value

500 points 
Submission Rate

127 / 206 (62.65%) 
Success Rate

51 / 127 (40.16%) 
High Score

Johnfd for 464.48 points

There were a number of ways to do this. Obviously, the simplest thing to do is to check each
substring with the same length as the pattern. When testing two strings of the same length,
we want to check that for each character, whenever that character appears, it appears in the
same place in both strings. The simplest way to do this is
//s and t have the same length
public boolean match(String s, String t){
for(int i = 0; i<s.length(); i++){
if(s.indexOf(s.charAt(i))!=t.indexOf(t.charAt(i)))return false;
}
return true;
}
AlphaWord
Used as: DivisionII, Level 3:
Value

1000 points 
Submission Rate

60 / 206 (29.13%) 
Success Rate

41 / 60 (68.33%) 
High Score

simcoen for 823.03 points 
Used as: DivisionI, Level 1:
Value

250 points 
Submission Rate

93 / 106 (87.74%) 
Success Rate

88 / 93 (94.62%) 
High Score

SnapDragon for 242.77 points

There are potentially a huge number of possible orderings which satisfy the constraints, and
it is pretty clear that we shouldn't try to look at them all. Instead, we should add letters
1 at a time, starting with a, and put them as close to the end of the string as possible, since
the letter that we add is bigger than all previously added letters.
public String firstAlpha(String decree){
String ret = "a";
for(int i = 0; i<decree.length(); i++){
if(decree.charAt(i)=='B'){
ret += (char)('a'+i+1);
}else{
ret = ret.substring(0,ret.indexOf((char)(i+'a'))) + (char)('a'+i+1)
+ ret.substring(ret.indexOf((char)(i+'a')));
}
}
return ret;
}
StringCmp
Used as: DivisionI, Level 2:
Value

600 points 
Submission Rate

84 / 106 (79.25%) 
Success Rate

39 / 84 (46.43%) 
High Score

venco for 561.46 points

Most people solve this in two stages. First you parse the inputs to remove all the sequences of 0 characters, and end up with a sequence of positive numbers, matched to a sequence of characters, for each of the input strings. Once this is done, its not too hard to find where they differ. You keep two pointers, one to the current index in each expanded string. Then you have three cases. When the two pointers are the same, you increment them both by whatever number is associated with the next character (provided the characters are the same. If they are not, return the current pointer value). If the two pointers are different, check that the next character for the sequence with the smaller pointer matches the current character for the other sequence. If not, return the smaller pointer, otherwise, advance the smaller pointer. You repeat this process until you find a difference, or you hit the end of both sequences, and return 1. An alternative to this is, after you parse the strings, to join adjacent characters that are the same. After that, the two strings match only if the numbers and characters are identical, and it is simple to find the index of the difference. Here is some java code which makes use of the second method mentioned above:
String letters = "abcdefghijklmnopqrstuvwxyz";
public int firstDif(String code1, String code2) {
char[] let1 = new char[60], let2 = new char[60];
int[] num1 = new int[60], num2 = new int[60];
for (int i = 0; i < 2; i++) {
StringTokenizer st = new StringTokenizer((i==0?code1:code2),letters,true);
int size = 0, state = 1;
char[] let = (i == 0?let1:let2);
int[] num = (i == 0?num1:num2);
while (st.hasMoreTokens()) {
String curr = st.nextToken();
boolean hmm = false;
if (Character.isLetter(curr.charAt(0))) {
if (size!=0 && let[size1]==curr.charAt(0)) hmm = true;
if (state != 0)
if (hmm) num[size1]+=state;
else {
num[size] = state;
let[size] = curr.charAt(0);
size++;
}
state = 1;
} else state=Integer.parseInt(curr);
}
}
for (int i = 0, ret = 0; i < 50; i++) {
if (let1[i]!=let2[i]) return ret;
if (num1[i]!=num2[i]) return ret+Math.min(num1[i],num2[i]);
ret+=num1[i];
}
return 1;
}
Solar
Used as: DivisionI, Level 3:
Value

950 points 
Submission Rate

8 / 106 (7.55%) 
Success Rate

1 / 8 (12.50%) 
High Score

radeye for 424.92 points

This problem turned out to be much harder than anticipated. However, there are two ways to solve them, neither of which is too overly complicated.
There are two basic approaches to solving this problem. The first one uses some sort of iterative technique to test a whole bunch of points on the collector, and then determines the fraction of such points that can be seen. This approach can be seen in radeye's solution, where he tests 720 different points on the collector. To find out if a point can be seen, you can try a couple of different things. The first is to try a whole bunch more points on the window, and see if there is a line from some point on the window that does not hit one of the supports, and hits some point on the collector. If your step size is sufficiently small (i.e. you try enough points on the window), this method will work. However, a more precise test is to try a line which goes from each point on the collector, and just barely touches each corner of the box, and each corner of the supports. This is the basic idea behind radeye's solution. It turns out that java provides a very simple way to implement the strategy where we just test a whole bunch of points on the window:
public String dark(int x1, int y1, int x2, int y2) {
Rectangle r1 = new Rectangle(x1*120,(5y1)*120,120,120), r2 = new Rectangle(x2*120,(5y2)*120,120,120);
int ret = 0;
outer: for (double top = .5; top <= 719.5; top++){
for (double bottom = 0; bottom <= 720; bottom+=0.1) {
if (!r1.intersectsLine(top,0,bottom,720) && !r2.intersectsLine(top,0,bottom,720)) {
ret++;
continue outer;
}
}
System.out.println(top);
}
int g = gcd(720ret,720);
return ((720ret)/g)+"/"+(720/g);
}
Another, more precise method involves similar triangles. We can define three different areas of the collector: the region that can be hit by light going to the left of both beams, the light going to the right of both beams, and the light going between both beams. The two outer regions can be found quite simply using similar triangles. However this way is probably more difficult than is needed. Here is the writer's solution, which checks all relevant spots on the collector to see if they ever get hit by light.
public class Solar{ int F=2*3*4*5; int MX=6; int x1,y1,x2,y2;
public String dark(int zx1, int zy1, int zx2, int zy2){
x1=F*zx1; y1=F*zy1; x2=F*zx2; y2=F*zy2;
int tot=0;
for(int test = 1; test<F*MX; test+=2){
if(inShade(test)) tot+= 2;
}
int g = gcd(tot,MX*F);
return ""+tot/g+"/"+(MX*F/g);
}
boolean inShade(int xt){ //do shadows of xt cover the window?
int a1 = left(xt, x1,y1); int b1 = right(xt,x1,y1);
int a2 = left(xt, x2,y2); int b2 = right(xt,x2,y2);
return a1<=0 && ( b1>=F*MX  b1>=a2 && b2>=F*MX ) 
a2<=0 && ( b2>=F*MX  b2>=a1 && b1>=F*MX );
}
int left(int xt, int x, int y){ //block with support (at x,y)
if(xt>=x) y = y+F;
if(y==F*MX) return 0;
return xt+ (xxt)*MX/(MXy/F);
}
int right(int xt, int x, int y){
x=x+F;
if(xt<=x) y = y+F;
if(y==F*MX) return F*MX;
return xt + (xxt)*MX/(MXy/F);
}
int gcd(int a, int b){ if(b==0)return a; else return gcd(b, a%b);}
}
By
lbackstrom
TopCoder Member