10817 - Headmaster's Headache

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

[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. */
      }

[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;

[technobug]

Hey there.... what was the idea behind your algorithm?

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

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

[..]

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

[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

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

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

[windows2k]

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

[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

[technobug]

Is this a max flow problem? Any other similar ones in the problem set?

[Larry]

It's a DP/memo problem. Think about the search space. Good luck!

[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)