10558 - A Brief Gerrymander

[filipek]

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]

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]

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.]

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.

[serur]

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]

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]

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