Page 1 of 2
10817 - Headmaster's Headache
Posted: Mon Feb 14, 2005 9:53 pm
by Adrian Kuegel
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.
Posted: Mon Feb 14, 2005 11:58 pm
by little joey
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. */
}
Posted: Tue Feb 15, 2005 12:07 am
by Adrian Kuegel
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;
Posted: Wed Feb 16, 2005 5:18 am
by technobug
Hey there.... what was the idea behind your algorithm?
Posted: Wed Feb 16, 2005 5:28 am
by Adrian Kuegel
Memoization with table n * 4^s.
But I guess there is a better way, looking at memory consumption and runtime of other programs.
Posted: Wed Feb 16, 2005 6:30 am
by Observer
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.
Posted: Wed Feb 16, 2005 11:52 am
by ..
Adrian 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.
Mine is O(3^s), I can't see why you require 4^s, as every subject has either
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...
Posted: Wed Feb 16, 2005 1:09 pm
by Observer
Adrian probably uses 4^s because this simplifies the "setbit" procedure a bit.
And yes, the judge solution also uses two 3^s arrays
Posted: Wed Feb 16, 2005 4:26 pm
by Adrian Kuegel
Adrian probably uses 4^s because this simplifies the "setbit" procedure a bit.
Exactly. But I didn't think of using only two such arrays, although it is the standard technique to reduce memory consumption.
Posted: Thu Feb 17, 2005 10:19 am
by uzurpatorul
Out of my curiosity what is the idea behind using memoizetion?, I used dynamic programming and my solution is very similar with the classic 0-1 knapsack problem, the only difference is that I have an array of subjects instead of the weight.
Cheers,
R.
Posted: Fri Feb 18, 2005 9:05 am
by windows2k
.. wrote:Adrian 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.
Mine is O(3^s), I can't see why you require 4^s, as every subject has either
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...
Hello, my method is similar as you, but I get WA all the time.
could you give some input/output ? thx
Posted: Fri Feb 18, 2005 10:09 am
by uzurpatorul
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
10817
Posted: Sun Feb 20, 2005 8:17 pm
by technobug
Is this a max flow problem? Any other similar ones in the problem set?
Posted: Sun Feb 20, 2005 8:33 pm
by Larry
It's a DP/memo problem. Think about the search space. Good luck!
Posted: Sun Feb 20, 2005 10:28 pm
by technobug
Great.... thanks Larry, got AC with +-0.9secs
I am not an expert so everything i did in here was a challenge for me...
What I did looks like a Nth dimension knapsack, but mapping the dimensions to a simple array.... (another challenge for me)