430 - Swamp County Supervisors

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

Moderator: Board moderators

Post Reply
tokei
New poster
Posts: 5
Joined: Tue Aug 20, 2002 7:27 am

430 - Swamp County Supervisors

Post by tokei » Mon Oct 07, 2002 4:34 pm

Hi!

I had no idea how to solve this problem efficiently....
I used DFS to solve this problem, but it seemed that my program ran too slow....

Can anyone help me to solve this problem efficiently ?

Thanks in advance!

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Jun 30, 2004 4:31 pm

I didn't solve it using a DFS; I tried to prune, but all my efforts came up fruitless. Then I used a fancier algorithm and got AC, at around 7.8 seconds. Which makes me doubt that I did it the "right" way. Of course I was horribly inefficient in my implementation, so maybe that's why.
I'm always willing to help, if you do the same.

obelix
New poster
Posts: 1
Joined: Tue Sep 21, 2004 3:42 am

430 .. How to reduce running time!

Post by obelix » Tue Sep 21, 2004 4:08 am

Hello folks,

My first post here because normally the existing posts answer all my questions.. But not this time... I'm doing this probem 'Swamp Country Supervisors'.. I've done a bit of optiminzation to the recursive function but can't manage to get it to run within the time limit ... Can somebody have a look ?
[cpp]
void solve(int c, int tot)
{

if((tot + cur[c] >= min) || c==theC-1)
{
if(tot+cur[theC-1] >= min)
num++;

return;
}

solve(c+1, tot+cur[c]);
solve(c+1,tot);

}[/cpp]

Just a quick explanation :
theC = number of elements
cur[] = the array containing the elements
c = the array index currently being considered i.e. cur[c] is being
considered
min = the minimum number of votes required
tot = the running total

One more thing .. before I call this problem, I take the element for which I want to find the number of ways, I swap it with the last element of the array, and then I sort the remaining elements...

so forexample, if array is : 6 1 2 4 3 9 7 and I am interested in '4' , then before calling solve, i swap 4 with 7 and sort the remaining elements .. so the array looks like = 1 2 3 6 7 9 4

I keep on getting TLE.. Please suggest how to optimize the above function!

.. In case you want to look at the complete code

[cpp]#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

char s1[1000];
int cur[27];
int toUse[27];
int min;
int num;
int theC=0;


void solve(int c, int tot)
{

if((tot + cur[c] >= min) || c==theC-1)
{
if(tot+cur[theC-1] >= min)
num++;

return;
}

solve(c+1, tot+cur[c]);
solve(c+1,tot);

}

void main()
{
ifstream fin("input.txt");


while(fin.getline(s1,1000,'\n'))
{
char * token = strtok(s1," \n");
min = atoi(token);
theC=0;

token = strtok(NULL," \n");
while(token!=NULL)
{
cur[theC++] = atoi(token);
token = strtok(NULL," \n");
}

int i,j,k, temp;


// maintain an original copy of the array
for(i=0; i<theC; i++)
toUse = cur;

// for every single element in the array
for(i=0; i<theC; i++)
{

// get the original copy of the array
for(j=0; j<theC; j++)
cur[j] = toUse[j];

// swap the element ith element with the last element
temp = cur;
cur = cur[theC-1];
cur[theC-1] = temp;

// sort all the elements except last one
for(k=0; k<theC-1; k++)
{
for(j=k+1; j<theC-1; j++)
{
if(cur[j] < cur[k])
{
temp = cur[j];
cur[j] = cur[k];
cur[k] = temp;
}
}
}



num=0; // the number of ways it can affect the vote
solve(0,0); // the first argument is the index of the array which it should consider next
// the second argument is the running total
cout << num << " ";

}


cout << endl;
}



}[/cpp]

tsengct
New poster
Posts: 5
Joined: Mon Aug 27, 2007 7:11 am

Post by tsengct » Wed Aug 29, 2007 4:33 am

Does the input of problem 430 contain numbers that are larger than 2^32?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 29, 2007 3:17 pm

tsengct wrote:Does the input of problem 430 contain numbers that are larger than 2^32?
No. I used normal 'int'.
Ami ekhono shopno dekhi...
HomePage

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sat Sep 08, 2007 4:50 pm

Jan wrote:
tsengct wrote:Does the input of problem 430 contain numbers that are larger than 2^32?
No. I used normal 'int'.
Can anyone who got acc give me some test cases?
I can't find the error with my code ....

thanks, :D
studying @ ntu csie

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sat Sep 08, 2007 7:12 pm

SRX wrote:
Jan wrote:
tsengct wrote:Does the input of problem 430 contain numbers that are larger than 2^32?
No. I used normal 'int'.
Can anyone who got acc give me some test cases?
I can't find the error with my code ....

thanks, :D
Oh.........
The input is tricky...
There is empty line in the input ...
Those who got WA should take card about it ...
studying @ ntu csie

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Dec 15, 2007 2:22 pm

I tried with Dynamic Programming .. I dont know why I am getting RTE .. Another thing is , what is the maximum value of the votes ??
Here is my code ... can anyone give me some suggestion ? Thanks in advance.

Code: Select all

removed after AC
The problem was in input taking actually ..
Last edited by Kallol on Sun Dec 16, 2007 4:44 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG » Sun Dec 16, 2007 12:07 am

There are two places in your knapsack function that give RTE.

1. The size of votes can be larger than 10000, which gives out of bounds error for the memo array.

2. for(i=amount-1;i>=(amount-votes[left]);i--) , this causes another out of bounds error for the memo array when amount-votes[left] is less than 0.

3. Another possible place for RTE is when there is only one bog in the input, but I dont think there is an input case with only 1 bog.

Post Reply

Return to “Volume 4 (400-499)”