## 269 - Counting Patterns

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

Moderator: Board moderators

zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am

### [269 ]Counting Patterns ,TLE

I got TLE in this problem ,what's the algo for it,just only burte force?
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Smart brute force, yes.
Make sure that your algorithm is fantastic enough
zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am
wat's smart burte force
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
zizi wrote:wat's smart burte force
I'm not sure how good you are at programming, but this question has a VERY VERY low submission count (70+) and only 16 people got it correct.. so unless you are really quite experienced at brute force, you shouldn't be too worried if you cannot solve it within time limit.

Anyway, "smart brute force" generally means pruning.. if you visual the paths taken by an exhaustive search, it is in the form of a tree. Pruning simply means removing parts of the tree. How and which branch to remove is the "smart" part.
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 269 - Counting Patterns

How many sequence for:

Code: Select all

1 11
2 10
3 9
4 8
5 7
6 6
7 5
8 4
9 3
10 2
11 1
I get:

1

11

30

285

1558

8221

28227

60638

61121

19586

655

Thanks.
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
This is how many sequences I get for your input:
1
11
30
285
1599
9058
32900
73558
74002
22159
657
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Thanks, Adrian, I have fixed my error!
DJY
New poster
Posts: 5
Joined: Sun Oct 12, 2003 9:24 am
Could anyone give me a hint how to solve it efficient
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I tried, but can't get below the 10 sec limit. Is there any tricks? I basically generate an unordered set of number satisfying the criterion, then try to permute them to find the equivalent classes.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I finally did enough optmizations to get it AC
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Could someone verify my I/O test ?

input:

Code: Select all

1 3
3 0
2 2
3 3
3 4
4 3
output:

Code: Select all

1
(0)

1
(0,0,0)

3
(0,0)
(1,-1)
(2,-2)

6
(0,0,0)
(1,0,-1)
(2,-1,-1)
(2,0,-2)
(3,-1,-2)
(3,0,-3)

9
(0,0,0)
(1,0,-1)
(2,-1,-1)
(2,0,-2)
(3,-1,-2)
(3,0,-3)
(4,-2,-2)
(4,-1,-3)
(4,0,-4)

30
(0,0,0,0)
(1,-1,1,-1)
(1,0,-1,0)
(1,0,0,-1)
(1,1,-1,-1)
(2,-2,2,-2)
(2,-1,0,-1)
(2,-1,1,-2)
(2,0,-2,0)
(2,0,-1,-1)
(2,0,0,-2)
(2,1,-2,-1)
(2,1,-1,-2)
(2,2,-2,-2)
(3,-3,3,-3)
(3,-2,1,-2)
(3,-2,2,-3)
(3,-1,-1,-1)
(3,-1,0,-2)
(3,-1,1,-3)
(3,0,-3,0)
(3,0,-2,-1)
(3,0,-1,-2)
(3,0,0,-3)
(3,1,-3,-1)
(3,1,-2,-2)
(3,1,-1,-3)
(3,2,-3,-2)
(3,2,-2,-3)
(3,3,-3,-3)
And the sequence for :

Code: Select all

5 5
5 4
7 3
3 7
8 3
I get

Code: Select all

483
228
2281
20
13023
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I found my bug and got AC. Anyway, i/o test of my previos post seems to be right.
It might help ones trying this problem.
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
If (2,-1,0,-1) & (2,0,-1,-1) is valid then why (2,-1,-1,0) not valid?

Can anybody tell me!
I dont understand it.
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Because (2, -1, -1, 0) is equivalent to (2, 0, -1. -1).

Code: Select all

(2, 0, -1, -1)  --rule(a)--> (0, -1, -1, 2) --rule(b)--> (2, -1, -1, 0)