Page **1** of **2**

### 10660 - Citizen attention offices

Posted: **Sun Jun 06, 2004 10:07 pm**

by **Dominik Michniewski**

I have to ask

Is there any better algorithm to solve this problem instead of using backtracking ?

After contest I discovered, that office could be placed not only in square, where some people live, but in empty square too (!!). So could anyone tell me, how can I speed up backtracking for this problem (if doesn't exist any other method

) ?

Best regards

DM

Posted: **Sun Jun 06, 2004 10:49 pm**

by **Adrian Kuegel**

Is there any better algorithm to solve this problem instead of using backtracking ?

I would rather call it brute force than backtracking.

But I think there is no other algorithm than the naive one, trying all possibilites. But you can see that there are only (25 over 5) = 53130 possibilities, and for each possibility you can check in O(n) (where n is the number of non-empty squares) what the costs are.

Posted: **Mon Jun 07, 2004 5:29 pm**

by **Dominik Michniewski**

Thanks for reply ... I think too, that brute-force (backtracking) is the only possibilities, but I thought , that I was wrong

Best regards

DM

### Hi:Need Help

Posted: **Mon Jun 07, 2004 5:42 pm**

by **sumankar**

Can someone post the minimum dist values for the

input set?I don't think I am calculating them correctly.

Posted: **Tue Jun 08, 2004 4:00 pm**

by **Farid Ahmadov**

Hi.

Can anyone AC post some I/O... I get WA.

My program runs in O(50130*n). What can be wrong ?

Thanks.

### WA pls help

Posted: **Sun Jun 13, 2004 7:38 am**

by **Faizur**

Hi,

I also use simple bruteforce. trying to put the offices for all possible combinations .But i m keep getting wrong answer. Some one can help me giving some AC Sample I/O or some hints. Thanx in advance.

Regards

_______________________________________________

faizur

Posted: **Sun Jun 13, 2004 9:45 am**

by **Eduard**

Try this IO.

Input
Code: Select all

```
2
5
0 0 20
0 1 25
0 2 30
0 4 40
1 2 20
3
0 0 5
4 4 5
2 2 3
```

Output
[/code]

Posted: **Sun Jun 13, 2004 10:51 am**

by **Faizur**

Hello Eduard

Thanx for ur sample I/O. But my code give the output as yours.I dont know why i get WA.Here is my code-

pls help....

________________________________

faizur

Posted: **Sun Jun 13, 2004 11:58 am**

by **Adrian Kuegel**

you should not count the distance to all the offices, only to the nearest office.

So this part of your code is wrong:

Code: Select all

```
value+=((labs(i/5-n/5)+labs(i%5-n%5))*sqr[n/5][n%5]);
value+=((labs(j/5-n/5)+labs(j%5-n%5))*sqr[n/5][n%5]);
value+=((labs(k/5-n/5)+labs(k%5-n%5))*sqr[n/5][n%5]);
value+=((labs(l/5-n/5)+labs(l%5-n%5))*sqr[n/5][n%5]);
value+=((labs(m/5-n/5)+labs(m%5-n%5))*sqr[n/5][n%5]);
```

Posted: **Sun Jun 13, 2004 12:15 pm**

by **Faizur**

Thanx Adrian for ur help. I have actualy misunderstood the problem. Now I get AC.

Regards

____________________________________

faizur

Posted: **Mon Jun 28, 2004 2:56 am**

by **Vegeta**

I am receiving WA too. I test my code with the inputs and its OK. Here's my code:

[c]#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int n, z, i, j, x, y, v;

int level;

int mat[25];

int pos[5], resp[5];

int min_total, min_cada, min_temp;

void Testa()

{

min_temp = 0;

for (i = 0; i < 25; i++)

if (mat* > 0)*

{

min_cada = 1e9;

for (j = 0; j < 5; j++)

{

v = mat* * (abs(pos[j] / 5 - i / 5) + abs(pos[j] % 5 - i % 5));*

if (v < min_cada)

min_cada = v;

}

min_temp += min_cada;

}

if (min_temp < min_total)

{

min_total = min_temp;

memcpy(resp, pos, sizeof(pos));

}

}

void Back(int limit)

{

int i;

if (level == 5)

Testa();

else

for (i = 4 - level; i < limit; i++)

{

pos[level++] = i;

Back(i);

level--;

}

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("10660.in", "rb", stdin);

#endif

scanf("%d\n", &z);

while (z--)

{

scanf("%d\n", &n);

memset(mat, 0, sizeof(mat));

for (i = 0; i < n; i++)

{

scanf("%d %d %d\n", &x, &y, &v);

mat[x * 5 + y] = v;

}

min_total = 1e9;

level = 0;

Back(25);

for (i = 4; i >= 0; i--)

{

if (i != 4) printf(" ");

printf("%d", resp*);*

}

printf("\n");

}

return 0;

}

[/c]

Posted: **Wed Jul 14, 2004 8:14 am**

by **Vegeta**

### Re: 10660 - Citizen Attention Offices

Posted: **Fri Jan 11, 2013 4:42 am**

by **theemathas**

I also have a problem with this one, but it's NOT OK on the example test cases.

currently no idea on what is the problem

anyone please point out the bug!

Code: Select all

```
deleted after AC
(found bug at i/o)
```

on the sample test cases my program outputs

0 1 2 3 12

0 1 4 20 24

0 6 12 18 24

1 7 14 16 22

instead of

0 1 2 3 12

0 1 4 20 24

0 6 12 18 24

5 7 8 14 22

### Re: 10660 - Citizen Attention Offices

Posted: **Thu May 30, 2013 5:05 pm**

by **brianfry713**

Input:

Code: Select all

```
1
10
0 0 1
0 2 1
1 0 1
1 2 1
2 0 1
2 2 1
3 0 1
3 2 1
4 0 1
4 2 1
```

AC output:

### Re: 10660 - Citizen attention offices

Posted: **Tue Jan 13, 2015 2:31 pm**

by **Lim.YuDe**

Hi, I've looked at all of the posts and I've tried all of the input/output posted + more (and checked with uDebug to see if input/output matches), but to no avail.

I'm still getting WA.

If anybody can tell me what is wrong with my code I'd be really grateful