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).
The ProblemsCastleGuardsUsed as: Division One  Level One:
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. DogAndRabbitUsed as: Division One  Level Two:
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}) / 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 * distanceToHome^{2} >= 2 * rabbitSpeed^{2} * (distanceToRabbit + distanceToHome) .We can check this condition using only integers, but even here we should be careful and use 64bit 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 Used as: Division One  Level Three:
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^{7} so it’s fine. But we should be very careful computing consecutive powers of each prime. It’s obvious that 32bit types would overflow, but it’s not so obvious that 64bit types can overflow as well. We should be aware of that, though many competitors were not. See klopyrev's solution for reference. 
