http://mirror.codeforces.com/problemset/problem/482/A
if k = n — 1, all of the differences must be different and one of them is d = n — 1, which means 1 and n must come together. till now we have [1 n]
to get d = n — 2, either 1 and n — 1 would have to come together, or n and 2
so, [n — 1, 1, n] or [1, n, 2] are correct.
I know that adding each element greedily to [1, n] at the back i.e. [1, n, 2, ].... does work[or to the front]
[1, n, 2, n — 1, 3, n — 2]
But, how does one think through it during the contest? Is it grabbing pen and paper and trying brute force like
approach to find solution? That would take a hell lot of time (at least for me). But this was an specific case, [k =
n — 1] and using this case, general solution is obtained. So, is looking for some special cases a problem solving
strategy?
I cannot infer how people reach such a simple and sweet solution for such a seemingly complex problem.
Any suggestions would be helpful.
I don't know what others think but to solve such kind of problems, brute-force technique helps a lot. I solved this problem earlier and for this I just wrote a code with
next_permutation()in C++ and checked the output for small n's. Then I found out a pattern and just coded it.In fact, even today I solved a problem on HackerEarth where I had to find a permutation of first N numbers such that the summation of all the absolute differences between any two consecutive number is maximum. I used brute-force technique eventually.
For me, the reasoning was like "Let's see how I can generate the desired permutation", I tried a couple of things and I ended up doing the following: {1, K + 1, 2, K, 3...}. That way, the first difference is K, the second one is K - 1, the third one is K - 2, and so on until we reach a difference of 1. After that, the "jump" to K + 2 will be smaller than K and the remaining differences will be all 1, so we're OK.