12795 - Ecology

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

Moderator: Board moderators

Post Reply
nada_elnokaly
New poster
Posts: 3
Joined: Thu Oct 23, 2014 12:29 am

Re: 12795 - Ecology

Post by nada_elnokaly » Tue Nov 11, 2014 7:14 am

do any one have an idea how can we solve this problem within the time limit !?

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

Re: 12795 - Ecology

Post by brianfry713 » Tue Nov 18, 2014 4:51 am

My code gets AC in 57 seconds.

I first precalculate all possible shapes and their sizes for 1 <= M <= 10. For M = 10 there are 36,446 shapes. That takes less than a second on my machine. I use a struct with a set<pair<int, int> > of points and the height and width of the shape.
I then start reading the input and test each shape on each location it fits.
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

Re: 12795 - Ecology

Post by LCSFC » Wed Feb 04, 2015 4:39 pm

Please help me with this problem. Are you sure there is only about 36000 shapes for M=10? I wanna test my algorithm, it gives 4900 shapes for M=2, 14404 shapes for M=3...is that right?

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

Re: 12795 - Ecology

Post by brianfry713 » Wed Feb 04, 2015 8:31 pm

M, Unique shapes
1, 1
2, 2
3, 6
4, 19
5, 63
6, 216
7, 760
8, 2725
9, 9910
10, 36446
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

Re: 12795 - Ecology

Post by LCSFC » Thu Feb 05, 2015 3:33 pm

Thank you very much! With your results i could find my mistakes and solve it. Thanks!

Post Reply

Return to “Volume 127 (12700-12799)”