[Timus 1522] Help to prove solution.

Правка en18, от sidereal, 2020-02-18 14:45:31

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_j \lt c_k$$$ held, 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_j \gt c_k$$$, 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_j \lt c_k$$$ and $$$b_i \lt c_j \lt a_k$$$. 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. Simply comparing two costs $$$cost(T_1, T_2)$$$ and $$$cost(T_2, T_1)$$$ in this case—and in general—is not a strict weak ordering, and thus undefined behavior for sorting (this can get AC though).

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский sidereal 2020-02-18 14:45:31 206
en17 Английский sidereal 2020-02-17 20:55:53 0 (published)
en16 Английский sidereal 2020-02-17 20:05:35 8 Tiny change: ' \lt c_i$ would hold, then t' -> ' \lt c_i$ held, then t'
en15 Английский sidereal 2020-02-17 19:59:13 621
en14 Английский sidereal 2020-02-17 19:52:49 889
en13 Английский sidereal 2020-02-17 19:34:59 247
en12 Английский sidereal 2020-02-17 19:33:49 227
en11 Английский sidereal 2020-02-17 19:31:25 110
en10 Английский sidereal 2020-02-17 19:29:36 17
en9 Английский sidereal 2020-02-17 19:29:03 87
en8 Английский sidereal 2020-02-17 19:27:28 4
en7 Английский sidereal 2020-02-17 19:27:17 2 Tiny change: 'is fine:\n~~~~~\n\' -> 'is fine:\n\n~~~~~\n\'
en6 Английский sidereal 2020-02-17 19:27:09 17
en5 Английский sidereal 2020-02-17 19:26:44 2 Tiny change: 'ne:\n~~~~~struct,202' -> 'ne:\n~~~~~\nstruct,202'
en4 Английский sidereal 2020-02-17 19:26:38 15
en3 Английский sidereal 2020-02-17 19:26:25 139
en2 Английский sidereal 2020-02-17 19:25:19 506
en1 Английский sidereal 2020-02-17 19:23:11 185 Initial revision (saved to drafts)