Posted:

**Fri Oct 26, 2007 5:27 pm**The UVa Online Judge board

https://uva.onlinejudge.org/board/

Page **4** of **6**

Posted: **Fri Oct 26, 2007 5:27 pm**

Posted: **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

Posted: **Sat Nov 24, 2007 10:33 am**

Error - please delete

Posted: **Sat Nov 24, 2007 10:34 am**

Error - please delete

Posted: **Sat Nov 24, 2007 10:36 am**

Error - please delete

Posted: **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:

^ = 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 ?

Posted: **Fri Nov 30, 2007 7:24 pm**

Your output format is correct.

Posted: **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!!

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!!

Posted: **Sun Jun 08, 2008 1:05 pm**

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

Posted: **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?..

I understand the method of solving this problem: sorting by ratio.

But I have global question:

Posted: **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.)

Cost before the exchange: cost1 = ... + S

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

We have: cost1 <= cost2, or cost1 - cost2 <= 0, or, after simplification: S[i+1]*T

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.)

Posted: **Tue Dec 16, 2008 4:02 pm**

But.. Did

Posted: **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.*

And then after you reach T

Posted: **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?

By the way, is it possible to solve this problem without sorting?

Posted: **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.*

If all S