Match Editorials

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

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.

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 * t²) / 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) .

  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";
  }

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 10⁷ 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.