## 10026 - Shoemaker's Problem

Moderator: Board moderators

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Hey, I've just got AC. I must confess that it was really a strange fault. I had been submitting it with a wrong problem number & started cracking my brain figuring out the error. . Such a stupidity....
You should never take more than you give in the circle of life.

xinmeng
New poster
Posts: 2
Joined: Thu Oct 26, 2006 2:18 pm

### 10026 runtime error help!

I compile and run my program. It solves ok and gives the correct answer on my computer. but, ACM gives me runtime error, the error message is Invalid memory reference. I cannot see where the error is. Can anyone help me or give me some test data? My main idea is to calculate the fine of all the permutations, find the smallest one.

#include <iostream>
using namespace std;

int count=0;
inline void swap( int & a, int & b){
int temp = a;
a = b;
b = temp;
}
void Perm( int a[], int k, int m, int ** array ){
// generate all permutations of list[ k:m ]
int i;
if( k == m ){
for( i = 0; i <=m; i++ )
array[count]= a[ i ];
count++;
}
else{
for( i = k; i <= m; i++ ){
swap( a[ k ], a[ i ] );
Perm( a, k+1, m,array );
swap( a[ k ], a[ i ]); // restore back to the original sequence
}
}
}

int main() {
int cases,n,i,t,k,j,tfine,min,mindex;
cin>>cases;
while(cases){
min=0;
mindex=0;
cases--;
t=1;
tfine=0;
cin>>n;
int *time=new int[n];
int *fine=new int[n];
for (i=0;i<n;i++)
cin>>time>>fine;
for (i=2;i<=n;i++)
t*=i;
int **atime=new int*[t];
for (i=0;i<t;i++)
atime=new int[n];
int **afine=new int*[t];
for (i=0;i<t;i++)
afine=new int[n];
count=0;
Perm(time,0,n-1,atime);
count=0;
Perm(fine,0,n-1,afine);

for (j=0;j<n;j++){
for (k=j+1;k<n;k++)
min+=atime[0][j]*afine[0][k];
}

for(i=1;i<t;i++){
for (j=0;j<n;j++){
for (k=j+1;k<n;k++)
tfine+=atime[j]*afine[k];
}
if (tfine<min){
min=tfine;
mindex=i;
}
tfine=0;
}

for(i=0;i<n;i++){
for (j=0;j<n;j++)
if (atime[mindex]==time[j])
cout<<j+1<<" ";
}
cout<<"\n";
delete []time;
delete []fine;
for (i=0;i<n;i++){
delete []atime;
delete []afine;
}
delete []atime;
delete []afine;
}
return 0;
} [/code]

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm
Can someone plzz explain me why this question is getting accepted by greedy!!!!
for the given test case the shomaker has to pay a fine of 2 cents.
But if he do the jobs in the order
2 3 1 4
he has to pay 0 cents!!

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
<:3)~~ wrote:Can someone plzz explain me why this question is getting accepted by greedy!!!!
for the given test case the shomaker has to pay a fine of 2 cents.
But if he do the jobs in the order
2 3 1 4
he has to pay 0 cents!!
u have to output a order of the jobs such that the total fine is minimized.

for each day the shoemaker has to pay fines for every other pending jobs.
suppose,
2
5 8
6 7
if he does the 1st job 1st then fine is 5*7=35
if he does the 2nd job 1st then fine is 6 8=42

thus,for the sample input "2 1 3 4" order yields a fine of (4+2+5)*1 + (2+5)*3 + 5*2 = 42
for the order "2 3 1 4" the fine is (4+2+5)*1 + (4+5)*2 + 5*3 = 44.

Diagnostic
New poster
Posts: 1
Joined: Tue Apr 10, 2007 7:47 am

### 10026 Shoemaker -- Test Data?

Would someone who's gotten AC on this problem mind posting some test data? It would be greatly appreciated.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hi guys!
I am trying to solve this prob, but I hit one problem: misunderstanding and total mess with the problem statement.

For example if we have:

Code: Select all

``````indx:    1     2    3    4
time:    3     1    2    5
fine:    4  1000    2    5
``````
What is the fine for sequence:
2 1 3 4 (Sample Out)
?
4+8+40 = 52 (Whinii F.'s method of understanding of statement)
OR
11 + 21 + 10 = 42 (How I firstly understood the statement)

And I am doubting if Sample OUT is OPTIMAL....

THANX FOR ANY HELP!!!!
Now I lay me down to sleep...
my profile

Dao007forever
New poster
Posts: 2
Joined: Sun Sep 09, 2007 8:45 pm
Contact:

### Compilation error??

I have my program compiled on Dev-C++.
But it keeps saying 'compilation error' on UVA. What can it be??

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

### I need help!

Ahhh... somebody help-me?
what's the output for this input?

Input:

Code: Select all

``````8

10
1 1
1 1
1 1
1 1
2 2
3 3
2 2
2 2
4 4
3 3

5
10 10
10 10
10 10
10 11
10 10

5
1 1
1 1
1 1
1 1
1 1

6
1 1
2 2
3 3
4 4
5 5
6 6

10
1 1
1 2
2 2
2 4
3 3
3 9
4 4
4 16
5 5
5 25

10
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6

10
1 1
1 2
2 1
2 2
3 1
3 2
4 1
4 2
5 1
5 2

20
200 10
190 10
190 9
200 11
199 10
199 11
200 11
200 9
201 9
201 10
201 11
191 9
10000 9999
9999 10000
10000 10000
9999 9999
5 10000
10000 5
5 5``````
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns...

Output:

Code: Select all

``````1 2 3 4 5 6 7 8 9 10

4 1 2 3 5

1 2 3 4 5

1 2 3 4 5 6

10 8 6 2 4 1 3 5 7 9

2 4 6 8 10 1 3 5 7 9

2 1 4 6 3 8 10 5 7 9

17 14 15 16 19 13 6 4 7 11 2 5 1 10 3 12 8 9 18 20``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm
thanks!

my code too...

but uva returns WA!
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

My code is:

Code: Select all

``...``

Advice: My english is very poor and so badly! I'll try to write, but I dont believe that I will successful!![/code]
Last edited by Marcelo on Tue Oct 02, 2007 4:56 pm, edited 1 time in total.
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your code looks correct except one thing. Check the case carefully...

Input:

Code: Select all

``````1

5
8 9
11 9
12 19
8 9
12 19``````
Output:

Code: Select all

``3 5 1 4 2^``
where '^' represents a newline character. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm
Jan,

thanks!

My code is acepted now!
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm