Match Editorial

Match summary

The match in Division 1 started quietly, as most coders struggled with an unusually tedious easy problem. However, the solutions finally started to pour in, as about 400 coders managed to submit something, and several coders even submitted all three. However, the challenge phase and the system tests proved most of the submitted solutions wrong, leaving only 163 coders with positive scores, and nobody with three problems correct. The pack was led by Andrew_Lazarev with the help of 3 successful challenges on top of his correct easy and hard submissions, followed by battyone (easy, medium and 100 challenge points) and Egor (easy and a very strong time on medium).

Division 2 was won by lyt with a huge margin of about 270 points. He was followed by newcomer hahao and vijeth.d. Competitors encountered another rather difficult set here, however, several coders managed to solve all three problems.

Generally, this SRM's problems put the emphasis on creative thinking and inventing new (albeit rather simple) ideas, and not on the knowledge of existing algorithms. That has proven to be a tough experience even for some top reds.

The Problems

Value	250
Submission Rate	558 / 574 (97.21%)
Success Rate	534 / 558 (95.70%)
High Score	bcsnmurthy for 249.61 points (1 mins 7 secs)
Average Score	231.98 (for 534 correct submissions)

This problem was very straightforward. One just needed to check if product ever appears in food, and if it does, multiply price by 1.1 to get the answer; otherwise multiply it by 1.18. See lyt's code for a sample implementation.

When using Java, one had to be careful to avoid == and use .equals() instead.

Value	550
Submission Rate	505 / 574 (87.98%)
Success Rate	143 / 505 (28.32%)
High Score	GAZZASharp for 514.71 points (7 mins 32 secs)
Average Score	370.52 (for 143 correct submissions)

This problem allowed several different correct approaches. In my view, the most elegant and easy to implement one was: return the number of eights in the longest common prefix of low and high, but pay attention to the length: if low is shorter than high, one needs to pad it with zeroes and thus the answer will be 0 as there will be no common prefix.

For example, let low be 1838583, and high be 1838683. They have a common prefix of 1838, and thus the answer is 2. However, if low was just 183858, then padding it to the length of high yields 0183858, and no common prefix, thus returning 0.

Once we have come up with such an idea, we need to prove it. Suppose the longest common prefix of low and high is α, the digit following it in low is x, and the digit following it in high is y. I.e., low = αx..., high = αy..., both ellipses have the same length and x is less than y. First, it's easy to see that α will start every number between low and high, and thus such a number of eights is unavoidable. But how do we not get more? If y is not equal to 8, the number αy00..0 yields the required number of eights (and lies between low and high), and if y equals 8, the number α799..9 will do.

See lyt's code for a sample implementation.

The solution for this problem remains the same if we change the digit 8 to 1, 2, ..., 7. However, changing it to 0 or 9 makes it a little more tricky — the correct solution for that modification (and its proof) is left to the reader.

Value	950
Submission Rate	85 / 574 (14.81%)
Success Rate	17 / 85 (20.00%)
High Score	Msching for 601.53 points (24 mins 53 secs)
Average Score	428.11 (for 17 correct submissions)

Value	300
Submission Rate	274 / 444 (61.71%)
Success Rate	97 / 274 (35.40%)
High Score	liympanda for 271.31 points (9 mins 26 secs)
Average Score	176.44 (for 97 correct submissions)

Consider i-th bottle. It contains amount[i] liters of percent[i]-% liquid, which means amount[i]*percent[i]/100 liters of substance and amount[i]*(100-percent[i])/100 liters of water.

Suppose we pour together all the bottles we have. We can calculate the total amount of substance and water we have by summing the above expressions; let these amounts be totalSubstance and totalWater. To avoid division, we can calculate them in centiliters (1/100 of a liter). Having done that, we find the concentration (percentage) of the solution as totalSubstance/(totalWater+totalSubstance). We need that number to be need/100. If it is, we're done — the answer is just the sum of all amounts.

In the other case, it is either more or less than required; suppose it's more. Then we need to somehow reduce the 'substance' part of our mix. It is clear that to achieve that faster we need to remove the bottle with the highest available percentage of the substance. If that is not enough, remove the bottle with the next highest percentage, and so on until we get the required percentage. In most of the cases, however, we will at some point 'jump over' the required percentage, which means that we need to take the last removed bottle partially.

The only remaining question is how to calculate how much of that bottle we should take. At the first glance the most obvious way seems to be binary search. However, let's examine the situation more carefully. Suppose all the remaining bottles have a liters of substance and b liters of water, and the last removed bottle had c liters of substance and d liters of water. We need to find such x that (a+x*c)/(a+b+x*(c+d))=need/100. x denotes the fraction of that bottle we should take. Getting rid of the division, we get (a+x*c)*100=(a+b+x*(c+d))*need — but that's a simple linear equation on x, so we can solve it easily and obtain the answer.

If the 'full mix's percentage is less than need, we do the same thing, but start with the bottles with the lowest percentage instead of the highest.

A similar approach was implemented by Andrew_Lazarev.

Value	600
Submission Rate	135 / 444 (30.41%)
Success Rate	53 / 135 (39.26%)
High Score	Egor for 523.18 points (11 mins 13 secs)
Average Score	334.64 (for 53 correct submissions)

Spatial geometry... Is it usually tough? Yes. Is this problem that tough? No! Strangely enough, this problem allows an almost planar solution.

Let's name our vertices A, B, C and D. At the first step, we check if triangles ABC and ABD are possible — that is, the triangle inequality holds for them: AB+BC>=AC, AB+AC>=BC, AC+BC>=AB, AB+BD>=AD, AB+AD>=BD, AD+BD>=AB. If at least one of the above doesn't hold, the answer is surely "NO".

In case they do, imagine the segment AB fixed in space, and triangles ABC and ABD rotating around it. What is the maximal and minimal possible value for CD, then? It is logical that the minimal possible value is achieved when they are in the same plane and 'co-aligned' — that is, points C and D are in the same semiplane with respect to AB, and the maximal possible value is achieved when they are in the same plane but 'counter-aligned' (one can prove this by applying the Pythagoras' theorem, I will omit the formulas, and just note that if AB is along the Ox axis, then rotating the triangles around it keeps the x-coordinates of C and D the same, thus the question is again reduced to a planar question in the Oyz plane).

To calculate that bounds, we need to find the possible coordinates of C and D in that plane. Suppose A has coordinates (0,0), B is at (b,0), and C is at (x,y). To find x, we apply the law of cosines: x=AC*cos(A), and cos(A)=(AC²+AB²-BC²)/(2*AC*AB). Then we find y with the help of Pythagoras. Finding the coordinates of D is done similarly, and then we just need to compute the required distances and check CD against them.

See Egor's code for a simple implementation of this approach.

rahulgarg123 used a different approach not requiring any floating-point computations. The formula given at this page allows us to find the squared volume of a tetrahedron given its six sides. It turns out that substituting impossible lengths of sides into that formula yields a negative value for that square, and that fact was employed in rahulgarg123's code.

Value	900
Submission Rate	15 / 444 (3.38%)
Success Rate	7 / 15 (46.67%)
High Score	Burunduk3 for 507.99 points (30 mins 26 secs)
Average Score	427.39 (for 7 correct submissions)

First, we need to somehow enumerate all the unit hexagons in our grid. Let's introduce a coordinate system, like shown on the following picture:

That picture gives us a clue on how to find the coordinates of all required unit hexagons: suppose the first coordinate is x, and the second is y, then the equations limiting our grid are:

• x>=0
• y>=0
• x<=s[2]+s[3]-2
• y<=s[1]+s[2]-2
• x-y<=s[0]-1
• y-x<=s[1]-1

So, basically, we just enumerate over all x's and y's between 0 and 100 and check the above constraints to get the list of unit hexagons. It turns out that everything we need from now is just a simple backtracking. We try to color each unit hexagon with each color, and prune if some colored hexagon has too much neighbors of some color. It turns out that this solution is quite fast, solving the biggest case in several tenths of a second.

Andrew_Lazarev is determining the list of eligible cells in a slightly different manner in his solution, however, you can surely refer to it for the backtracking part implementation.

The main difficulty was to convince oneself that such backtracking will run in time. Many high-rated coders failed to do that, started to implement difficult solutions involving dynamic programming, and couldn't do that successfully. I can't really think of any reasonable advice on that — one probably needed to use his/her intuition, or go for that backtracking from the lack of other implementable ideas.

Another interesting thing to notice is that by doing backtracking in the 'spiral' order from the center of the grid helps to solve this problem with the grid side lengths up to 8.