Somebody else has submitted editorial earlier (and most probably better :) ) than me, so I guess I'll just post this to my TC Experiences, just as a note to myself and somebody else who find it useful.
SRM 350 Match Editorial This SRM attracted 990 coders although it is early morning match for coders in EST time region. In both division coders were presented with
"not as hard as usual" 1000 ptr problems, where 31 coders in Division 1 and 92 coders in Division 2 managed to solve the Hard problems. A sharp contrast to remedy what happened in the previous SRM where only 3 coders in Division 1, and 16 coders in Division 2 managed to solve the Hard problems. Usual suspect from Division 1,
Petr wins the match solving all 3 problems + 2 successful and 1 failed challenges, followed closely by
Gawry with solid coding performance and the third place is taken by
ACRush.
voidProject takes the win for Division 2 with 200 points gap, solving all problems + 6 succesfull challenges,
codenameHarmony although also have 5 succesful challenges only managed to reach 2nd spot, and the third spot belongs to
Torax with a solid coding performance.
DistanceBetweenStrings Used as : Division Two - Level One:
| Value | 250 |
| Submission Rate | 503/525 (96.18%)
|
| Success Rate | 303/503 (60.24%) |
| High Score | marutiborker for 248.61 points (1 mins 7 secs)
|
| Average Score | 205.17 (for 303 correct submissions) |
This problem ask you to count occurrence of letters in a letter set, both in string a and string b, then return the sum of squared letter count difference. With div I 250 Ptr the important question is not on how to make efficiently running program, but more on how to write it quickly. A simple loop of each character in letterset and the another 2 loop inside to calculate this letter occurence on each string would allow you to have a fast submission e.g:
public int getDistance(String a, String b, String letterSet)
{
int res = 0;
for(char c : letterSet.toLowerCase().toCharArray()){
int n1 = 0; for(char ca : a.toLowerCase().toCharArray()) if(c==ca) n1++;
int n2 = 0; for(char cb : b.toLowerCase().toCharArray()) if(c==cb) n2++;
n1 -= n2;
res += n1*n1;
}
return res;
}
But if you don't care about loosing some points in time, and you wanted a faster code (or perhaps you have experienced similar problem with counting alphabets) you could also do each loops only once. Count characters in string a and be once, and then once again loop for the letterSet. This produces a more efficient running program but it requires more time to think about it.
public int getDistance(String a, String b, String letterSet)
{
int res = 0;
int []ca = new int[26], cb = new int[26];
a = a.toLowerCase();
for(char c : a.toCharArray()) ca[c-'a']++;
b = b.toLowerCase();
for(char c : b.toCharArray()) cb[c-'a']++;
letterSet = letterSet.toLowerCase();
for(char c : letterSet.toCharArray()){
int d = ca[c-'a']-cb[c-'a'];
res += d*d;
}
return res;
}
SumsOfPerfectPowers SuccessRate: 82.36%(Div I)/38.26%(Div II)
Used as Division Two : Level Two
| Value | 500
|
| Submission Rate | 149/516 (28.88%)
|
| Success Rate | 57/149 (38.26%) |
| High Score | danielrocha for 248.61 points (9 mins 41 secs)
|
| Average Score | 247.19 (for 57 correct submissions) |
Used as Division One : Level One
| Value | 250 |
| Submission Rate | 380/465 (81.72%)
|
| Success Rate | 313/380 (82.37%) |
| High Score | Triple_M for 245.18 points (3 mins 59 secs)
|
| Average Score | 162.74 (for 303 correct submissions) |
We can start by questioning how many perfect power numbers are there within the maximum intervals. With some small experiments generating it, you could find out that it there are only 2421 numbers. Knowing this, you can be sure that generating all possible sum of perfect square within this interval, will be within time limits. With O(N^2) algorithms generating all sums, it requires less than 6 millions operations. Seems like what we need to do is just can generate all power numbers using a modified sieve type algorithm, and generate all possible sums, count those within the limit and we're done. But there are small details that have to be taken care of, like possible overflow when generating the perfect power numbers, and avoiding timeouts when generating the sums. One way that you could time out is by using standard set libraries instead of using simple boolean arrays to count only distinct sums.
public int howMany(int lo, int hi)
{
HashSet<Integer> allPower = new HashSet<Integer>();
allPower.add(0); allPower.add(1);
for(int i=2;i*i<=hi;i++)
// use long since this might overflow
for(long j=i*i;j<=hi;j*=i)
allPower.add((int)j);
int res = 0;
boolean sumPower[] = new boolean[hi+1];
for(int i : allPower)
for(int j : allPower)
// count only sum of perfect power square we have not yet seen
if(lo <= i+j && i+j <= hi && !sumPower[i+j]){
sumPower[i+j] = true; res ++;
}
return res;
}
BagsQuiz Used as Division Two : Level Three
| Value | 1000
|
| Submission Rate | 164/405 (40.49%)
|
| Success Rate | 92/164 (56.10%) |
| High Score | punzki for 926.11 points (8 mins 08 secs)
|
| Average Score | 588.80 (for 92 correct submissions) |
This problem is a straight forward simulation problem. We need only to keep track the container of each bags, and then perform each operations accordingly, making sure we made no invalid moves. Initially just let the container of each back equals to 0 (bag is numbered 1 to n inclusive, let us just use 0 as floor). When we put bags i inside bag j, it means that we set the container of i as j. When we set bag i loose, we want each of its content to be on the floor, so we check all bags whose container is i, and let it loose (set its container as 0). If we are swapping bags, then all the bags whose container is i, now is contained by j vice versa. You could also see the problem as a tree problem since each bags has one parents/containers. Java code follows:
public int checkIfProper(int n, String[] actions)
{
int [] container = new int[n+1];
for(String act : actions)
if(act.startsWith("PUT")){
String sp[] = act.split(" ");
int i = new Integer(sp[1]);
int j = new Integer(sp[3]);
// both of them should be on the floor, otherwise it is invalid
if(!(container[i]==0 && container[j] ==0)) return -1;
put i inside j, now i's container is j
container[i] = j;
} else if(act.startsWith("SET")){
String sp[] = act.split(" ");
int i = new Integer(sp[1]);
// not on the floor, invalid
if(container[i] != 0) return -1;
for(int j=1;j<=n;j++)
// if j is inside i, laid it out on the floor
if(container[j] == i)
container[j] = 0;
} else{
String sp[] = act.split(" ");
int i = new Integer(sp[1]);
int j = new Integer(sp[3]);
// both of them should be on the floor, otherwise it is invalid
if(!(container[i]==0 && container[j] ==0)) return -1;
for(int k=1;k<=n;k++) {
// things contained by i now contained by j
if(container[k] == i) container[k] = j;
else
// things contained by j now cointained by i
if(container[k] == j) container[k] = i;
}
}
int res = 0;
for(int i=1;i<=n;i++)
if(container[i] == 0) res ++; // its on the floor
else
if(container[i] < i) return -1; // improper configuration
return res;
}
StarsInGraphs Used as Division One : Level Two
| Value | 500
|
| Submission Rate | 288/454 (63.44%)
|
| Success Rate | 128/288 (44.44%) |
| High Score | ACRush for 464.74 points (7 mins 56 secs)
|
| Average Score | 293.01 (for 128 correct submissions) |
We could break down the original problems into sub-problems that has to be answered :
- How to count number of the stars for each vertex ?
- How would you detect cycles in the graphs, and find the longest path if there are no cycles ?
The first question is basic combinatorial problems, if we know that a vertex has n >= 3 edge coming out from it, we can have choose(n,k) numbers of k ray stars. Then number of stars in the vertex can be rephrased as sum of choose(n,k) for all k >=3. You could implement choose(n,k) function and calculate this literally or a bit further analysis would lead you to even simpler formula, since sum of all choose(n,k) for all k <= n is basically number of all subset of n element sets, and it is known to be 2^n, we want all this subset excepts those with less than 3 elements. We end up with this formula : (1<<n) - n*(n-1)/2 -n -1. Having figure out this basic formula you then need only to be careful about overflow while coding it.
The next question is a standard graph problems which keeps reoccurring on TopCoder. When asked about shortest/longest paths and cycle detection you could choose to do it the Floyd-Warshall ways (see for example Im2Good
solution ), or the dfs + memoization ways (see tomek's
solution ). In the first approach, after calculating the stars, you could build another graph, removing vertex that has zero or exceeding C stars, and keeping only edge on the original graph that connects vertexes with non decreasing number of stars.
PlaneDivision Used as Division One : Level Three
| Value | 1000
|
| Submission Rate | 50/312 (16.03%)
|
| Success Rate | 31/50 (62.00%) |
| High Score | ACRush for 630.72 points (18 mins 45 secs)
|
| Average Score | 592.01 (for 31 correct submissions) |
This is another 1000 point problems where perhaps 650 points are for knowing what to code and perhaps only 350 points in knowing how to code it. Even if you don't know about the math background, having read the problem (assuming you knew that a graph where there are no edges intersecting is a Planar Graph) you could use key word "Planar Graph" to ask Google, if you're feeling lucky you would end up
here.
Euler's Formula in that article states that if a finite,
connected, planar graph is drawn in the plane without any edge intersections, and
V is the number of vertices,
E is the number of edges and
F is the number of
faces (regions bounded by edges, including the outer, infinitely-large region), then
V − E + F = 2. For this problem we are interested in F excluding the infinite large region so
F' = F- 1 =2+E-V -1 = 1+E-V.
The problem reduces to calculating how many vertexes and edges are there in our set of lines. It is quite obvious that vertices are just the intersection points, and for each closest pair of vertices in a line (no other vertex in between this pair of vertex), there are edges. Points of intersections can found by doing line-segment intersections (refer to this
tutorial ). If you find v(i)>0 intersection points between a line i with all other lines, then you number of edges among these points are just e(i) = v(i)-1. You can get V and E by summing these values for all line i.
Counting number of distinct intersection points can be quite tricky due to precision error and possible integer overflow. If you are brave enough and familiar with tricks of using double you could have a look at qixin99's
solution for a reference (using array of doubles to implement the set of points). You could avoid using doubles by performing 64 bit integer arithmetic as what you can see in gawry's
solution. Another java implementation with similar ideas is as follow :
public int howManyFiniteParts(int[] x1, int[] y1, int[] x2, int[] y2)
{
int n = x1.length;
long [] A = new long[n], B=new long[n], C=new long[n];
for(int i=0;i<n;i++){
// A,B,C refer to the tutorial on line intersection points
A[i] = y2[i]-y1[i];
B[i] = x1[i]-x2[i];
C[i] = A[i]*x1[i]+B[i]*y1[i];
}
HashSet<P> points = new HashSet<P>();
int edges = 0;
for(int i=0;i<n;i++){
// Intersection points on line i
HashSet<P> iPoints = new HashSet<P>();
for(int j=0;j<n;j++) if(i!=j){
long d = (A[i]*B[j] - A[j]*B[i]); //determinant
if(d == 0) continue;
long x = (B[j]*C[i]-B[i]*C[j]);
long y = (A[i]*C[j]-A[j]*C[i]);
P p = new P(x,y,d);
points.add(p); // add p to set of all points
iPoints.add(p); // add p to set of point intersection of line i
}
if(iPoints.size() > 0)
edges += iPoints.size()-1;
}
if(points.size() < 3) return 0;
return 1+edges-points.size();
}
class P {
long x,y,d;
public P(long _x, long _y, long _d){
x = _x; y = _y; d = _d;
}
// HashSet will use this equals, instead of the hashCode() to differentiate elements
// since hashCode is overriden to always be zero thanks to Petr in practice room :)
public boolean equals(Object oo){
P o = (P)oo;
return x*o.d == d*o.x && y*o.d == d*o.y;
}
// override object hashCode() to avoid HashSet thinking that 0,0,-3 is different with 0,0,3
public int hashCode(){
return 0;
}
}
