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

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

430 - Swamp County Supervisors

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 ?

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
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!

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;
int cur;
int toUse;
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
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
Contact:
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
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, studying @ ntu csie

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
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, Oh.........
The input is tricky...
There is empty line in the input ...
Those who got WA should take card about it ...
studying @ ntu csie

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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