OJ Board

Posted: **Fri Feb 06, 2004 4:40 pm**

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

Posted: **Fri Feb 06, 2004 5:10 pm**

Smart brute force, yes.

Make sure that your algorithm is fantastic enough

Posted: **Sat Feb 07, 2004 4:54 am**

wat's smart burte force

Posted: **Sat Feb 07, 2004 6:41 pm**

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.

Posted: **Tue May 18, 2004 11:37 pm**

How many sequence for:

Code: Select all

I get:

1

11

30

285

1558

8221

28227

60638

61121

19586

655

Thanks.

Posted: **Tue May 18, 2004 11:49 pm**

This is how many sequences I get for your input:
1
11
30
285
1599
9058
32900
73558
74002
22159
657

Posted: **Wed May 19, 2004 12:22 am**

Thanks, Adrian, I have fixed my error!

Posted: **Tue Jul 06, 2004 5:53 pm**

Could anyone give me a hint how to solve it efficient

Posted: **Tue Jul 04, 2006 11:09 am**

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.

Posted: **Mon Nov 20, 2006 5:08 am**

I finally did enough optmizations to get it AC

Posted: **Sat Dec 02, 2006 7:13 pm**

Could someone verify my I/O test ?

input:

Code: Select all

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

I get

Code: Select all

Thanks in advance.

Posted: **Mon Dec 04, 2006 3:58 pm**

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.

Posted: **Fri Apr 06, 2007 10:57 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.

Posted: **Sat Apr 07, 2007 4:10 am**

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)

OJ Board

269 - Counting Patterns

[269 ]Counting Patterns ,TLE

269 - Counting Patterns