10660  Citizen attention offices
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
10660  Citizen attention offices
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
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
Last edited by Dominik Michniewski on Wed Jul 14, 2004 8:46 am, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I would rather call it brute force than backtracking.Is there any better algorithm to solve this problem instead of using 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 nonempty squares) what the costs are.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Thanks for reply ... I think too, that bruteforce (backtracking) is the only possibilities, but I thought , that I was wrong
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
Hi:Need Help
Can someone post the minimum dist values for the
input set?I don't think I am calculating them correctly.
input set?I don't think I am calculating them correctly.

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
WA pls help
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
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
Try this IO.
Input
Output
[/code]
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
Code: Select all
0 1 2 4 7
0 1 2 12 24
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
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
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
Code: Select all
Accepted
________________________________
faizur
Last edited by Faizur on Sun Jun 13, 2004 12:18 pm, edited 2 times in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
you should not count the distance to all the offices, only to the nearest office.
So this part of your code is wrong:
So this part of your code is wrong:
Code: Select all
value+=((labs(i/5n/5)+labs(i%5n%5))*sqr[n/5][n%5]);
value+=((labs(j/5n/5)+labs(j%5n%5))*sqr[n/5][n%5]);
value+=((labs(k/5n/5)+labs(k%5n%5))*sqr[n/5][n%5]);
value+=((labs(l/5n/5)+labs(l%5n%5))*sqr[n/5][n%5]);
value+=((labs(m/5n/5)+labs(m%5n%5))*sqr[n/5][n%5]);
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]
[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]

 New poster
 Posts: 19
 Joined: Mon Jan 07, 2013 9:30 am
Re: 10660  Citizen Attention Offices
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!
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
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)
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

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10660  Citizen Attention Offices
Input:AC output:
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
Code: Select all
0 2 5 15 17
Check input and AC output for thousands of problems on uDebug!
Re: 10660  Citizen attention offices
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
I'm still getting WA.
If anybody can tell me what is wrong with my code I'd be really grateful
Code: Select all
Removed after AC
Last edited by Lim.YuDe on Wed Jan 14, 2015 3:49 am, edited 1 time in total.