## 10558 - A Brief Gerrymander

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

Moderator: Board moderators

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:

### 10558 - A Brief Gerrymander

Hello,
I've been trying for some time to solve this problem, and i have no idea, why i get WA all the time. Is there any trick in this task? I solve it with DP, for each k and l, i find the maximum number of ridings, if you can use k avenues to divide, and the last to the north would be l avenue. Do I have to choose avenues 1 and 100 too? (i tried both versions).
Best regards,
Furippo

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

There is only simple DP. But you have to consider avenues 1 and 100 also, and remember that if you were said to divide it with 8 avenues, you have to output 8 avenues (even if the same optimal anser is for 4 )

I hope I will help you

Best regards

CYFRA

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Can anyone provide some sample test data for me to test my program? I keep getting WA even though I'm pretty sure the program is correct.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Go to Waterloo contest website at http://plg.uwaterloo.ca/~acm00
and you will find all source codes and input datas.

But be sure not to spoil your "fun" by looking over solutions.

However, after I solve problems from Waterloo contest I always check out their solutions: they are quite impressive often.
JongMan @ Yonsei

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 10558 - A Brief Gerrymander

1. Do Avenues run from South to North and Streets from West to East?
To put it simply, Avenues are vertical lines and Streets are horizontals, right?
2. "Riding" is a large rectangle we have obtained by S horizontal and A vertical cuts?

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 10558 - A Brief Gerrymander

Maybe this part of task could be helpful for those of you, who get WA
"The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries;".

thomgil
New poster
Posts: 2
Joined: Mon Jun 20, 2011 8:25 pm

### Re: 10558 - A Brief Gerrymander

Maybe this part of task could be helpful for those of you, who get WA
"The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries;".
that's a useful hint
An Overview of Mobile Phone Signal Booster
Mobile Phone Signal Booster[/url] a Solution to Poor Signal? http://gizmolord.com/mobile-phone-signa ... or-signal/