Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

JuanFernandez's blog

By JuanFernandez, history, 5 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By JuanFernandez, history, 10 months ago, In English,

I wonder if there's an easy way to solve this problem using suffix automaton. There's a linear solution for this problem using suffix tree (link to a much harder version of a problem).

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By JuanFernandez, history, 2 years ago, In English,

It is well known that a x ≡ b (mod q) can be solved for x in applying meet-in-the-middle optimization after rewriting an equation like that a gk ≡ ba h (mod q), where gk - h = x.

How can one solve (a x mod p) ≡ b (mod q), where p, q are prime numbers and p > q?

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it