Page 4 of 6

Posted: Fri Oct 26, 2007 5:27 pm
by 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

Posted: Sat Oct 27, 2007 4:49 am
by cz.guardian
Thx, it was very usefull. I finally noticed my problem in input and now it's accepted. Once again thx

Posted: Sat Nov 24, 2007 10:33 am
by paul
Error - please delete

Posted: Sat Nov 24, 2007 10:34 am
by paul
Error - please delete

Still WA

Posted: Sat Nov 24, 2007 10:36 am
by paul
Error - please delete

Still WA

Posted: Sat Nov 24, 2007 10:37 am
by 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 ?

Posted: Fri Nov 30, 2007 7:24 pm
by Jan
Your output format is correct.

Posted: Wed Feb 13, 2008 3:58 am
by 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!!

Re: 10026 - Shoemaker's Problem

Posted: Sun Jun 08, 2008 1:05 pm
by Igor9669
Yes! I agree with you, that this is a sorting problem!

Re: 10026 - Shoemaker's Problem

Posted: Tue Dec 16, 2008 1:40 pm
by andysoft
Hi guys!
I understand the method of solving this problem: sorting by ratio.
But I have global question: why it works?..

Re: 10026 - Shoemaker's Problem

Posted: Tue Dec 16, 2008 3:00 pm
by 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.)

Re: 10026 - Shoemaker's Problem

Posted: Tue Dec 16, 2008 4:02 pm
by 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.

Re: 10026 - Shoemaker's Problem

Posted: Tue Dec 16, 2008 4:17 pm
by 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.

Re: 10026 - Shoemaker's Problem

Posted: Wed Dec 17, 2008 12:05 pm
by 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?

Re: 10026 - Shoemaker's Problem

Posted: Wed Dec 17, 2008 12:26 pm
by 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.