Match Editorial

Match summary

During SRM 418, Division One coders were presented with a straightforward easy problem which gave them more time for very technical and time-consuming medium. Those who managed to finish (or skipped) 500-pointer faced a tricky 900-pointer with some tempting but incorrect solutions. Entering the challenge phase, there were 86 hard and almost 220 medium submissions. Unfortunately, most of them turned out to be wrong and only 7 coders were left with three problems solved. After all, ACRush was on top with an excellent performance on the 500 and 200 points earned in challenge phase. Petr and .Invader took second and third place respectively.

Division 2 saw quite difficult 250-pointer and simplified 900-pointer from Division 1. Solid submission on hard problem with three successful challenges won svolegov the division by a comfortable margin. He was followed by KingStone and lebed. mart0258 proved to be a fine coder as well. His 1000-pointer solution passes 234 from 235 tests of 900-pointer from Division 1.

The Problems

Value	250
Submission Rate	627 / 752 (83.38%)
Success Rate	369 / 627 (58.85%)
High Score	dogbox for 246.14 points (3 mins 34 secs)
Average Score	172.59 (for 369 correct submissions)

To solve this problem all we have to do is to keep destroying towers, one after another. The best way to do it is to count overall sum of towers' hit points (hpT*numT) and use integer division. However, we should be careful to avoid integer overflow. Here goes a sample solution:

int attack(int myUnits, int hpT, int attackT, int numT){
  int all = hpT*numT, ret=0;
        
  while(all>0 && myUnits>0){
    ret++;
    all -= myUnits;
    if(all<=0) break;   // without it the next line may cause integer overflow
    myUnits -= attackT*((all+hpT-1)/hpT);
  }
        
  if(myUnits>0) return ret;
  else return -1;
}

Value	500
Submission Rate	245 / 752 (32.58%)
Success Rate	185 / 245 (75.51%)
High Score	Lack.RP for 474.75 points (6 mins 37 secs)
Average Score	315.50 (for 185 correct submissions)

Value	250
Submission Rate	573 / 616 (93.02%)
Success Rate	531 / 573 (92.67%)
High Score	Petr for 248.80 points (1 mins 58 secs)
Average Score	208.99 (for 531 correct submissions)

In many countries, it is not rare to see lottery advertisements like 'choose 6 numbers out of 45 numbers, blah blah...' or 'take 5 numbers out of 39 numbers, blah blah...'. When you pass by the newsstand near your home, school, or work, you might compute the winning probability, from time to time.
In New York, USA, for instance, there is this lottery game called 'TAKE 5' where you choose 5 numbers between 1 and 39, inclusive. The winning probability (where you get all 5 numbers that will be chosen later) is easy to compute: 1 / Binom(39, 5) = 1 / 575757. Now there could be a second place where you get only 4 numbers correctly, and it is not very hard to compute. Out of 5 numbers that you choose, 4 numbers MUST BE chosen by the organizers and the other number MUST NOT BE chosen: Binom(5, 4) * Binom(39-5, 5-4) / Binom(39, 5) = 5 * 34 / 575757.
Now it can be generalized. the probability that you get exactly x numbers correctly is Binom(m, x) * Binom(n-m, m-x) / Binom(n, m). Thus, for the given problem, where it states 'at least k numbers', we can just sum up the probabilities for evrey x between k and m, inclusive.
See tkleczeksolution as a reference to this approach.
It is worth to note that this problem can be solved by brute-force approach as well since n is small enough. Since there can be at most 8 numbers from which you can choose, you can try all possible combinations of m numbers chosen out of 1..n, inclusive. Without loss of generality, we can assume that the organizers will choose m numbers (1, 2, ..., m). Then, we can easily count the number of permutations that contain more than or equal to k numbers between 1 and m, inclusive. Take an example with n = 5, m = 3, k = 2. Then, there are 5C3 = 10 possible combinations:
(1, 2, 3)       (1, 2, 4)
(1, 2, 5)       (1, 3, 4)
(1, 3, 5)       (1, 4, 5)
(2, 3, 4)       (2, 3, 5)
(2, 4, 5)       (3, 4, 5)
Out of these 10 combinations, there are only 7 combinations that contain 2 or more numbers between 1 and 3, inclusive:
(1, 2, 3)
(1, 2, 4)       (1, 2, 5)
(1, 3, 4)       (1, 3, 5)
(2, 3, 4)       (2, 3, 5)
This approach will take roughly O(n!). n is fairly small so that this approach would not cause a time-out.
Solutions with brute-force approach can be shorter than the classic binomial, probability approach. Because, at the end of the day, what we want to achieve during the competition is get a high score one each problem, you might better off writing a inefficient, short solution than a very elegant solution.

Value	1000
Submission Rate	105 / 752 (13.96%)
Success Rate	13 / 105 (12.38%)
High Score	lebed for 738.89 points (18 mins 18 secs)
Average Score	545.47 (for 13 correct submissions)

The hardest thing in this problem was to resist temptation of using (more or less sophisticated) strategy and simulate the battle. Only two non-DP solutions passed system cases.

Low constraints allow this problem to be solved by dynamic programming. Suppose we have i soldiers, barracks has z hit points, and our opponent has j soldiers. Then dp[i][j][z] is the minimum number of rounds we need to win the battle (or infinity if it is impossible). To compute dp[i][j][z] check each possible assignment of damage to the barracks and enemy soldiers. It seems not so hard, but there are some things we should be careful about:

• Don't consider triples (i,j,z) with j>100.
• Don't consider assignment of all damage to enemy soldiers while the barracks hasn't been destroyed yet. It's pointless and could cause infinite recursion if myUnits = unitsPerRound.
• When computing dp[i][j][z] we may need dp[i'][j'][z'] with j'>j. Make sure that you have computed all dp[i'][j'][z'] with i'<i and z'<z before or choose memoization approach.

For a better understanding look at the sample solution:

for(int i=1;i<=myUnits;i++) for(int z=0;z<=barHp;z++) for(int j=0;j<=100;j++){
  for(int k=0;k<=i;k++){
    int bH = max(0,z-k);    // barracks' hit points
    int op = max(0,j-i+k);  // number of enemy soldiers
    int mine = max(0,i-op); // number of our soldiers at the end of the round
                
    if(bH>0) op+=unitsPerRound;
    if(k==0 && bH>0) continue; 
    if(op<=100) dp[i][j][z] = min(dp[i][j][z],dp[mine][op][bH]+1);
  }
}

It is a simplified 900-pointer from Division 1. Have a look at description of Barracks for a better solution.

Value	500
Submission Rate	219 / 616 (35.55%)
Success Rate	75 / 219 (34.25%)
High Score	ACRush for 379.47 points (17 mins 11 secs)
Average Score	236.74 (for 75 correct submissions)

Let G be an undirected graph where vertices are the buyers with an associated value. There is an edge between two buyers if they share at least one stamp in their demand. It's easy to see that we have to find independent set of maximum value in G. The assumption about number of elements in demand and buyers who want to buy the same stamp makes G special - each vertex has at most two adjacent vertices. Because of that, each connected component is either cycle or simple path. Both of these cases can be solved with standard dynamic programming approaches. For clean solution you can take a look at Vitaliy's solution

Note that if we allowed buyers who want to buy 3 stamps and for each stamp no more than 3 who want to buy it, problem would become NP-complete.

The hardest thing in this problem was to code flawless solution. For most coders coding part took more than 30 minutes. Although examples cover most of boundary cases, success rate was rather low.

Value	900
Submission Rate	86 / 616 (13.96%)
Success Rate	20 / 86 (23.26%)
High Score	Soultaker for 669.54 points (18 mins 1 secs)
Average Score	503.20 (for 20 correct submissions)

Assume that an optimal solution requires to kill x enemy soldiers before we destroy the barracks. It's easy to show that to achieve best result we have to kill x soldiers as soon as they appear. So, if we knew x, we could follow simple greedy strategy. It turns out that we don't have to guess or compute x - we could try all possible x's and choose the best result. Unfortunately, straightforward simulation for each possible x will time out. We need to make some adjustments.

First of all, if myUnits≤unitsPerRound straightforward simulation won't definitely time out so let's assume that myUnits>unitsPerRound.

Choose x big enough. We may see that simulation consists of 4 phahes:

1. First round - we inflict myUnits hit points of damage to the barracks.
2. We kill all enemy soldiers and inflict (myUnits-unitsPerRound) hit points of damage to the barracks each round.
3. We inflict hit points of damage only to the barracks and let our opponent to produce soldiers.
4. Barracks is destroyed and all we have to do is to kill enemy soldiers.

It turns out that second phase takes most of the rounds, so all we have to do is to process it in constant time.

Exercises:

1. What is the complexity of above approach?
2. Many coders were checking only x's which are divisible by unitsPerRound. Prove or disprove this approach.
3. Suppose that k is the smallest number such that we kill k enemy soldiers before we destroy the barracks and win the battle. It's enough to check x's from [k,k+myUnits] - try to prove or disprove this approach.
4. Suppose that approaches above are correct - does it mean that it is enough to check x's from [k,k+myUnits] which are divisible by unitsPerRound? Try to prove or disprove this approach.