10026 - Shoemaker's Problem

[Mohammad Mahmudur Rahman]

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

[xinmeng]

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)~~]

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]

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

read the problem description carefully.
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]

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

[andysoft]

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

[Dao007forever]

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

[Marcelo]

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

[Jan]

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.

[Marcelo]

thanks!

my code too...

but uva returns WA!

[Jan]

You can post your code...

[Marcelo]

Thanks for your help!

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]

[Jan]

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.

[Marcelo]

Jan,

thanks!

My code is acepted now!

[Jan]

You are welcome. It would be better if you remove your code. [After logging in, use the edit option]