## 12795 - Ecology

Moderator: Board moderators

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

### Re: 12795 - Ecology

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

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

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

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

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