431 - Trial of the Millennium

All about problems in Volume 4. 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
tokei
New poster
Posts: 5
Joined: Tue Aug 20, 2002 7:27 am

431 - Trial of the Millennium

Post by tokei » Sun Sep 29, 2002 12:48 am

Hmmm ....

I was wondering how to solve this problem.

First, I try to solve this problem like a 0/1 knapsack problem.

However, after I found the maximum points and the optimal number of evidence presentations within the time constraint, I had another problem which is how to find the sequence of the evidence presentations.

For example, I got maximum points: 62 and 14 tasks(evidence presentations) for the sample Input.

Then, I tried to use DFS to find the sequence.
However, this is too slow.....

My program cannot finish in 10 seconds....

Can anyone help me on this problem?

Thanks in advance. :-?

User avatar
nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

Post by nealzane » Fri Aug 22, 2003 8:06 pm

this code is wrong answer but i can't see where the defect is.

can anybody help?

thanks

[cpp]/* CODE DELETED */[/cpp]
Last edited by nealzane on Sat Aug 30, 2003 2:26 pm, edited 1 time in total.
8-)

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Wed Aug 27, 2003 7:49 am

Hello Neal,
I just got AC and generated an input file to compare my answer with yours.
The following is one of the case that differs:

Code: Select all

1

2
4 1 M
9 4 Y
7 1 E
2 2 B
6 4 W
9 1 N
6 3 F
The answer is obvious, but your program cannot output correctly.
If you need more random generated i/o, write pm to me.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 08, 2005 2:38 am

What is the answer to this test case? Is it

Code: Select all

Score  Time  Description
-----  ----  -----------
  7      1   E
  9      1   N

Total score: 16 points
 Total time: 2 hours
or should it be

Code: Select all

  9      1   N
  7      1   E
Does it matter?
If only I had as much free time as I did in college...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 08, 2005 3:04 am

I don't know what's wrong with my code. :-(
Does the order of items in the output matter?
Does the order of selecting the items during the DP matter?
If there are 0 items in the ouput, should the footer with the total value and total time appear?
I think I deal correctly with the case of 0 items.
Can anyone offer comments?

Code: Select all

code fixed.
Last edited by Abednego on Tue Jun 28, 2005 8:40 am, edited 1 time in total.
If only I had as much free time as I did in college...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jun 27, 2005 7:15 pm

Hi, Igor. I see you haven't still solved the problem.

My AC program sorts the output table, in this order: on time (in ascending order), on score (descending), on description (ascending). I don't know if it's necessary, I just followed the sample output. Also, during DP I minimize the total time.

Your program gave wrong output for this input:

Code: Select all

1

10
10 1 A
20 4 B
10 7 C

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Jun 28, 2005 8:39 am

Thanks! Your example found my bug. I need to practice DP more...
If only I had as much free time as I did in college...

niangjun
New poster
Posts: 3
Joined: Mon Dec 18, 2006 11:40 am

431 WA

Post by niangjun » Fri Dec 22, 2006 9:36 am

I keep getting WA for 431, here is my code

Code: Select all

program acm_431;
var score,time:array[1..100] of integer;
    des:array[1..100] of string;
    c,m,t,sum,i,n:integer;
    f:array[0..100,0..240] of integer;
    take:array[1..300,1..300] of integer;
    mem:array[1..300,1..300] of integer;
    ev:array[1..100] of integer;

procedure init;
var i,j,k:integer;  s,s1,s2,s3:string;
begin
        readln(t);
        k:=0;
        repeat
         readln(s);
         i:=1;
         while (i<=length(s)) and (s[i]=' ') do i:=i+1;
         j:=length(s);
         while (j>0) and (s[j]=' ') do j:=j-1;
         s:=copy(s,i,j-i+1);
         if (s<>'') then begin
                          k:=k+1;
                          i:=pos(' ',s);
                          s1:=copy(s,1,i-1);
                          while (i<=length(s)) and (s[i]=' ') do i:=i+1;
                          s:=copy(s,i,length(s)-i+1);
                          i:=pos(' ',s);
                          s2:=copy(s,1,i-1);
                          while (i<=length(s)) and (s[i]=' ') do i:=i+1;
                          s:=copy(s,i,length(s)-i+1);
                          des[k]:=s;
                          val(s1,score[k],j);
                          val(s2,time[k],j);
                         end;
        until (s='');
        m:=k;
end;

procedure calc;
var i,j,k,l:integer;    p1,p2,m1,m2:integer;
begin
        fillchar(f,sizeof(f),0);
        fillchar(take,sizeof(take),0);
        fillchar(mem,sizeof(mem),0);
        for i:=1 to m do
         for j:=1 to t do
                if (time[i]>j) then begin f[i,j]:=f[i-1,j]; take[i,j]:=0; mem[i,j]:=1; end
                               else if (f[i-1,j]>=f[i-1,j-time[i]]+score[i])
                                       then begin
                                             f[i,j]:=f[i-1,j];
                                             take[i,j]:=0;
                                             mem[i,j]:=1;
                                            end
                                       else begin
                                             f[i,j]:=f[i-1,j-time[i]]+score[i];
                                             take[i,j]:=1;
                                             mem[i,j]:=2;
                                            end;
        sum:=f[m,t];
end;

procedure backtrack;
var i,j,k,l:integer;
begin
        fillchar(ev,sizeof(ev),0);
        i:=m;
        j:=t;
        k:=0;
        while (mem[i,j]<>0) do
         begin
          if (take[i,j]=1) then begin k:=k+1; ev[k]:=i; end;
          if (mem[i,j]=1) then i:=i-1
                          else begin j:=j-time[i]; i:=i-1; end;
         end;
        n:=k;
end;

procedure sort;
var i,j,k,l:integer;
begin
        for i:=2 to n do
         begin
          j:=1;
          l:=ev[i];
          while (j<i) and
          ((time[ev[j]]<time[ev[i]]) or (time[ev[j]]=time[ev[i]]) and (score[ev[j]]>score[ev[i]]))
           or ((time[ev[j]]=time[ev[i]]) and (score[ev[j]]=score[ev[i]]) and (des[ev[j]]<des[ev[i]])) do j:=j+1;
          if (j<i) then begin
                         for k:=i downto j+1 do ev[k]:=ev[k-1];
                         ev[j]:=l;
                        end;
         end;
end;

procedure output;
var i,j,k:integer; tt:integer;
begin
        tt:=0;
        writeln('Score  Time  Description');
        writeln('-----  ----  -----------');
        for i:=1 to n do
                begin
                 if (13+length(des[ev[i]])=80) then
                 write(score[ev[i]]:3,time[ev[i]]:7,'   ',des[ev[i]])
                 else writeln(score[ev[i]]:3,time[ev[i]]:7,'   ',des[ev[i]]);
                 tt:=tt+time[ev[i]];
                end;
        writeln;
        writeln('Total score: ',sum,' points');
        writeln(' Total time: ',tt,' hours');
end;

begin
        readln(c);
        readln;
        for i:=1 to c do
         begin
                init;
                calc;
                backtrack;
                sort;
                if (f[m,t]=0) then
                              writeln('There is not enough time to present any evidence. Drop the charges.')
                         else output;
         end;
end.
any one can tell me where I get it wrong or give me some test cases that expose my error?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 22, 2006 7:09 pm

First search your problem in the forum. And if you find a thread use it. Otherwise open a new one. Check the link below.
http://online-judge.uva.es/board/viewto ... hlight=431
Ami ekhono shopno dekhi...
HomePage

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sat Sep 08, 2007 11:53 am

mf wrote:

Code: Select all

1

10
10 1 A
20 4 B
10 7 C
This is my code give for that input.

Code: Select all

Score  Time  Description
-----  ----  -----------
 10      1   A
 20      4   B

Total score: 30 points
 Total time: 5 hours
Is it right?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Sep 08, 2007 5:47 pm

Yes, it's correct.
Ami ekhono shopno dekhi...
HomePage

vijay_comc
New poster
Posts: 3
Joined: Sat Nov 03, 2007 6:01 pm

Re: 431 - Trial of the Millennium

Post by vijay_comc » Tue Oct 28, 2008 1:28 pm

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<sstream>
using namespace std;
#define GI ({int t;scanf("%d",&t);t;})
#define sz size()
#define pb push_back

typedef vector<int> vi;
typedef vector<string> vs;
int dp[105][250];
int path[105][250];
int main()
{
	int t =GI;
	string str;
	while(t-->0)
	{
		int lim = GI;
		memset(dp,0,sizeof(dp));
		memset(path,0,sizeof(path));
		getchar();
		vi time, score;
		vs desc;
		int n = 0;
		while(true) {
			getline(cin,str);
			if(str.sz == 0) break;
			stringstream in(str);
			int score_, time_;
			string desc_;
			in >> score_ >> time_;
			getline(in,desc_);
//			cout << score_ << " " << time_ << " " << desc_ << endl;
			score.pb(0), time.pb(0), desc.pb(string());
			int i;
			for(i = n-1; i >= 0 && time[i] > time_; i--)
			{
				time[i+1] = time[i], score[i+1] = score[i], desc[i+1] = desc[i];
			}
			time[i+1] = time_, score[i+1] = score_, desc[i+1] = desc_;
			n++;
		}

		for (int i = n; i --> 0; )
		{
			if(i == n-1) {
				if(time[i] <= lim) dp[i][time[i]] = score[i], path[i][time[i]] = 1;
				dp[i][0] = 0;		
				path[i][0] = 0;
			}
			else
			for (int s = lim; s >= time[i]; s--)
			{
				dp[i][s] = dp[i+1][s];
				if(dp[i][s] < score[i] + dp[i+1][s-time[i]]) {
					dp[i][s] = score[i] + dp[i+1][s-time[i]];
					path[i][s] = 1;
				}
			}
		}
		int mm = 0, maxs = -1;
		for( int s = lim; s >= 0; s--) 
		{
			if( dp[0][s] >= mm ) mm = dp[0][s], maxs = s;
		}
		if(mm == 0) printf("There is not enough time to present any evidence. Drop the charges.\n");
		else {
		printf("Score  Time  Description\n");
		printf("-----  ----  -----------\n");
		for(int i = 0, s = maxs; i < n; i++)
		{
			if(path[i][s]) {
				s -= time[i];
				printf("%3d%7d   %s\n",score[i],time[i],desc[i].c_str());			
			}
		}
		printf("\n");
		printf("Total score: %d points\n",mm);
		printf(" Total time: %d hours\n",maxs);
		}
		if(t)
		printf("\n");
	}
	return 0;
}
Guys, I am Getting PE for this...
Any Help will be Appreciated...
cheers,
vijay

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 431 - Trial of the Millennium

Post by red_apricot » Mon Oct 26, 2015 2:21 pm

I'm getting WA for this:

Code: Select all

/*
 * 431. Trial of the Millenium
 * TOPIC: dp
 * status:
 */
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 0x80
#define MAXT BIT(9)
#define FG (ptr = fgets(buff,sizeof buff,stdin))
#define oo 0xfffffffful
#define S 8
#define BIT(k) (1UL<<(k))
#define MASK(k) (BIT(k)-1UL)
#define enc(x,y) ((x)|((y)<<S))

int empty( char *ptr ) {
	for (;*ptr && *ptr != '\n' && isspace(*ptr); ++ptr );
	return !*ptr || *ptr == '\n';
}

int m,T,n,score[N],tm[N],TT,idx[N];
char buff[0x400],*ptr,
	 desc[N][0x400];
unsigned int z[N][MAXT],way[N][MAXT];

int cmp( const void *a, const void *b ) {
	int *x = (int *)a,
		*y = (int *)b;
	if ( tm[*x] == tm[*y] ) {
		if ( score[*x] == score[*y] ) {
			return strcmp(desc[*x],desc[*y]);
		}
		return score[*x]>score[*y]?-1:1;
	}
	return tm[*x]<tm[*y]?-1:1;
}

void dump( int k, int t ) {
	int pk,pt;
	if ( t == 0 || k == 0 ) return ;
	pk = (way[k][t]&MASK(S)), pt = (way[k][t]>>S);
	if ( pt != t ) {
		/*printf("%3d %6d   %s\n",score[k],tm[k],desc[k]);*/
		idx[m++] = k;
	}
	dump(pk,pt);
}

unsigned int max ( unsigned int x, unsigned int y ) { return x<y?y:x; }

unsigned int calc_z( int k, int t ) {
	if ( z[k][t] < +oo ) return z[k][t];
	if ( k == 0 || t == 0 ) return z[k][t] = 0;
	assert( t >= 1 );
	assert( k >= 1 );
	z[k][t] = calc_z(k-1,t), way[k][t] = enc(k-1,t);
	if ( tm[k] <= t && calc_z(k-1,t-tm[k]) < +oo ) {
		if ( z[k][t] < z[k-1][t-tm[k]]+score[k] )
			z[k][t] = z[k-1][t-tm[k]]+score[k], way[k][t] = enc(k-1,t-tm[k]);
	}
	return z[k][t];
}

typedef struct {
	int score,t;
	char d[0x80];
} cell;

int cm( const void *a, const void *b ) {
	cell *x = (cell *)a,
		 *y = (cell *)b;
	if ( x->t == y->t ) {
		if ( x->score == y->score ) {
			return strcmp(x->d,y->d);
		}
		return x->score>y->score?-1:1;
	}
	return x->t<y->t?-1:1;
}

cell c[N];

int main() {
	int i,j,k,l,cs = 0,ts;
	unsigned int w;
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
#endif
	for ( sscanf(FG,"%d",&ts), FG; ts--; ) {
		for ( k = (1<<29), sscanf(FG,"%d",&T), n=0; FG && !empty(ptr); ++n ) {
			assert( 3 == sscanf(ptr,"%d %d %[^\n]",score+n+1,tm+n+1,desc[n+1]) );
			if ( tm[n+1] < k ) k = tm[n+1];
			c[n+1].score = score[n+1], c[n+1].t = tm[n+1], strcpy(c[n+1].d,desc[n+1]);
		}
		/*
		qsort(c+1,n,sizeof *c,cm);
		for ( i = 1; i <= n; ++i )
			tm[i] = c[i].t, score[i] = c[i].score, strcpy(desc[i],c[i].d);
		*/
		for ( i = 0; i <= n; ++i )
			for ( j = 0; j <= T; z[i][j++] = +oo );
		w = calc_z(n,T);
		if ( w == 0 ) {
			puts("There is not enough time to present any evidence. Drop the charges.");
			if ( ts ) putchar('\n');
			continue ;
		}
		/*
		for ( w = 0, j = 0; j <= T; ++j )
			for ( i = 0; i <= n; ++i )
				if ( calc_z(i,j) < +oo && calc_z(i,j) > w ) 
					k = i, l = j, w = calc_z(i,j);
		*/
		puts("Score  Time  Description");
		puts("-----  ----  -----------");
		for ( TT = 0; TT <= T && calc_z(n,TT) != w; ++TT );
		assert( calc_z(n,TT) == w );
		m = 0, dump(n,TT), qsort(idx,m,sizeof *idx,cmp);
		for ( i = 0; i < m; ++i ) 
			printf("%3d%7d   %s\n",score[idx[i]],tm[idx[i]],desc[idx[i]]);
		printf("\nTotal score: %u points\n",w);
		printf(" Total time: %d hours\n",TT);
		if ( ts ) putchar('\n');
	}
	return 0;
}
Any help is appreciated.

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

Re: 431 - Trial of the Millennium

Post by metaphysis » Thu Sep 20, 2018 4:31 pm

After tons of submit, I always got WA, so I turn to UVa BBS for help.
It is a classical 0-1 knapsack problem. I have considered various boundary test cases:
(1)the total allowed time equal to 0;
(2)evidences with time 0;
(3)evidences with same score and time, I choose the item which description ascii smaller;
(4)the description with additional space before the first character or after the last character(I kept it);
(5)I sorted the output first by time, and then by score, last by description ascii ascending.
Is the special judge has some bugs?
Below is my solution:

Code: Select all

// Trial of the Millennium
// UVa ID: 431
// Verdict:  Wrong Answer
// Submission Date: 2018-09-20
// UVa Run Time: 0.070s

#include <bits/stdc++.h>

using namespace std;

struct evidence
{
    int index, score, hour;
    string description;
    
    bool operator<(const evidence &data) const
    {
        if (hour != data.hour)
            return hour < data.hour;
        if (score != data.score)
            return score > data.score;
        return description < data.description;
    }
};

int main(int argc, char *argv[])
{
    string line;
    int scores[110][250], choices[110][250], n, cases;
    
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        int time_limit;
        cin >> time_limit;
        cin.ignore(256, '\n');

        vector<evidence> evidences;
        int count = 1;
        while (getline(cin, line), line.length() > 0)
        {
            if (line.length() == 0) break;
            evidence data;
            data.index = count++;
            istringstream iss(line);
            iss >> data.score >> data.hour;
            getline(iss, data.description);
            data.description.erase(data.description.begin());
            evidences.push_back(data);
        }
        
        if (cs > 1) cout << '\n';

        sort(evidences.begin(), evidences.end());
        evidence empty;
        evidences.insert(evidences.begin(), empty);

        memset(scores, 0, sizeof(scores));
        memset(choices, 0, sizeof(choices));
        n = evidences.size() - 1;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= time_limit; j++)
            {
                if (j >= evidences[i].hour && scores[i - 1][j - evidences[i].hour] + evidences[i].score > scores[i - 1][j])
                {
                    choices[i][j] = 1;
                    scores[i][j] = scores[i - 1][j - evidences[i].hour] + evidences[i].score;
                }
                else scores[i][j] = scores[i - 1][j];
            }
        
        vector<int> selected;
        int last_index = n, pre_time_limit = time_limit;
        int used_hours = 0, max_points = 0;

        while (last_index)
        {
            if (choices[last_index][pre_time_limit])
            {
                selected.push_back(last_index);
                pre_time_limit -= evidences[last_index].hour;
                used_hours += evidences[last_index].hour;
                max_points += evidences[last_index].score;
            }
            last_index--;
        }
        reverse(selected.begin(), selected.end());

        if (time_limit == 0)
        {
            max_points = 0;
            selected.clear();
            for (int i = 1; i <= n; i++)
                if (evidences[i].hour == 0)
                {
                    selected.push_back(i);
                    max_points += evidences[i].score;
                }
        }

        if (max_points == 0)
        {
            cout << "There is not enough time to present any evidence. Drop the charges.\n";
            continue;
        }

        cout << "Score  Time  Description\n";
        cout << "-----  ----  -----------\n";
        for (auto item : selected)
        {
            cout << setw(3) << right << evidences[item].score;
            cout << "    ";
            cout << setw(3) << right << evidences[item].hour;
            cout << "   ";
            cout << evidences[item].description << '\n';
        }
        cout << '\n';
        cout << "Total score: " << max_points << " points\n";
        cout << " Total time: " << used_hours << " hours\n";
    }
    
	return 0;
}

Post Reply

Return to “Volume 4 (400-499)”