[Timus 1522] Help to prove solution.

Revision en15, by sidereal, 2020-02-17 19:59:13

Problem link: https://acm.timus.ru/problem.aspx?space=1&num=1522

In this problem all you have to do is to come up with clever sorting comparator.

This one is fine:

Explanation/Idea
code

After sorting the answer is just:

code

I don't understand how to prove all details of this solution, and hence my request.

I started trying to work out different cases. If we knew that in the first group the system of inequalities $$$a_i \lt b_i \lt c_i$$$ would hold, then the time needed to produce toy $$$T_2$$$ after toy $$$T_1$$$, with empty machines, would amount to $$$a_1 + b_1 + c_1 + c_2$$$; if we tried to produce $$$T_1$$$ after $$$T_2$$$, that is reverse the order, the time would equal to $$$a_2 + b_2 + c_1 + c_2$$$. If we were to compare two values we'd understand why we need to compare using $$$a_i + b_i$$$; $$$cost(T_1, T_2) - cost(T_2, T_1) = a_1 + b_1 - a_2 - b_2$$$.

Similarly, if we knew that the second group satisfies $$$a_i \gt b_i \gt c_i$$$, we could get that $$$cost(T_1, T_2) = a_1 + a_2 + b_2 + c_2$$$; and $$$cost(T_1, T_2) - cost(T_2, T_1) = b_2 + c_2 - b_1 - c_1$$$; and that's why the second group is sorted in descending order.

There are two other possible cases inside a single group: $$$b_i \lt a_i \lt c_i$$$ and $$$b_i \lt c_i \lt a_i$$$. In both cases the cost seems to be $$$cost(T_1, T_2) = a_i + \max(b_1 + c_1, a_2 + b_2) + c_2$$$. I don't know how to prove the comparator works for these. And there doesn't seem to be a nice way to get a comparator by subtracting costs.

I also don't know why we must append second group to the first. Why should there be these two groups? And why exactly it's better for the second group to follow the first? If we process the second group before the first, the cost is not optimal even in the test sample.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English sidereal 2020-02-18 14:45:31 206
en17 English sidereal 2020-02-17 20:55:53 0 (published)
en16 English sidereal 2020-02-17 20:05:35 8 Tiny change: ' \lt c_i$ would hold, then t' -> ' \lt c_i$ held, then t'
en15 English sidereal 2020-02-17 19:59:13 621
en14 English sidereal 2020-02-17 19:52:49 889
en13 English sidereal 2020-02-17 19:34:59 247
en12 English sidereal 2020-02-17 19:33:49 227
en11 English sidereal 2020-02-17 19:31:25 110
en10 English sidereal 2020-02-17 19:29:36 17
en9 English sidereal 2020-02-17 19:29:03 87
en8 English sidereal 2020-02-17 19:27:28 4
en7 English sidereal 2020-02-17 19:27:17 2 Tiny change: 'is fine:\n~~~~~\n\' -> 'is fine:\n\n~~~~~\n\'
en6 English sidereal 2020-02-17 19:27:09 17
en5 English sidereal 2020-02-17 19:26:44 2 Tiny change: 'ne:\n~~~~~struct,202' -> 'ne:\n~~~~~\nstruct,202'
en4 English sidereal 2020-02-17 19:26:38 15
en3 English sidereal 2020-02-17 19:26:25 139
en2 English sidereal 2020-02-17 19:25:19 506
en1 English sidereal 2020-02-17 19:23:11 185 Initial revision (saved to drafts)