Saturday, September 20, 2008 Match summaryDuring SRM 418, Division One coders were presented with a straightforward easy problem which gave them more time for very technical and timeconsuming medium. Those who managed to finish (or skipped) 500pointer faced a tricky 900pointer 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 250pointer and simplified 900pointer 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 1000pointer solution passes 234 from 235 tests of 900pointer from Division 1. The ProblemsTowersUsed as: Division Two  Level One:
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+hpT1)/hpT); } if(myUnits>0) return ret; else return 1; }TwoLotteryGames Used as: Division Two  Level Two: Used as: Division One  Level One:
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. Used as: Division Two  Level Three:
The hardest thing in this problem was to resist temptation of using (more or less sophisticated) strategy and simulate the battle. Only two nonDP 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:
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,zk); // barracks' hit points int op = max(0,ji+k); // number of enemy soldiers int mine = max(0,iop); // 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 900pointer from Division 1. Have a look at description of Barracks for a better solution. StampsCollectionUsed as: Division One  Level Two:
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 NPcomplete. 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. BarracksUsed as: Division One  Level Three:
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:
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:

