430 - Swamp County Supervisors

[tokei]

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]

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.

[obelix]

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]

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

[Jan]

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

No. I used normal 'int'.

[SRX]

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,

[SRX]

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

[Kallol]

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

[CMG]

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.