Problem Analysis

Revision en4, by bhikkhu, 2015-06-09 23:37:02

http://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.

Tags problem solving

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English bhikkhu 2015-06-09 23:37:02 11 Tiny change: 'ase, [k = n \n\n- 1] and u' -> 'ase, [k = \n\nn - 1] and u'
en3 English bhikkhu 2015-06-09 23:33:48 2 Tiny change: 'em/482/A\nif k = n' -> 'em/482/A\n\nif k = n'
en2 English bhikkhu 2015-06-09 23:33:34 48 Tiny change: 'if k = n &' -> 'http://codeforces.com/problemset/problem/482/A\nif k = n &'
en1 English bhikkhu 2015-06-09 23:32:01 991 Initial revision (published)