269 - Counting Patterns

[zizi]

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

[Adrian Kuegel]

Smart brute force, yes.

Make sure that your algorithm is fantastic enough

[zizi]

wat's smart burte force

[junbin]

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]

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]

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

[Larry]

Thanks, Adrian, I have fixed my error!

[DJY]

Could anyone give me a hint how to solve it efficient

[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]

I finally did enough optmizations to get it AC

[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]

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]

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]

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)