323 - Jury Compromise

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

Moderator: Board moderators

Post Reply
Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Nov 16, 2002 9:36 am

I guess its due to algorithm.

Perhaps its not necessary to run all the loops. There may be some ranges to look for the optimum within.

BTW are you going to take part in Sunday's contest or not?
I wrote you several messages, but you keep silence. :evil:

craniac
New poster
Posts: 2
Joined: Mon Jun 16, 2003 11:25 pm
Location: Poland

323 - Jury compromise - WA

Post by craniac » Mon Jun 16, 2003 11:34 pm

I can't see any mistake in this code - it's dynamic programming. Could you please help me with some test cases?
[pascal]program p323;

type rec=record d,p,ind:byte; end;

var t:array[1..201,-201..201,0..20] of record w:byte; s:integer; end;
x,n,m,j,i,il,sp,sd,l,k,p:integer;
ci,cj:boolean;
tab:array[1..201] of rec;
wyn:array[1..21] of byte;

procedure zeruj;
begin
for i:=1 to n do
for j:=-200 to 200 do
for k:=0 to m do begin t[i,j,k].w:=0; t[i,j,k].s:=0; end;
end;

procedure qsort(l,r:byte);
var a,b,x:byte; y:rec;
begin
a:=l; b:=r; x:=tab[(a+b) div 2].p+tab[(a+b) div 2].d;
repeat
while tab[a].p+tab[a].d>x do inc(a);
while tab.p+tab.d<x do dec(b);
if a<=b then begin
y:=tab[a]; tab[a]:=tab; tab:=y;
inc(a); dec(b);
end;
until a>b;
if a<r then qsort(a,r);
if l<b then qsort(l,b);
end;

procedure qsort1(l,r:integer);
var a,b,x,y:integer;
begin
a:=l; b:=r; x:=wyn[(a+b) div 2];
repeat
while wyn[a]<x do inc(a);
while wyn>x do dec(b);
if a<=b then begin
y:=wyn[a]; wyn[a]:=wyn; wyn:=y;
inc(a); dec(b);
end;
until a>b;
if a<r then qsort1(a,r);
if l<b then qsort1(l,b);
end;

procedure doit;
begin
t[1,tab[1].p-tab[1].d,1].w:=1;
t[1,tab[1].p-tab[1].d,1].s:=tab[1].p+tab[1].d;
if n>1 then for i:=2 to n do begin
x:=tab.p-tab.d;
t[i,x,1].w:=1;
t[i,x,1].s:=tab.p+tab.d;
for j:=-200 to 200 do begin
for k:=1 to m do if t[i-1,j,k].w>0 then begin t[i,j,k].w:=2;
t[i,j,k].s:=t[i-1,j,k].s;
end;
for k:=1 to m-1 do
if (t[i-1,j,k].w>0) and (t[i-1,j,k].s+tab.p+tab.d>=t[i,j+x,k+1].s)
then begin t[i,j+x,k+1].w:=1; t[i,j+x,k+1].s:=t[i-1,j,k].s+tab.p+tab.d;
end;
end;
end;
end;

procedure writeit;
var w1,w2:integer;
begin
i:=0; j:=0;
while (t[n,i,m].w=0) and (t[n,j,m].w=0) do begin
inc(i); dec(j);
end;
if t[n,j,m].w=0 then cj:=FALSE else cj:=TRUE;
if t[n,i,m].w=0 then ci:=FALSE else ci:=TRUE;
if ci then w1:=t[n,i,m].s else w1:=0;
if cj then w2:=t[n,j,m].s else w2:=0;
if w2>w1 then i:=j;
l:=m; p:=i; sp:=0; sd:=0; x:=1;
for i:=n downto 1 do
if t[i,p,l].w=1 then begin
dec(l);
p:=p-tab.p+tab.d;
sp:=sp+tab[i].p; sd:=sd+tab[i].d;
wyn[x]:=tab[i].ind;
inc(x);
end;
writeln('Jury #',il);
writeln('Best jury has value ',sd,' for prosecution and value ',sp,' for defence:');
qsort1(1,m);
for i:=1 to m do write(' ',wyn[i]);
writeln;
end;

begin
n:=1; il:=0;
while not ((n=0) and (m=0)) do begin
readln(n,m);
if not ((n=0) and (m=0)) then begin
if il>=1 then writeln;
for i:=1 to n do begin
readln(tab[i].d,tab[i].p);
tab[i].ind:=i;
end;
inc(il); readln;
zeruj;
qsort(1,n);
doit;
writeit;
end;
end;
end.[/pascal]
I want to know God's thoughts
The rest are details

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Feb 05, 2004 1:33 pm

Didn't read your code, but check that the blank lines are as specified (between cases, no blank line at the end of the output) 323's special corrector doesn't handle PE correctly.

Saludos,
HoraPe

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Feb 19, 2004 5:47 pm

can you provide me outputs for this following inputs :

Code: Select all

2 1
14 4 
16 2 

24 20
11 15 
8 5 
11 10 
17 5 
17 2 
9 17 
3 16 
2 3 
16 4 
13 2 
6 1 
7 20 
15 13 
12 1 
13 8 
8 10 
17 15 
7 7 
18 3 
10 17 
14 5 
3 1 
19 7 
7 19 

8 3
1 8 
18 1 
10 14 
1 5 
2 6 
10 19 
1 1 
7 8 

26 20
16 1 
20 20 
2 5 
16 9 
11 14 
7 14 
4 14 
6 9 
20 6 
12 11 
5 9 
8 5 
16 12 
3 18 
6 2 
4 14 
17 14 
2 4 
15 2 
1 3 
12 14 
16 18 
17 14 
7 3 
2 16 
20 19 

14 9
10 12 
9 4 
10 18 
16 19 
18 19 
6 13 
15 14 
12 6 
5 11 
6 7 
13 20 
3 17 
18 19 
2 15 

0 0
thanks :) :)

-titid-
Kalo mau kaya, buat apa sekolah?

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Feb 19, 2004 7:07 pm

titid_gede wrote:can you provide me outputs for this following inputs :

...

thanks :) :)

-titid-

Code: Select all

Jury #1
Best jury has value 14 for prosecution and value 4 for defence:
 1

Jury #2
Best jury has value 195 for prosecution and value 192 for defence:
 1 2 3 6 7 8 10 11 12 13 14 15 16 17 18 20 21 22 23 24

Jury #3
Best jury has value 29 for prosecution and value 28 for defence:
 1 2 6

Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
 1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26

Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
 1 2 4 5 7 8 9 10 13

horape@elanor:~/acm$ tail 323.out
 1 2 6

Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
 1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26

Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
 1 2 4 5 7 8 9 10 13
Saludos,
HoraPe

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Apr 07, 2004 11:01 am

hello, everyone. :lol: :lol:

I kept getting WA, can someone provide more testcase. :cry:

Thanks

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

323 - Jury Compromise

Post by b3yours3lf » Sat Apr 24, 2004 8:10 am

I tried to solve this problem but i can't find good dp solution, the only way i found is use 200*200 size array, but i think that's not the optimal way. it there better way to solve this problem?

thanks in advance

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Wed Jun 16, 2004 8:58 pm

8 4
19 18
5 9
0 9
5 0
4 4
16 9
4 15
20 5



10 5
3 8
15 8
11 8
7 8
1 8
17 8
8 8
2 8
13 8
3 8



18 7
1 1
1 2
2 1
10 10
11 10
10 11
7 7
7 8
8 7
14 14
14 15
15 14
4 4
4 5
5 4
19 19
19 20
20 19

if u can think of it .. u can do it in software.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

323 - Jury Compromise WA - Please, Help!

Post by ErickNascimento » Fri Apr 07, 2006 7:01 pm

I am getting WA, but don't know why. My code works for the sample input.
Someone please give me inputs and outputs for this problem.
Thank you.

Code: Select all

 
#include <stdio.h>

#define MOD(a) ((a)>=0?(a):(-(a)))

#define MAXN 200+10
#define MAXM 20+10
#define INFINITO 99999999

#define UP 1
#define UP_LEFT 2

int nCases;

int n, m;
int d[MAXN], p[MAXN];
int D, P;
int diff[MAXN], sum[MAXN];

int C[MAXN+1][MAXM+1]; /* C[i][j] == (D(T)-P(T)) tal que |D(T)-P(T)| == minimal p/
S={1,..,i} e |T|=j */
int M[MAXN+1][MAXM+1]; /* M[i][j] == D(T)+P(T) == maximo p/ S={1,...i} |T|=j */
int E[MAXN+1][MAXM+1]; /* indica qual foi a escolha feita na posicao i, j (UP, ou
UP_LEFT)*/

int itens[MAXM];
int nItens;

/* Determina quais os itens que foram escolhidos */
void getItens(int i, int j){
  if(i==0 || j==0) { return; }
  if(E[i][j] == UP)
    getItens(i-1, j);
  else{ /*E[i][j] == UP_LEFT*/    
    getItens(i-1, j-1);
    itens[nItens++] = i-1;
  }
}


void knapsack(){
  int i, j;
  
  for (i=0; i<n; i++){
    diff[i] = d[i] - p[i];
    sum[i] = d[i] + p[i];
  }
  
  /* Caso Base */
  for (j=0; j<=m; j++)
    C[0][j] = INFINITO; 
  for (i=0; i<=n ;i++)
    C[i][0] = 0;
  
  
  for (j=0; j<=m; j++)
    M[0][j]=0;  
  for (i=0; i<=n; i++)
    M[i][0]=0;

  
  
  for (i=1; i<=n; i++) {
    for (j=1; j<=m; j++) {
      if(MOD(C[i-1][j]) == MOD(C[i-1][j-1]+diff[i-1]) ){
        /* Faz a escolha mais vantajosa */
        if(M[i-1][j] > M[i-1][j-1]+sum[i-1]){
          C[i][j] = C[i-1][j];
          M[i][j] = M[i-1][j];
          E[i][j] = UP;
        }else{
          C[i][j] = C[i-1][j-1] + diff[i-1];
          M[i][j] = M[i-1][j-1] + sum[i-1];
          E[i][j] = UP_LEFT;
        }
      }else{
        if ( MOD(C[i-1][j]) < MOD(C[i-1][j-1]+diff[i-1]) ){
          C[i][j] = C[i-1][j];       
          M[i][j] = M[i-1][j];
          E[i][j] = UP;
        }else{
          C[i][j] = C[i-1][j-1] + diff[i-1];
          M[i][j] = M[i-1][j-1] + sum[i-1];
          E[i][j] = UP_LEFT;
        }
        
      }
      
    }
  }
  
  getItens(n, m);  
}
  

int main(){
  int i;
  
  nCases=1;
  while(1){
    
    scanf("%d %d", &n, &m);
    if(n==0 && m==0)
      break;
    else
      if(nCases>1)
	printf("\n");
    
    for (i=0; i<n; i++)
      scanf("%d %d", &p[i], &d[i]);
    
    printf("Jury #%d\n", nCases++);
    
    nItens=0;
    knapsack();

    D=0; P=0;
    for (i=0; i<m; i++){
      D += d[itens[i]];
      P += p[itens[i]];
    }
    printf("Best jury has value %d for prosecution and value %d for defence:\n", P, D);
    for (i=0; i<m; i++)
      printf(" %d", itens[i]+1);
    printf("\n");
  }
  
  return 0;
}
 

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

NP=P???

Post by rcrezende » Fri May 05, 2006 12:35 am

Ol

metaphysis
Experienced poster
Posts: 129
Joined: Wed May 18, 2011 3:04 pm

Re: 323 - Jury Compromise

Post by metaphysis » Wed Sep 19, 2018 11:02 am

Test data generator.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    for (int cases = 1; cases <= 100; cases++)
    {
        int n = rand() % 100 + 1;
        int m = min(rand() % n + 1, 20);
        cout << n << ' ' << m << '\n';
        for (int i = 1; i <= n; i++)
        {
            cout << rand() % 21;
            cout << ' ';
            cout << rand() % 21;
            cout << '\n';
        }
        cout << '\n';
    }
    cout << "0 0\n";
    return 0;
}

Post Reply

Return to “Volume 3 (300-399)”