Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: TadijaSebez
Jedno od optimalnih uparivanje za 4 broja 
~A \leq B \leq C \leq D~ je uvek ![[(A, B), (C, D)]](//algoge.com/mathoid/6ff6fbe473816234ba94515286136ca53d300fa0/svg)
~[(A, B), (C, D)]~. Lepota ovog uparivanja je 
~A B + C D~. Pokazaćemo da uparivanja ![[(A, C), (B, D)]](//algoge.com/mathoid/82fc52d912c150449eda4d86236c32da3545e398/svg)
~[(A, C), (B, D)]~ i ![[(A, D), (B, C)]](//algoge.com/mathoid/713d4779d12f3c7e56c3abc0680ab3d7de67b296/svg)
~[(A, D), (B, C)]~ nikada nisu bolja. ![\displaystyle Lepota([(A, B), (C, D)])-Lepota([(A, C), (B, D)]) = A B + C D - A C-B D = A (B - C) + D (C - B) = (A - D) (B - C) \geq 0](//algoge.com/mathoid/aabd39de664a2da813b37e18f228701ad53c41ef/svg)
$$\displaystyle Lepota([(A, B), (C, D)])-Lepota([(A, C), (B, D)]) = A B + C D - A C-B D = A (B - C) + D (C - B) = (A - D) (B - C) \geq 0$$ ![\displaystyle Lepota([(A, B), (C, D)])-Lepota([(A, D), (B, C)]) = A B + C D - A D - B C = A (B - D) + C (D - B) = (A - C) (B - D) \geq 0](//algoge.com/mathoid/03238bc75900d7a5fc319c5266d5f2dd5b9d19e2/svg)
$$\displaystyle Lepota([(A, B), (C, D)])-Lepota([(A, D), (B, C)]) = A B + C D - A D - B C = A (B - D) + C (D - B) = (A - C) (B - D) \geq 0$$
Sada znamo da je rešenje da soritramo niz 
~A~ i uparimo ![[(A_1, A_2), (A_3, A_4) ... (A_{N-1}, A_N)]](//algoge.com/mathoid/b7e637ad858e8b71ad177017ab71df25c333f8c6/svg)
~[(A_1, A_2), (A_3, A_4) ... (A_{N-1}, A_N)]~.
Vremenska složenost: 
~O(NlogN)~
Comments