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

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

[269 ]Counting Patterns ,TLE

Post by zizi »

I got TLE in this problem ,what's the algo for it,just only burte force?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Smart brute force, yes.
Make sure that your algorithm is fantastic enough
:wink:

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

Post by zizi »

wat's smart burte force :)

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

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

Post by Larry »

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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:

Post by Larry »

Thanks, Adrian, I have fixed my error!

DJY
New poster
Posts: 5
Joined: Sun Oct 12, 2003 9:24 am

Post by DJY »

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:

Post by sclo »

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:

Post by sclo »

I finally did enough optmizations to get it AC :D

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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
Thanks in advance.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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

Post by asif_rahman0 »

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

Post by rio »

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)

Post Reply

Return to “Volume 2 (200-299)”