10817 - Headmaster's Headache

[technobug]

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]

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]

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

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.

[Gigi's Baby]

very good problem!
I like McDull too!

[L I M O N]

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

[Martin Macko]

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

[lord_burgos]

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

[Destination Goa]

lord_burgos
Please correct your forumlae... I don't see why 'S' stopped being an exponent

[Tirdad]

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]

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.