10026 - Shoemaker's Problem

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Oct 26, 2007 5:27 pm

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
Ami ekhono shopno dekhi...
HomePage

cz.guardian
New poster
Posts: 4
Joined: Thu Oct 25, 2007 3:00 pm

Post by cz.guardian » Sat Oct 27, 2007 4:49 am

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

paul
New poster
Posts: 4
Joined: Sat Nov 24, 2007 10:28 am

Post by paul » Sat Nov 24, 2007 10:33 am

Error - please delete
Last edited by paul on Sat Nov 24, 2007 10:38 am, edited 1 time in total.

paul
New poster
Posts: 4
Joined: Sat Nov 24, 2007 10:28 am

Post by paul » Sat Nov 24, 2007 10:34 am

Error - please delete
Last edited by paul on Sat Nov 24, 2007 10:38 am, edited 1 time in total.

paul
New poster
Posts: 4
Joined: Sat Nov 24, 2007 10:28 am

Still WA

Post by paul » Sat Nov 24, 2007 10:36 am

Error - please delete
Last edited by paul on Sat Nov 24, 2007 10:38 am, edited 2 times in total.

paul
New poster
Posts: 4
Joined: Sat Nov 24, 2007 10:28 am

Still WA

Post by paul » Sat Nov 24, 2007 10:37 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Nov 30, 2007 7:24 pm

Your output format is correct.
Ami ekhono shopno dekhi...
HomePage

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Post by deadangelx » Wed Feb 13, 2008 3:58 am

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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 10026 - Shoemaker's Problem

Post by Igor9669 » Sun Jun 08, 2008 1:05 pm

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10026 - Shoemaker's Problem

Post by andysoft » Tue Dec 16, 2008 1:40 pm

Hi guys!
I understand the method of solving this problem: sorting by ratio.
But I have global question: why it works?..
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10026 - Shoemaker's Problem

Post by mf » Tue Dec 16, 2008 3:00 pm

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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10026 - Shoemaker's Problem

Post by andysoft » Tue Dec 16, 2008 4:02 pm

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.
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10026 - Shoemaker's Problem

Post by mf » Tue Dec 16, 2008 4:17 pm

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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10026 - Shoemaker's Problem

Post by andysoft » Wed Dec 17, 2008 12:05 pm

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?
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10026 - Shoemaker's Problem

Post by mf » Wed Dec 17, 2008 12:26 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”