Let's go.

Answer is

Proof is rather easy: every jump is shorter than the previous one.

D. Physical education

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 - 100

If there are no such one, write source string. 'Goodness' of string is checking with one

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 ^{3}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)

*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

Now we want to make

*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

*a*. Find in_{1}=b_{1}*b*element, that equals*a1*and move it to the first position. Similarly we can make*a*. So, we have_{2}=b_{2}*n*steps and at every step we do*n - 1*swaps at the most.*n<=300*, so*n(n-1)<=89700<10*.^{6}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

Now we know that

It's

Possible bugs are:

p.s. I'll be glad if you tell me my mistakes in English.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=2*. We need to find such^{x}*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(log*solution._{2}h)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*.

E. Dead ends

The first thing you should notice - -

Solution is dynamic programming

Recalculating isn't really hard. For empty subset and subset of two vertexes (either 0 or 1) answer is oblivious. Also you should know that there is no tree with exactly one dead end (it's easy to prove). Now for greater subsets: rundown

*n <= 10*. It means, that we have exponential solution and we can rundown some subsets.Solution is dynamic programming

*d[m][subm]*- number of ways to make connected tree from subgraph*m*(it's a bit mask) with dead ends*subm*(it's also a bit mask). Answer is sum of*d[2*, where^{n}-1][x]*|x|=k*(size of*x*as a subset is*k*).Recalculating isn't really hard. For empty subset and subset of two vertexes (either 0 or 1) answer is oblivious. Also you should know that there is no tree with exactly one dead end (it's easy to prove). Now for greater subsets: rundown

*i*from*subm*- one of dead ends. Cut it off from tree along some edge to*b*(*b*shouldn't be a dead end, otherwise we got unconnected graph). Now we have tree with lower count of vertexes and either decreased 1 number of dead ends or with changed*i*to*b*(if*b*had exactly two neighbors). Answer for this tree we know already. In the end of summarizing we should divide answer by*k*- each tree has been taken as many times, as it has dead ends (*k*).
Can someone help me with Problem E explanation ? Not getting much from the editorial Thanks

Could someone help me to explain why we can get correct/unrepeated answer if we add a new point linked by points which belong to the original graph and has number smaller than any leaf node?