### yeputons's blog

By yeputons, 10 years ago, translation, Let's go.

A. Autocomplete

In this problem you should read the statement and solve in any way. One of the most simple solutions is read string and last visited pages, sort (even bubble source - 1003 isn't a lot, 3rd power because we need 100 operations to compare two strings), and rundown pages. When we find good string, we should write it and exit.
If there are no such one, write source string. 'Goodness' of string is checking with one if (to check lengths and avoid RTE) and for.

C. Froggy (Little Frog)

IMHO it's the second difficulty problem. If you cannot see solution just after you saw the statement, you can write brute-force solution (rundown all permutation and check), run it for n=10 and see beautiful answer.
Answer is 1 n 2 (n-1) 3 (n-2) 4 (n-3) ... Let's define two pointers - l and r. In the beginning, the first one will point to 1, and the second one - to n. On odd positions write down l (and increase it), on even - r (and decrease it). Do it while l <= r.
Proof is rather easy: every jump is shorter than the previous one.

D. Physical education

This problem is also very easy. The first thing we should learn is moving element from position x to position y (y < x). Let's move x to position x - 1 with one oblivious swap. Then to position x -2. And so on.
Now we want to make a1=b1. Find in b element, that equals a1 and move it to the first position. Similarly we can make a2=b2. So, we have n steps and at every step we do n - 1 swaps at the most. n<=300, so n(n-1)<=89700<106.

B. Blog photo

Due to bug in GCC I've lost 25 minutes solving this problem. In the end I've used MSVC++.
But it was digression, now let's think.
The first thing we need to do is fix one side (which are power of two). Because there are two sides and copy-paste is great place for bugs it'll be better to make one more for from 1 to 2 and on the 2nd step swap w and h. It decreases amount of code.
Now we know that h=2x. We need to find such w, that 0.8 <= h/w <= 1.25. Solve inequalities for w: h/1.25 <= w <= h/0.8. Because w is integer, it can take any value from ceil(h/1.25) to floor(h/0.8) inclusive. We need to maximize square and h is fixed, so our target is maximize w. We need to let w=floor(h/0.8) and check that it fit borders. If so - relax the answer.
It's O(log2 h) solution.
Possible bugs are:
• You calculate square in 32-bit type or like this: int w = ..., h = ...; long long s = w * h; In this case compiler calculate w * h in 32-bit type first, and then convert it to long long. Solution is long long s = (long long)w * h
• floor(0.9999999999)=0. The floor function does not correspond with inaccuracy of floating point types. It can be solved either with adding something eps to number before calling floor, or with additional check that difference between floor's result and source value is not greater than 1 - eps.
• p.s. The floor function is up to 8-9 times slower that conversion to int. Tutorial of Codeforces Beta Round #49 (Div. 2)  Comments (2)