JOIN
Get Time
high_school  Match Editorials
TCHS SRM 33
Thursday, July 12, 2007

Match summary

HS SRM 33 was the first match in new season, so many high rated competitors that aren't eligible to compete anymore did not participate. Moreover, HS SRMs are now in parallel with regular SRMs, so many people just chose SRM, which was sponsored this time. Nevertheless, 63 participants made together a great competition. With quite standard easy and hard, they had to face tricky medium which led to very exciting challenge phase (with 35 out of 51 solutions challenged).

Thanks to the fastest submission on the hard, klopyrev won the match, despite he failed medium. neal_wu, the only one who solved all 3 problems correctly, unluckily finished second because of resubmissions on medium and hard. maciejk rounded up the top three with correct easy and hard, while other coders were far away as they had no more than one correct submission (although cheater_no1 managed to submit correct solution for the hard).

The Problems

CastleGuards rate it discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 53 / 63 (84.13%)
Success Rate 44 / 53 (83.02%)
High Score neal_wu for 248.78 points (1 mins 59 secs)
Average Score 201.10 (for 44 correct submissions)

The classical version of this problem has a restriction that we canít place guards in some fields, which makes the problem a way harder (it can be solved via bipartite matching). In our problem we can place our guards wherever we like. Letís consider empty rows and empty columns. We must place at least one guard in each. Itís obvious that we can place a guard in particular empty row such that heís placed in some empty column, and vice versa. So, placing guards one by one, weíre choosing some empty row and empty column (or if one of those doesnít exist weíre choosing it randomly) and place him there, until all rows and all columns are guarded. Now, itís easy to see that the answer is the number of empty rows or the number of empty columns, whichever is greater.

DogAndRabbit rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 51 / 63 (80.95%)
Success Rate 1 / 51 (1.96%)
High Score neal_wu for 331.98 points (16 mins 55 secs)
Average Score 331.98 (for 1 correct submission)

This problem also looks very easy at the first sight. But, in fact, itís not so simple. All we need to check is if the dog will catch the rabbit in time smaller than or equal to overall time the rabbit runs to his home. This overall time is distanceToHome / rabbitSpeed. Letís denote it with t. The distance that dog would run in that time is (dogAcceleration * t2) / 2. All we want to check is if that distance is greater then or equal to distanceToRabbit + distanceToHome. If it is, dog will surely catch the rabbit, and it wonít catch it otherwise. Ok.. so it looks like just a simple inequality and thatís it. But things are not so simple, because if we used floating point arithmetic we would surely fail. But rearranging our original inequality a bit gives us:

  dogAcceleration * distanceToHome2 
      >= 2 * rabbitSpeed2 * (distanceToRabbit + distanceToHome) .
We can check this condition using only integers, but even here we should be careful and use 64-bit types. Another thing about this problem are corner cases, when some of input parameters are equal to 0 Ė but this can be simply handled before checking above inequality. Sample solution follows:
  public String willCatch (int dTR, int dTH, int rS, int dA) {
      if (dTR == 0) return "YES";
      if (dA == 0) return "NO";
      if ((long)dA * dTH * dTH >= (long)2 * rS * rS * (dTR + dTH))
          return "YES";
      return "NO";
  }

AlmostPrime rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 15 / 63 (23.81%)
Success Rate 4 / 15 (26.67%)
High Score klopyrev for 931.82 points (7 mins 47 secs)
Average Score 680.57 (for 4 correct submissions)

Due to the fact that almost prime number is a prime raised at least to a second power, itís obvious that all almost prime integers less than or equal to B are powers of primes less then or equal to sqrt(B). We can find all these primes with sieve and then iterate over all of them raising each to all integer powers with exponent greater than 1, until the power is not greater than our upper bound. Time complexity of this solution is O( pi(sqrt(B)) * log(B) ), where B is given upper bound and pi(n) denotes how many primes that are not greater than n exist. There are exactly 664579 primes not greater than 107 so itís fine. But we should be very careful computing consecutive powers of each prime. Itís obvious that 32-bit types would overflow, but itís not so obvious that 64-bit types can overflow as well. We should be aware of that, though many competitors were not. See klopyrev's solution for reference.

Author
By mateuszek
TopCoder Member