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

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

Post by technobug » Mon Feb 21, 2005 5:17 am

.. wrote: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... :)
O(n*3^s) here...... but it gets faster and with less memory as it goes bottom up using just one table size (3 ^ s). Just a little bit of memory needed...

But then, if you use the (3^s) * 2 table, you can always use a trick a friend of mine tought me:

Code: Select all

int actual = 0;
int other = 1;
for(i -> n) {
  // do your stuff, reading from "actual" and writing to "other"
  // after everything is done, change their values
  actual = !actual;
  other = !other;
}
// at the end, you have the result on table 'ACTUAL'
So you dont have to copy the data from one to the other everytime

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sun Mar 06, 2005 5:38 pm

uzurpatorul wrote:out

58000
154000
35000
Thanks for the sample i/o. It confirmed what I thought, I've misunderstood the problem. I thought that there had to be at least one serving teacher and at least one applicant for each subject. Since there is no serving teacher for subject 4 in the first input above, my program finds no solution. But why is the answer 58000, and not 56000 (using 1000 1 2, 5000 1 2 3 4 and 50000 3 4)? What is the difference between a serving teacher and an applicant in this problem? Is the difference above due to the fact that serving teachers always must be chosen? I hope someone can explain...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sun Mar 06, 2005 6:28 pm

It seems the thinking needed to write the above post helped me a lot! Of couse the serving teachers are employed at the school and they are always chosen 8) . I just got accepted. Btw, I use only one 3^n table, it's possible when reversing the inner loop (counting down instead of up) in the DP.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Mon Mar 07, 2005 10:20 am

With O(n*4^s) DP I got TL during the contest. It's better to index back and forth all 3^s states into 4^s map.
To be the best you must become the best!

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Mon May 09, 2005 8:24 pm

very good problem!
I like McDull too! :lol:

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10817 : Wt's the Output ???

Post by L I M O N » Sun Sep 18, 2005 4:37 pm

pls anyone gives me the output :

input :
4 2 2
10 1 2 3 4
10 1 2 3 4
1 1 2 3 4
1 1 2 3 4
0 0 0


my program outputs : 20

is it right one ??

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10817 : Wt's the Output ???

Post by Martin Macko » Fri Sep 23, 2005 2:50 am

My AC gives the same output. (20)

You may find the topics http://online-judge.uva.es/board/viewtopic.php?t=7582 and http://online-judge.uva.es/board/viewtopic.php?t=7533 useful.

good luck

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Thu Feb 09, 2006 1:38 am

Destination Goa wrote:With O(n*4^s) DP I got TL during the contest. It's better to index back and forth all 3^s states into 4^s map.
My algorithm use DP whit O( N * ( 2^(2*S) ))


Code: Select all

int dp[101][(1<<16) + 1];
use masc 8)
Last edited by lord_burgos on Sun Feb 12, 2006 5:35 am, edited 1 time in total.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Thu Feb 09, 2006 2:46 am

lord_burgos
Please correct your forumlae... I don't see why 'S' stopped being an exponent :)
To be the best you must become the best!

Tirdad
New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:

Post by Tirdad » Tue Oct 10, 2006 6:09 pm

Hi,
I've got TLE on this problem!
help me plz.
thanks in advance

Code: Select all

#include <iostream>
#include <memory>
#include <assert.h>
using namespace std;
int dp[100000];
bool applicant[100][8];
int appVal[100];
int M,N,S;
int count ;
void dfs(int i,int state,int soFarVal)
{
	if ( state > ( (1<<(2*S)) - 1 ) || state >= 100000) // looking for sooti
	{
		state =  0 ;
		state = 1/state ;
	} 
	if ( state ==( (1<<(2*S)) - 1 ))//reach end State
	{
		if((dp[state] >= soFarVal && soFarVal != 0) || dp[state] == 0) // set the so
			dp[state] = soFarVal;
		return ;
	}
	if ( i == N )
			return;
	if(dp[state] != 0 && soFarVal != 0)
	{
		if(dp[state] >= soFarVal)
			dp[state] = soFarVal;
		else
			return ;
	}
	else
		if(soFarVal != 0)
		dp[state]= soFarVal;

	int newState = state;
	for(int j=0;j<S;j++)
	{
		if(!applicant[i][j])
			continue;
		if(!(newState & (1 << (2*j))) ) 
			newState |= (1<<(2*j));
		else
			newState |= (1<<(2*j + 1));
	}
		
		dfs(i+1,state,soFarVal);
		if(state !=newState)
			dfs(i+1,newState,soFarVal + appVal[i]);
}
int main()
{
	
	while(cin >> S)
	{
		if ( !S ) break;
		cin>>M>>N;
		count = 0 ;
		//memset(dp,0,sizeof dp);
		for ( int i=0 ; i<(1<<2*S) ; i++ ) dp [i] = 0 ;
		for(int i=0;i<100;i++)
			for ( int j=0 ; j<S ; j++ )
				applicant [i][j] = 0 ;
		int soFarCost=0,temp;
		int  state = 0;
		bool flag;
		for(int i =0 ;i<M;i++)
		{
			cin>>temp;
			soFarCost+=temp;
			while(cin.peek()!= '\n')
			{
				cin.get() ;
				cin>>temp;
				temp--;
				if(!(state&(1<<(2*temp))))
				state |=(1<<(2*temp));
				else
					state |=(1<<(2*temp + 1));
			}
		}
		for(int i =0 ;i<N;i++)
		{
			cin>>appVal[i];
			
			while(cin.peek()!= '\n')
			{
				cin.get();
				cin>>temp;
				applicant[i][temp-1] = true;
			}
			flag = true;
			for(int course=0;course<S;course++)
			{
				if(applicant[i][course]&& (!( state & (1 <<(2*course)) ) || !(state&(1<<(2*course + 1)))))
					flag = false;
			}
			if(flag)
			{
				for(int course=0;course<S;course++)
					applicant[i][course] = false;
				N--;
				i--;
			}
		}
		dfs(0,state,0);
		int bestVal = dp[((1<<(2*S))-1)];
		cout<<bestVal + soFarCost<<endl;
		
	}
	
	return 0;
}

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

Re: 10817 - Headmaster's Headache

Post by pdwd » Thu Aug 26, 2010 7:34 am

Can somebody explain me how to get:
a) time complexity O(n*4^s)
b) time complexity O(n*3^s)

I have O(n*s*2^(2s)) for each masc 'M' I must compute the set 'S' for actual applicant than I can substract from this masc min(dp[M], dp[M-S]). I cannot compute 'S' at the begining of processing actual applicant because it depends on masc 'M' wheter in some subjects applicant is a first or second teacher.

Post Reply

Return to “Volume 108 (10800-10899)”