10817 - Headmaster's Headache
Moderator: Board moderators
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
10817 - Headmaster's Headache
I think there is a mistake in the judge input. It contains an employed teacher description where a teached subject appears more than once. And if this is valid, then at least the judge output for this case is wrong, because I got WA when I counted the subject only once, and accepted when I counted it as often as it appeared in the list.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Hmm. That's strange, because I count the subject only once, and get accepted:
Code: Select all
while(1){
scanf("%d%d%d\n",&subjects,&serving,&applicants);
if(subjects==0) break;
for(i=0;i<serving+applicants;i++){
scanf("%d",&salary[i]);
fgets(line,sizeof(line),stdin);
for(j=0;j<subjects;j++) teaches[i][j]=0;
for(j=0;line[j];j++) if(isdigit(line[j])) teaches[i][line[j]-'1']=1;
}
/* etc. */
}
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Ok, right, it was my fault. I changed one part in my code and forgot to change another part:
Code: Select all
num--;
if (!used[num])
bits = setbit(bits,1<<(2*num));
used[num-1] = 1;
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Memoization with table n * 4^s.
But I guess there is a better way, looking at memory consumption and runtime of other programs.
But I guess there is a better way, looking at memory consumption and runtime of other programs.
Last edited by Adrian Kuegel on Wed Feb 16, 2005 6:47 am, edited 1 time in total.
Memoization is good. Of course the table size can be reduced. There are many other possible appoaches, e.g. dynamic programming.
FYI, the problem idea is taken from "Linear Optimization in Applications", a book about linear programming.
FYI, the problem idea is taken from "Linear Optimization in Applications", a book about linear programming.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Mine is O(3^s), I can't see why you require 4^s, as every subject has eitherAdrian Kuegel wrote:Memoization with table n * 4^s.
But I guess there is a better way, looking at memory consumption and runtime of other programs.
0, 1, 2+ teachers. My algorithm has runtime O(n * 3^s). As I want to reduce the memory usage, I use 2 pieces of 3^s memory, on start of very loop I copy one to another(I guess you know what I say...
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
Adrian probably uses 4^s because this simplifies the "setbit" procedure a bit.
And yes, the judge solution also uses two 3^s arrays
And yes, the judge solution also uses two 3^s arrays
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- New poster
- Posts: 5
- Joined: Fri Oct 22, 2004 10:21 am
Hello, my method is similar as you, but I get WA all the time... wrote:Mine is O(3^s), I can't see why you require 4^s, as every subject has eitherAdrian Kuegel wrote:Memoization with table n * 4^s.
But I guess there is a better way, looking at memory consumption and runtime of other programs.
0, 1, 2+ teachers. My algorithm has runtime O(n * 3^s). As I want to reduce the memory usage, I use 2 pieces of 3^s memory, on start of very loop I copy one to another(I guess you know what I say...
could you give some input/output ? thx
-
- New poster
- Posts: 5
- Joined: Fri Oct 22, 2004 10:21 am
in
4 3 10
1000 1 2
1000 3
1000 1
5000 1 2 3 4
50000 3
50000 4
50000 3 4
50000 1
50000 1
50000 2
50000 1
50000 2
50000 1
8 4 20
1000 1
1000 2
1000 3
1000 2
10000 1
20000 2
40000 3 4
50000 1 2
50000 1 4
50000 1
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 5 7 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 6 8
50000 1 5 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 2 3 4 5 6 7 8
2 2 5
10000 1
20000 2
30000 1 2
40000 1 2
10000 1
10000 2
5000 1 2
0 0 0
============
out
58000
154000
35000
4 3 10
1000 1 2
1000 3
1000 1
5000 1 2 3 4
50000 3
50000 4
50000 3 4
50000 1
50000 1
50000 2
50000 1
50000 2
50000 1
8 4 20
1000 1
1000 2
1000 3
1000 2
10000 1
20000 2
40000 3 4
50000 1 2
50000 1 4
50000 1
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 5 7 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 6 8
50000 1 5 3 4
50000 1 2 3 4
50000 1 2 3 4
50000 1 2 3 4 5 6 7 8
2 2 5
10000 1
20000 2
30000 1 2
40000 1 2
10000 1
10000 2
5000 1 2
0 0 0
============
out
58000
154000
35000
10817
Is this a max flow problem? Any other similar ones in the problem set?
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
It's a DP/memo problem. Think about the search space. Good luck!
Check out http://www.algorithmist.com !