10026 - Shoemaker's Problem

[Jan]

I am little bit of sick right now, so, can't check your code, sorry. I have attached two files. Hope these help.

Input
Output

[cz.guardian]

Thx, it was very usefull. I finally noticed my problem in input and now it's accepted. Once again thx

[paul]

Error - please delete

[paul]

Error - please delete

[paul]

Error - please delete

[paul]

Hi,

I have a problem with validation of my code. For example (from Jan) input I got example output. But I still have WA. I really dont know why.

My program output look like this:

Code: Select all

2^
^
4^
3 4^
1 1000^
2 2^
5 5^
^
4^
3 4^
1 1000^
2 2^
5 5^
^
2 1 3 4^
^
2 1 3 4^

^ = new Line

What is wrong with my output or with my sollution ?

[Jan]

Your output format is correct.

[deadangelx]

I think this is a sorting problem.
It must not use Greedy to solve it.

Look.....

Day Cost Index Ratio(Cost/Day)
3 4 1 1.333333
1 1000 2 1000
5 5 4 1
2 2 3 1


First, sort Ratio(big to small)
Second, if some raito are the same, sort Index(small to big)

then It will be

Day Cost Index Ratio(Cost/Day)
1 1000 2 1000
3 4 1 1.333333
2 2 3 1
5 5 4 1

Do u see the answer? so intersting!!

[Igor9669]

Yes! I agree with you, that this is a sorting problem!

[andysoft]

Hi guys!
I understand the method of solving this problem: sorting by ratio.
But I have global question: why it works?..

[mf]

Consider the optimal, least-cost solution. If we exchange the order of any two adjacent jobs i and i+1 in it, then its cost must not decrease, or else it won't be optimal. Let's write this fact mathematically:

Cost before the exchange: cost1 = ... + S*(T[1] + ... + T[i-1]) + S[i+1]*(T[1] + ... + T[i-1] + T) + ...
Cost after the exchange of jobs i and i+1: cost2 = ... + S[i+1]*(T[1] + ... + T[i-1]) + S*(T[1] + ... + T[i-1] + T[i+1]).

We have: cost1 <= cost2, or cost1 - cost2 <= 0, or, after simplification: S[i+1]*T-S*T[i+1] <= 0. After some more simplification it becomes: T/S <= T[i+1]/S[i+1]. Which as you can see is basically a comparison function for sorting!


This trick of exchanging two adjacent elements can be very useful when you're dealing with problems involving permutation. For example, in problem 10037, and Johnson's two-machines flowshop problem (sorry, I can't remember exactly where, but I've seen it a few times in contests.)

[andysoft]

mf, I thank you so much for your quick reply. Now it is clear..
But.. Did you start thinking from that point with "optimal solution" and "exchanging two adjacent jobs in optimal solution"? Because I am still pretty unsure about how to come to these thoughts, though I understand your explanaition well.

[mf]

Well, actually you can ignore the word 'optimal' at the beginning. Just consider any solution - if you can exchange a pair of jobs in it and improve its cost then it can't be the best (optimal) solution. Thinking about how to improve an existing solution should be more intuitive, I guess.

And then after you reach T/S <= T[i+1]/S[i+1], it means jobs in every optimal solution have to be sorted by T/S, the same end result.

[andysoft]

I thank you, mf. Hope some day I will be able to help you too
By the way, is it possible to solve this problem without sorting?

[mf]

This problem is equivalent to sorting.
If all S=1, then whatever algorithm you use to solve it, at the end you get a sorted array T, so it'll be just a yet another sorting algorithm in disguise.