Let's go.
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
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.
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.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)
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.
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:
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=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.
E. Dead ends
The first thing you should notice - - 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[2n-1][x], where |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).
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[2n-1][x], where |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).
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?