Bài I mình làm quy hoạch động
O(log2(10^9)*36^3+200*log2(10^9)*36^2)
mà nộp ko kịp :\

Bạn có thể nói rõ thuật toán được không ?

Mình cùng team với s_dragon_hk9.
Bài I mình làm thế này:

Mình đánh số các trạng thái trên 1 cột (10 ô). Như vậy có tất cả 36 trạng thái.

a[i][j] = 1 nếu cột có trạng thái i có thể liền kề cột có trạng thái j, = 0 nếu ngược lại.

g[i][j][k] là số cách xếp cờ lên bảng 2^i * 10, sao cho cột cuối cùng có tt k, và cột TRƯỚC cột đầu tiên có trạng thái j

• g[0][j][k] = a[j][k] với mọi j,k
• g[i][j][k] = tổng { g[i-1][j][x] * g[i-1][x][k] }, với x: 1..36

Từ bảng n*10 đã cho, mình xếp thoải mái vào cột 1, n-1 cột còn lại mình chia thành các bảng con có kích thước 1, 2, 4, 8, 16,... Ví dụ: 7 = 2^0 + 2^1 + 2^2 --> mình có v[1]=0, v[2]=1, v[3]=2.

gọi f[i][j] là số cách xếp cờ vào i bảng con đầu, sao cho cột cuối cùng có tt j

• f[0][j] = 1 với mọi j
• f[i][j] = tổng { f[i-1][k] * g [v[i]][k][j] }, với k: 1..36

Kết quả = tổng { f[m][j] }, với m là số bảng con chia ra được, j: 1..36

-----------------------------------------------------

Bạn nào có cách khác thì share với nhek :)

Mình cũng làm tương tự thế này, chỉ khác là thay vì tính các bảng 2^i thì mình đẻ ma trận kề xong lũy thừa nó với N-1 rồi nhân với ma trận 36x1 toàn số 1 :))) đpt là O(T * 36^3 * log(N)).

Về bản chất thì bài toán này chỉ là đếm số đường đi khác nhau qua đúng N đỉnh trên đồ thị, cho nên làm cách nào cũng ổn cả ;)

Đã hết ngày rồi sao vẫn chưa có bảng rank nhỉ :D

em thấy cách làm team a khá phức tạp, e xin chia sẻ cách xây dựng mảng nhân ma trận của team e:

vẫn tính ra số cách xếp trên một cột là 36

rồi so sánh hai cách xếp i và j với nhau, nếu thỏa mãn không thể ăn dc thì đặt f[i][j]=1, ngược lại f[i][j]=0;

nhân ma trận 36*36, rồi cuối cùng nhân với ma trận ban đầu tmp[1...36][1]=1

Cho mình hỏi bài J làm như nào vậy :D

Bài này với N = 3 thì là 1 bài toán khá cổ điển. Mà mình không tìm đc nguồn nào giải bài N tổng quát :(

Edit: Sau 1 hồi tìm kiếm, cuối cùng cũng mò ra đc kết quả ở đây -_-. Kết quả = 1 - tích( k / (Fibonacci(k+2) - 1), k = 2..N)

đơn giản vậy :o (y)

Rank tạm thời đây a :)

RankNameSolvedTime    A        B        C        D        E        F        G        H        I        J        K        L    Total att/solv

1Primal Spirits96491/102/--4/670/--2/1191/--1/1602/281/1061/41/231/5217/9

2BYTE96981/11/--1/861/2903/1193/--1/621/111/450/--1/171/2715/9

3Danang Never Over97461/21/101/370/--2/2140/--4/2161/281/1370/--1/191/6313/9

4OSU98171/52/--6/303/2253/1371/--1/931/371/1052/--1/341/7123/9

53Animals98942/131/--2/620/--1/516/--3/2461/91/1861/1911/61/5020/9

6Hitler910602/201/412/990/--1/1590/--2/2192/172/2840/--1/861/9514/9

7PTIT.POSTMEN912511/141/526/1360/--8/2060/--1/1054/682/1862/--2/731/9128/9

8no name YET85661/74/--5/620/--2/888/--3/922/121/801/--1/461/5929/8

9MEGABYTE87061/31/--5/710/--1/1591/--1/1311/151/1120/--2/271/8815/8

10PSA87111/92/--1/320/--2/1135/--6/2471/242/981/--1/171/9123/8

11Try Hard88161/61/--1/110/--1/1262/--1/1005/1622/2060/--2/271/7817/8

12KILOBYTE88861/111/--5/1620/--2/1370/--2/2471/191/1022/--1/431/6517/8

13BIT88991/53/--10/1120/--2/1802/--2/1601/211/1692/--1/171/11526/8

14BK.Cepheus89751/81/--5/540/--2/2152/--7/2281/301/1270/--2/421/9123/8

15BKHT811031/151/--4/1100/--2/2210/--1/2861/311/2000/--1/451/13513/8

16DOTA812722/81/--8/1780/--4/2400/--1/1168/1133/2760/--2/581/8330/8

17BK.Alpha813061/81/--7/1610/--3/2311/--1/1742/422/2100/--3/521/22822/8

18WORD813961/90/--2/1150/--2/2780/--1/2235/911/1830/--3/478/23023/8

19HCMUS - Yolo814111/371/--3/750/--4/1930/--2/2483/2133/2970/--1/621/10619/8

20BKC814411/143/--11/1630/--2/2040/--1/1935/1094/2740/--1/731/11129/8

21Budweiser77591/43/--8/1600/--1/1980/--1/1861/203/--0/--1/182/5321/7

22BRONTOBYTE77762/112/--1/810/--8/--0/--1/2841/341/2210/--1/251/10018/7

23HCMUS - Penalty78351/364/--2/730/--2/610/--0/--3/857/1681/--1/533/15924/7

24GIGABYTE79061/81/--11/2720/--3/1093/--4/1671/182/--0/--1/271/4528/7

25CS79542/562/--5/2180/--0/--2/--1/1341/1901/1000/--1/771/7916/7

26HCMUS - Team 879631/401/--4/1590/--1/1590/--2/2382/1110/--0/--1/992/3714/7

27Doltish Blockheads711531/32/--4/870/--4/2040/--0/--3/1644/2960/--1/581/12120/7

28MTA_LS65301/151/--1/990/--7/--0/--3/1671/680/--0/--1/551/8616/6

29PTIT.INCEPTION67021/204/7511/1600/--3/--0/--0/--1/1600/--0/--1/422/12523/6

30PTIT.PENDING67351/81/566/1790/--3/--0/--0/--6/2070/--0/--1/531/11219/6

31FIFA67541/70/--7/1600/--1/2510/--1/1162/780/--0/--2/225/--19/6

32BK5969571/101/--9/2670/--3/2030/--0/--3/700/--0/--1/562/13120/6

33BKX69731/181/--4/2970/--2/2162/--0/--1/530/--0/--2/812/18815/6

34ChiChj69811/72/--7/1050/--4/2111/--0/--4/810/--0/--5/962/16126/6

35FireFox611402/104/--6/2070/--1/2400/--0/--7/1940/--0/--3/832/12625/6

36GEOPBYTE612623/330/--13/2180/--0/--0/--0/--4/1963/2590/--1/472/12926/6

37PSA.HAT612821/161/--6/1070/--4/2660/--0/--2/2370/--0/--5/1671/22920/6

38EPU-BNK53121/31/--2/320/--2/--0/--0/--3/641/--0/--3/561/7714/5

39HCMUS - Team 956141/392/--2/610/--3/--0/--0/--10/1650/--0/--1/395/21024/5

40HUBT King Kong56631/80/--7/2050/--0/--0/--1/1751/--0/--0/--2/231/11213/5

41Danang Ama56802/141/--3/1740/--0/--2/--0/--2/1030/--0/--2/802/20914/5

42FTU Knights157071/120/--3/--0/--1/--0/--0/--3/881/2910/--1/1621/13411/5

43LIST_UTC57122/141/--10/--0/--3/1310/--1/2272/--0/--0/--2/961/16422/5

44Su Pham DN 157411/141/1401/770/--6/--0/--0/--1/--0/--0/--2/1375/27317/5

45Danang Pro57582/72/--6/1730/--0/--0/--0/--4/941/--0/--2/464/21821/5

46PSA.New_wind57681/193/--3/1890/--1/--0/--0/--4/1780/--0/--1/915/11118/5

47PSU #158641/322/--2/1170/--2/--0/--0/--2/2530/--0/--2/1792/20313/5

48ZETTABYTE59791/110/--11/2720/--0/--11/--0/--2/770/--0/--1/2294/25030/5

49Su Pham DN 259913/632/853/2890/--9/--0/--0/--0/--0/--0/--4/2424/19225/5

50EXABYTE510971/261/--12/1750/--1/--0/--0/--12/2930/--0/--1/433/16031/5

51HCMUS - PTNK101541961/422/--0/--0/--0/--0/--0/--1/521/--0/--1/431/597/4

52YOTTABYTE43262/285/--8/--0/--0/--0/--1/--1/447/--0/--1/942/12027/4

53Black Red43601/140/--11/--0/--0/--0/--0/--1/650/--0/--2/355/16620/4

54FTU Knights244741/120/--11/--0/--0/--0/--0/--2/872/2890/--1/460/--17/4

55IUH.Ice Tea ESC44901/80/--3/1230/--0/--0/--0/--10/--0/--0/--2/551/26417/4

56HCMUS - Shine45012/910/--2/1250/--0/--0/--0/--1/1630/--0/--1/820/--6/4

57Blue Sea45061/162/--3/--0/--0/--0/--0/--3/1600/--0/--3/761/17413/4

58HCMUP1.PHT45141/102/--6/1930/--1/--0/--0/--5/--0/--0/--3/372/13420/4

59IUH.HPFairyTail45363/241/--14/--0/--1/2300/--0/--2/1160/--0/--1/1060/--22/4

60HCMUS - UpUp46841/300/--9/1630/--0/--0/--0/--6/1970/--0/--2/1340/--18/4

61HCMUP11.PVT47131/200/--5/2760/--0/--0/--0/--3/--0/--0/--1/973/20013/4

62Noobers47231/123/--5/2140/--0/--0/--0/--7/--0/--0/--2/1182/27920/4

63PSU #248262/381/--7/2070/--0/--0/--0/--1/2500/--0/--9/--1/19121/4

64HCMUS - Secret49291/391/--18/2770/--0/--0/--0/--0/--1/2700/--1/1030/--22/4

65HUBT Chicken49602/292/--6/2010/--0/--0/--0/--0/--0/--0/--4/2334/29718/4

66HUBT TXT32711/80/--3/1970/--0/--0/--0/--0/--0/--0/--1/4612/--17/3

67KSS32931/94/--1/2070/--6/--0/--0/--0/--0/--0/--2/570/--14/3

68TERABYTE33511/172/--2/--0/--0/--0/--2/--5/2130/--0/--1/410/--13/3

69IUH.Ice Tea CAPS34121/12/--4/2760/--0/--7/--0/--3/--0/--0/--2/550/--19/3

70HCMUP5.DTD34281/161/--0/--0/--0/--0/--0/--0/--0/--0/--3/1932/1597/3

71IUH.Ice Tea ALT34371/280/--6/--0/--0/--0/--0/--4/2410/--0/--2/880/--13/3

72UIT.HBT34451/183/--4/2660/--1/--0/--0/--3/--0/--0/--2/810/--14/3

73UIT-Fate34752/161/--8/--0/--0/--0/--0/--8/--0/--0/--1/519/22829/3

74icnhoukdsiih34971/280/--16/2660/--0/--0/--0/--2/630/--0/--10/--0/--29/3

75GreenHornet35441/134/--3/2720/--0/--0/--0/--0/--0/--0/--1/2190/--9/3

76UIT.Very_Happy35511/199/--14/2150/--0/--0/--0/--4/--0/--0/--3/770/--31/3

77HUS.CAMTU.201535841/342/--4/1130/--0/--0/--0/--1/--0/--0/--8/2570/--16/3

78STORM35936/872/1370/--0/--0/--0/--0/--0/--0/--0/--4/2490/--12/3

79The Human Spirit36092/140/--0/--0/--0/--0/--0/--7/2610/--0/--6/1744/--19/3

80Lead Soldier36162/273/--0/--0/--0/--0/--0/--0/--0/--0/--8/2921/27714/3

81beeDev36438/333/--1/2010/--1/--0/--0/--1/--0/--0/--8/2290/--22/3

82UIT.3T36471/36/--8/2970/--0/--0/--0/--2/--0/--0/--4/1672/--23/3

83HoneyBee37121/230/--4/2180/--0/--0/--0/--0/--0/--0/--8/2910/--13/3

84BumbleBee37599/620/--2/2720/--0/--0/--0/--0/--0/--0/--8/2050/--19/3

85VECTOR_UTC21151/114/--0/--0/--1/--0/--0/--0/--0/--0/--3/1041/--10/2

86The Dark21161/35/--0/--0/--0/--0/--0/--0/--0/--0/--4/530/--10/2

87HUS.OPEN.201521321/450/--2/670/--2/--0/--0/--1/--0/--0/--2/--0/--8/2

88Danang New21322/140/--4/--0/--0/--0/--0/--1/--0/--0/--2/785/--14/2

89BKKC21351/191/--4/561/--0/--0/--0/--6/--0/--0/--3/--0/--16/2

90UIT-Amateur21621/41/--6/--0/--0/--0/--0/--3/--0/--0/--2/1380/--13/2

91HCMUTRANS121711/480/--0/--0/--0/--2/--0/--0/--0/--0/--3/1230/--6/2

92CD-TCU21813/903/--2/510/--2/--9/--0/--0/--0/--0/--1/--0/--20/2

93STACK_UTC21951/313/--0/--0/--0/--0/--0/--1/--0/--0/--1/1640/--6/2

94HCMUSSH-0122033/301/--0/--0/--0/--0/--0/--0/--0/--0/--7/1330/--11/2

95HCMUP3.PVB22191/150/--0/--0/--0/--0/--0/--0/--0/--0/--15/--2/18418/2

96IUH.Ice Coffee Enter22393/23/--6/--0/--0/--0/--0/--9/1170/--0/--6/--0/--27/2

97IUH.REDSEC22483/160/--0/--0/--2/--0/--0/--0/--0/--0/--3/2121/--9/2

98Forensic22741/240/--4/2300/--0/--0/--0/--4/--0/--0/--0/--0/--9/2

99DH-TCU22815/322/--3/1290/--0/--0/--0/--0/--0/--0/--6/--0/--16/2

100HCMUSSH-0322907/442/--0/--0/--0/--0/--0/--0/--0/--0/--1/1260/--10/2

101IUH.4TTEAM22911/110/--0/--0/--0/--0/--0/--0/--0/--0/--5/2400/--6/2

102BUH223011/211/--4/2200/--0/--0/--0/--4/--0/--0/--0/--0/--10/2

103HCMUS - Team 2023104/1130/--0/--0/--0/--0/--0/--5/--0/--0/--1/1372/--12/2

104BUH123111/130/--5/2180/--1/--0/--0/--0/--0/--0/--1/--0/--8/2

105HCMUTRANS223282/510/--0/--0/--0/--0/--0/--3/--0/--0/--1/2570/--6/2

106HCMUS - Team 1123421/1620/--0/--0/--0/--0/--0/--0/--0/--0/--4/--2/1807/2

107HCMUS - Team 1423672/1280/--0/--0/--0/--0/--0/--5/--0/--0/--3/1793/--13/2

108Su pham DN 323762/440/--0/--0/--0/--0/--0/--0/--0/--0/--6/2320/--8/2

109Blueberries24095/624/--0/--0/--0/--0/--0/--0/--0/--0/--4/2270/--13/2

110HUS.JUNIOR.201524332/462/--10/2070/--1/--0/--0/--0/--0/--0/--0/--0/--15/2

111QUEUE_UTC24383/1721/--0/--0/--5/--0/--0/--0/--0/--0/--3/2260/--12/2

112IUH.7UP24422/1320/--7/2100/--0/--0/--0/--0/--0/--0/--1/--1/--11/2

1133D25345/1222/--0/--0/--0/--0/--0/--0/--0/--0/--7/2920/--14/2

114HCMUP13.CTTH25963/790/--0/--0/--0/--0/--0/--0/--0/--0/--11/2770/--14/2

115HUBT Duck171/70/--0/--0/--4/--0/--0/--0/--0/--0/--0/--3/--8/1

116HCMUP9.MXNT1101/100/--0/--2/--0/--0/--0/--0/--0/--0/--1/--0/--4/1

117TREE_UTC1111/111/--0/--0/--0/--0/--0/--0/--0/--0/--5/--1/--8/1

118UIT.THM1121/121/--4/--0/--0/--1/--0/--2/--0/--0/--6/--0/--15/1

119HCMUP4.TNT1161/160/--0/--0/--0/--0/--0/--0/--0/--0/--4/--4/--9/1

119QS-TCU1161/163/--4/--0/--0/--3/--0/--3/--0/--0/--7/--1/--22/1

121HUFLIT1211/213/--14/--0/--1/--4/--0/--0/--0/--0/--0/--0/--23/1

121One Piece1214/210/--7/--0/--0/--0/--0/--2/--0/--0/--0/--0/--13/1

123IUH.KUSHINA1272/70/--0/--0/--0/--0/--0/--1/--0/--0/--1/--4/--8/1

124IUH.WHITE FIRE1281/283/--1/--0/--0/--0/--0/--1/--0/--0/--4/--0/--10/1

125HCMUS - Team 191331/330/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--1/1

126IUH.Future1371/371/--0/--0/--0/--0/--0/--0/--0/--0/--5/--0/--7/1

127UnKnowN1382/180/--0/--0/--0/--0/--0/--6/--0/--0/--6/--0/--14/1

128HEAP_UTC1401/400/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--1/1

129UIT-Chicken1411/411/--0/--0/--0/--0/--0/--2/--0/--0/--2/--0/--6/1

130ECO1432/230/--9/--0/--0/--0/--0/--5/--0/--0/--8/--0/--24/1

131PSA.Brothers1452/257/--6/--0/--0/--0/--0/--1/--0/--0/--0/--1/--17/1

132IUH.INDEXING1484/483/--12/--0/--0/--0/--0/--0/--0/--0/--2/--0/--21/1

133Not found1553/150/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--3/1

134HCMUP6.DVC1573/170/--0/--0/--0/--0/--0/--0/--0/--0/--1/--0/--4/1

135IUH.Ice Tea CTRL1623/223/--2/--0/--0/--0/--0/--1/--0/--0/--0/--0/--9/1

136Manager1641/643/--0/--0/--0/--1/--0/--0/--0/--0/--0/--3/--8/1

137UIT-FTE1692/490/--11/--0/--0/--0/--0/--2/--0/--0/--3/--0/--18/1

138it-pdu21722/520/--0/--0/--0/--0/--0/--0/--0/--0/--6/--1/--9/1

139HCMUS - Team 131761/760/--2/--0/--0/--0/--0/--2/--0/--0/--0/--0/--5/1

140HCMUP14.TT1807/800/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--7/1

141UIT.HamHocHoi1892/693/--8/--0/--2/--0/--0/--4/--0/--0/--7/--3/--29/1

142HCMUP7.NVQ11002/800/--0/--0/--0/--0/--0/--0/--0/--0/--1/--0/--3/1

143HCMUS - Team 1811053/650/--14/--0/--0/--0/--0/--0/--0/--0/--0/--0/--17/1

144HCMUSSH-0211269/663/--0/--0/--0/--0/--0/--0/--0/--1/--3/--0/--16/1

145HCMUSSH-0411335/730/--0/--0/--0/--0/--0/--0/--0/--0/--2/--0/--7/1

146UIT.Coeus11343/942/--0/--0/--1/--0/--0/--1/--0/--0/--0/--0/--7/1

147it-pdu1115116/310/--0/--0/--0/--0/--0/--1/--0/--0/--15/--0/--32/1

148IUH.Ice Tea TAB12807/2202/--0/--0/--5/--0/--0/--5/--0/--0/--0/--0/--19/1

149HCMUS - Team 17131410/1940/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--10/1

150Age Of Futures000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150CTU.A2LTT000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150CTU.ICT000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150CTU.SCORERS000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150CTU.WAC000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUP10.DVT000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUP12.DDQ000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUP2.DTHP000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUP8.NHT000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUS - Team 7000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUS - Team 10000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUS - Team 15000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUS - Team 16000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150HCMUSSH-050023/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--23/0

150PETABYTE000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150Pham Duc000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

150South Vietnam Sea000/--0/--2/--0/--0/--0/--0/--0/--0/--0/--0/--0/--2/0

150Waiting000/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/--0/0

RankNameSolvedTime    A        B        C        D        E        F        G        H        I        J        K        L    Total att/solv

Submitted/1st Yes/Total Yes325/1/149210/10/8600/11/787/225/2161/51/3380/--/060/62/29301/9/6067/45/2814/4/2393/6/100186/27/642404/553

Created by CSUS PC^2 9.3 20150923 build 3167
http://www.ecs.csus.edu/pc2/
Last updated Sat Oct 10 13:23:31 ICT 2015