10026  Shoemaker's Problem
Moderator: Board moderators
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
Input
Output
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 4
 Joined: Thu Oct 25, 2007 3:00 pm
Still WA
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:
^ = new Line
What is wrong with my output or with my sollution ?
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^
What is wrong with my output or with my sollution ?

 New poster
 Posts: 32
 Joined: Tue Feb 13, 2007 1:31 pm
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!!
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
Yes! I agree with you, that this is a sorting problem!

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
Re: 10026  Shoemaker's Problem
Hi guys!
I understand the method of solving this problem: sorting by ratio.
But I have global question: why it works?..
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
my profile
Re: 10026  Shoemaker's Problem
Consider the optimal, leastcost 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[i1]) + S[i+1]*(T[1] + ... + T[i1] + T) + ...
Cost after the exchange of jobs i and i+1: cost2 = ... + S[i+1]*(T[1] + ... + T[i1]) + S*(T[1] + ... + T[i1] + T[i+1]).
We have: cost1 <= cost2, or cost1  cost2 <= 0, or, after simplification: S[i+1]*TS*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 twomachines flowshop problem (sorry, I can't remember exactly where, but I've seen it a few times in contests.)
Cost before the exchange: cost1 = ... + S*(T[1] + ... + T[i1]) + S[i+1]*(T[1] + ... + T[i1] + T) + ...
Cost after the exchange of jobs i and i+1: cost2 = ... + S[i+1]*(T[1] + ... + T[i1]) + S*(T[1] + ... + T[i1] + T[i+1]).
We have: cost1 <= cost2, or cost1  cost2 <= 0, or, after simplification: S[i+1]*TS*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 twomachines flowshop problem (sorry, I can't remember exactly where, but I've seen it a few times in contests.)

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
Re: 10026  Shoemaker's Problem
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.
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
my profile
Re: 10026  Shoemaker's Problem
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.
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.

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
Re: 10026  Shoemaker's Problem
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?
By the way, is it possible to solve this problem without sorting?
Now I lay me down to sleep...
my profile
my profile
Re: 10026  Shoemaker's Problem
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.
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.