10660 - Citizen attention offices

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10660 - Citizen attention offices

Post by Dominik Michniewski » Sun Jun 06, 2004 10:07 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jun 06, 2004 10:49 pm

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jun 07, 2004 5:29 pm

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

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)

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Hi:Need Help

Post by sumankar » Mon Jun 07, 2004 5:42 pm

Can someone post the minimum dist values for the
input set?I don't think I am calculating them correctly.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Tue Jun 08, 2004 4:00 pm

Hi.
Can anyone AC post some I/O... I get WA.
My program runs in O(50130*n). What can be wrong ?
Thanks.
_____________
NO sigNature

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

WA pls help

Post by Faizur » Sun Jun 13, 2004 7:38 am

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
_______________________________________________
:x :lol: :D faizur

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Jun 13, 2004 9:45 am

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: Select all

0 1 2 4 7
0 1 2 12 24
[/code]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Sun Jun 13, 2004 10:51 am

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-

Code: Select all

Accepted
pls help....
________________________________
:) :lol: :D faizur
Last edited by Faizur on Sun Jun 13, 2004 12:18 pm, edited 2 times in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jun 13, 2004 11:58 am

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]);  

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Sun Jun 13, 2004 12:15 pm

Thanx Adrian for ur help. I have actualy misunderstood the problem. Now I get AC.
Regards
____________________________________
:) :lol: :D faizur

Vegeta
New poster
Posts: 3
Joined: Wed Sep 11, 2002 7:20 pm
Contact:

Post by Vegeta » Mon Jun 28, 2004 2:56 am

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]

Vegeta
New poster
Posts: 3
Joined: Wed Sep 11, 2002 7:20 pm
Contact:

Post by Vegeta » Wed Jul 14, 2004 8:14 am

I'm still WA! :cry: :cry: :cry:

theemathas
New poster
Posts: 19
Joined: Mon Jan 07, 2013 9:30 am

Re: 10660 - Citizen Attention Offices

Post by theemathas » Fri Jan 11, 2013 4:42 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10660 - Citizen Attention Offices

Post by brianfry713 » Thu May 30, 2013 5:05 pm

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:

Code: Select all

0 2 5 15 17
Check input and AC output for thousands of problems on uDebug!

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 10660 - Citizen attention offices

Post by Lim.YuDe » Tue Jan 13, 2015 2:31 pm

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 :)

Code: Select all

Removed after AC
Last edited by Lim.YuDe on Wed Jan 14, 2015 3:49 am, edited 1 time in total.

Post Reply

Return to “Volume 106 (10600-10699)”