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!

## 430 - Swamp County Supervisors

**Moderator:** Board moderators

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.

### 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[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

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

*;*

curcur

*= 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]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]

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

Ami ekhono shopno dekhi...

HomePage

HomePage

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

I can't find the error with my code ....

thanks,

The input is tricky...

There is empty line in the input ...

Those who got WA should take card about it ...

studying @ ntu csie

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.
The problem was in input taking actually ..

Here is my code ... can anyone give me some suggestion ? Thanks in advance.

Code: Select all

`removed after AC`

Last edited by Kallol on Sun Dec 16, 2007 4:44 pm, edited 1 time in total.

Syed Ishtiaque Ahmed Kallol

CSE,BUET

Bangladesh

CSE,BUET

Bangladesh

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.