10817 - Headmaster's Headache

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10817 - Headmaster's Headache

Post by Adrian Kuegel » Mon Feb 14, 2005 9:53 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Feb 14, 2005 11:58 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. */
      }

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 15, 2005 12:07 am

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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Feb 16, 2005 5:18 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Feb 16, 2005 5:28 am

Memoization with table n * 4^s.
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Feb 16, 2005 6:30 am

Memoization is good. Of course the table size can be reduced. There are many other possible appoaches, e.g. dynamic programming. :wink:

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Wed Feb 16, 2005 11:52 am

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Feb 16, 2005 1:09 pm

Adrian probably uses 4^s because this simplifies the "setbit" procedure a bit.

And yes, the judge solution also uses two 3^s arrays :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Feb 16, 2005 4:26 pm

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
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am

Post by uzurpatorul » Thu Feb 17, 2005 10:19 am

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Fri Feb 18, 2005 9:05 am

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

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am

Post by uzurpatorul » Fri Feb 18, 2005 10:09 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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

10817

Post by technobug » Sun Feb 20, 2005 8:17 pm

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Feb 20, 2005 8:33 pm

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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sun Feb 20, 2005 10:28 pm

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)

Post Reply

Return to “Volume 108 (10800-10899)”