ACM题(#2634 Collecting Stones)

〇〇

原帖由 rollingpig 于 2011-4-12 16:17 发表
MAX(TST),MIN(TST)
1948,328

pathstr?

〇〇

SQL> exec :m:=2000
已用时间:  00: 00: 00.00
SQL> @c:\downloads\rp1

N
-
N
已用时间:  00: 00: 00.12
把/*+ 改为/*-
SQL> @c:\downloads\rp1

N
-
N
已用时间:  00: 00: 42.30

lastwinner

讨论得很激烈，请继续，并请详解思路

rollingpig

呵呵，思路很简单
1. 每个列先单独找出列内的路径及石头数
2. 分别从1和64出发，其中64反方向走
1列并上2列并上3列并上4列，中间用total stone <:M过滤
8列并上7列并上6列并上5列，中间用total stone <:M过滤

最后在中间相遇。

下面的code稍微在原表添加了几个字段，避免后期运算

另外，从执行计划看，不知道为什么，几个cascade with 总是不能实体化，导致重复运算(3x),所以性能还是有提升空间。
再考虑到SQL引擎本身的开销，估计用类似算法写成C/C++, 应该可以到100ms以内。

1. 
   
2. drop table grid  ;
   
3. create table grid(x,y,n,s,st) as
   
4. select x,y,x*8+y,chr(x*8+y),round(dbms_random.value(10,100)) from
   
5. (select rownum-1 as x from dual connect by rownum <= 8),
   
6. (select rownum as y from dual connect by rownum <= 8)  ;
   
7. 
   
8. WITH                                                                                                  
   
9. p1(srcblock,destblock,tst,pathstr) AS (
   
10.   SELECT  /*+ materialize no_merge */ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
11.   from grid a , grid b
    
12.    where
    
13.    a.n=1    -- Start with first block
    
14.    and b.n in (a.n + 8)
    
15.   UNION ALL
    
16.   SELECT /*+ materialize */
    
17.   a.srcblock,b.n,
    
18.   a.tst + b.st,--st
    
19.   pathstr||b.s
    
20.   FROM  p1 a , (select * from grid where y in (1)) b
    
21.   WHERE         b.n in (
    
22.   a.destblock + 8
    
23.   ) and b.n!=1
    
24.   AND a.tst + b.st <=:M
    
25.   and instr(pathstr,s)=0
    
26. ),
    
27. p2(srcblock,destblock,tst,pathstr) AS (
    
28.   SELECT  /*+ materialize no_merge */ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
29.   from grid a , grid b
    
30.    where  a.y in (2)
    
31.    and b.n in (a.n + 8, a.n -8 )
    
32.   UNION ALL
    
33.   SELECT
    
34.   a.srcblock,b.n,
    
35.   a.tst + b.st,--st
    
36.   pathstr||b.s
    
37.   FROM  p2 a , (select * from grid where y in (2)) b
    
38.   WHERE         b.n in (
    
39.   a.destblock + 8  , a.destblock - 8
    
40.   )
    
41.   AND a.tst + b.st <=:M
    
42.   and instr(pathstr,s)=0
    
43. ),
    
44. p3(srcblock,destblock,tst,pathstr) AS (
    
45.   SELECT  /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
46.   from grid a , grid b
    
47.    where  a.y in (3)
    
48.    and b.n in (a.n + 8, a.n -8 )
    
49.   UNION ALL
    
50.   SELECT
    
51.   a.srcblock,b.n,                     
    
52.   a.tst + b.st,--st
    
53.   pathstr||b.s
    
54.   FROM  p3 a , (select * from grid where y in (3)) b
    
55.   WHERE         b.n in (
    
56.   a.destblock + 8  , a.destblock - 8
    
57.   )
    
58.   AND a.tst + b.st <=:M
    
59.   and instr(pathstr,s)=0
    
60. ),
    
61. p4(srcblock,destblock,tst,pathstr) AS (
    
62.   SELECT  /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
63.   from grid a , grid b
    
64.    where  a.y in (4)
    
65.    and b.n in (a.n + 8, a.n -8 )
    
66.   UNION ALL
    
67.   SELECT
    
68.   a.srcblock,b.n,
    
69.   a.tst + b.st,--st
    
70.   pathstr||b.s
    
71.   FROM  p4 a , (select * from grid where y in (4)) b
    
72.   WHERE         b.n in (
    
73.   a.destblock + 8  , a.destblock - 8
    
74.   )
    
75.   AND a.tst + b.st <=:M
    
76.   and instr(pathstr,s)=0
    
77. ),
    
78. p5(srcblock,destblock,tst,pathstr) AS (
    
79.   SELECT  /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
80.   from grid a , grid b
    
81.    where  a.y in (5)
    
82.    and b.n in (a.n + 8, a.n -8 )
    
83.   UNION ALL
    
84.   SELECT
    
85.   a.srcblock,b.n,
    
86.   a.tst + b.st,--st
    
87.   pathstr||b.s
    
88.   FROM  p5 a , (select * from grid where y in (5)) b
    
89.   WHERE         b.n in (
    
90.   a.destblock + 8  , a.destblock - 8
    
91.   )
    
92.   AND a.tst + b.st <=:M
    
93.   and instr(pathstr,s)=0
    
94. ),
    
95. p6(srcblock,destblock,tst,pathstr) AS (
    
96.   SELECT  /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
    
97.   from grid a , grid b
    
98.    where  a.y in (6)
    
99.    and b.n in (a.n + 8, a.n -8 )
    
100.   UNION ALL
     
101.   SELECT
     
102.   a.srcblock,b.n,
     
103.   a.tst + b.st,--st
     
104.   pathstr||b.s
     
105.   FROM  p6 a , (select * from grid where y in (6)) b
     
106.   WHERE         b.n in (
     
107.   a.destblock + 8  , a.destblock - 8
     
108.   )
     
109.   AND a.tst + b.st <=:M
     
110.   and instr(pathstr,s)=0
     
111. ),
     
112. p7(srcblock,destblock,tst,pathstr) AS (
     
113.   SELECT  /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
     
114.   from grid a , grid b
     
115.    where  a.y in (7)
     
116.    and b.n in (a.n + 8, a.n -8 )
     
117.   UNION ALL
     
118.   SELECT
     
119.   a.srcblock,b.n,
     
120.   a.tst + b.st,--st
     
121.   pathstr||b.s
     
122.   FROM  p7 a , (select * from grid where y in (7)) b
     
123.   WHERE         b.n in (
     
124.   a.destblock + 8  , a.destblock - 8
     
125.   )
     
126.   AND a.tst + b.st <=:M
     
127.   and instr(pathstr,s)=0
     
128. ),
     
129. p8(srcblock,destblock,tst,pathstr) AS (
     
130.   SELECT  /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(a.s||b.s as varchar2(100))
     
131.   from grid a , grid b
     
132.    where a.n=64
     
133.    and b.n in (a.n -8 )
     
134.   UNION ALL
     
135.   SELECT
     
136.   a.srcblock,b.n,
     
137.   a.tst + b.st,--st
     
138.   pathstr||b.s
     
139.   FROM  p8 a , (select * from grid where y in (8)) b
     
140.   WHERE         b.n in ( a.destblock - 8 )
     
141.   AND a.tst + b.st <=:M
     
142.   and instr(pathstr,s)=0
     
143. ),
     
144. p12 as (
     
145. select /*+ materialize no_merge use_concat ordered use_hash(a b)   */ distinct b.destblock,a.tst+b.tst  tst
     
146. from p1 a,p2 b
     
147. where
     
148.   b.srcblock in (
     
149.   a.destblock + 1 ,
     
150.   a.destblock - 7 ,
     
151.   a.destblock + 9
     
152. )
     
153.   AND a.tst + b.tst <:M
     
154. ),
     
155. p13 as (
     
156. select /*+ materialize no_merge ordered use_concat  use_hash(a b)   */ distinct b.destblock,a.tst+b.tst  tst
     
157. from  p3 b , (
     
158. select /*+no_merge(p12) */ tst, destblock+1 as destblock from p12
     
159. union all
     
160. select /*+no_merge(p12) */  tst, destblock+9 as destblock from p12
     
161. union all
     
162. select  /*+no_merge(p12) */ tst, destblock-7 as destblock from p12
     
163. ) a   
     
164. where
     
165.   b.srcblock =  a.destblock
     
166.   AND a.tst + b.tst <:M
     
167. ),
     
168. p14 as (
     
169. select /*+ materialize no_merge ordered use_concat  use_hash(a b)  no_merge(a) */ distinct b.destblock,a.tst+b.tst  tst
     
170. from p4 b,  
     
171. (
     
172. select /*+no_merge(p13) */ tst, destblock+1 as destblock from p13
     
173. union all
     
174. select /*+no_merge(p13) */  tst, destblock+9 as destblock from p13
     
175. union all
     
176. select  /*+no_merge(p13) */ tst, destblock-7 as destblock from p13
     
177. ) a   
     
178. where
     
179.   b.srcblock =  a.destblock
     
180.   AND a.tst + b.tst <:M
     
181. ) ,
     
182. p87 as (
     
183. select /*+ materialize no_merge use_concat ordered use_hash(a b)   */ distinct b.destblock,a.tst+b.tst  tst
     
184. from p8 a,p7 b
     
185. where
     
186.   b.srcblock in (
     
187.   a.destblock - 1 ,
     
188.   a.destblock + 7 ,
     
189.   a.destblock - 9
     
190. )
     
191.   AND a.tst + b.tst <:M
     
192. ),
     
193. p86 as (
     
194. select /*+ materialize no_merge ordered use_concat  use_hash(a b)   */ distinct b.destblock,a.tst+b.tst  tst
     
195. from  p6 b ,
     
196. ( select /*+no_merge(p87) */ tst, destblock-1 as destblock from p87
     
197. union all
     
198. select /*+no_merge(p87) */  tst, destblock-9 as destblock from p87
     
199. union all
     
200. select  /*+no_merge(p87) */ tst, destblock+7 as destblock from p87) a
     
201. where
     
202.   b.srcblock =a.destblock
     
203.   AND a.tst + b.tst <:M
     
204. ),
     
205. p85 as (
     
206. select /*+ materialize no_merge ordered use_concat  use_hash(a b)  */ distinct b.destblock,a.tst+b.tst  tst
     
207. from  p5 b,
     
208. ( select /*+no_merge(p87) */ tst, destblock-1 as destblock from p86
     
209. union all
     
210. select /*+no_merge(p87) */  tst, destblock-9 as destblock from p86
     
211. union all
     
212. select  /*+no_merge(p87) */ tst, destblock+7 as destblock from p86) a
     
213. where
     
214.   b.srcblock =a.destblock
     
215.   AND a.tst + b.tst <:M
     
216. ),
     
217. p18 as (
     
218. select /*+use_hash(a b)  */'Y' f,a.tst+b.tst tst from p14 a,p85 b
     
219. where
     
220.   b.destblock in (
     
221.   a.destblock + 1 ,
     
222.   a.destblock - 7 ,
     
223.   a.destblock + 9
     
224. ) and  b.tst = :M - a.tst and rownum = 1
     
225. )
     
226. select nvl(max(f),'N') from p18  
     
227. 
     

复制代码

〇〇

我偷偷用了滚珠的hint,大数也变快了
SQL> exec :m:=500
已用时间:  00: 00: 00.00
SQL> @c:\downloads\rpo

N
-
Y
已用时间:  00: 00: 00.13
SQL> @c:\downloads\26345rp

T.PATH||'*'||T2.PATH
-----------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,34,26,18,10,19,27,35,44*37,46,55,64,
已用时间:  00: 00: 00.43
SQL> exec :m:=900
已用时间:  00: 00: 00.00
SQL> @c:\downloads\26345rp

T.PATH||'*'||T2.PATH
-----------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,58,50,42,34,26,35,43,51,59,52*45,54,55,64,
已用时间:  00: 00: 00.43
SQL> exec :m:=1100
已用时间:  00: 00: 00.00
SQL> @c:\downloads\26345rp

T.PATH||'*'||T2.PATH
-----------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,58,50,42,34,26,18,11,19,27,35,43,51,59,60*53,62,54,47,55,64,
已用时间:  00: 00: 00.50
SQL> exec :m:=1500
已用时间:  00: 00: 00.00
SQL> @c:\downloads\26345rp

T.PATH||'*'||T2.PATH
-----------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,58,50,42,34,26,18,11,19,27,35,43,51,59,52*45,38,46,54,62,63,55,47,39,31,23,32,40,48,56,64,
已用时间:  00: 00: 03.06
SQL> exec :m:=1912
已用时间:  00: 00: 00.00
SQL> @c:\downloads\26345rp
已用时间:  00: 00: 11.21
SQL> exec :m:=1948
已用时间:  00: 00: 00.00
SQL> @c:\downloads\26345rp
已用时间:  00: 00: 11.08

〇〇

但是后边的几个算不出来，不知错在哪里

1. 
   
2. WITH d AS (
   
3.   SELECT to_char(ROWNUM,'fm09') id
   
4.         ,CEIL(ROWNUM/8) r
   
5.         ,MOD(ROWNUM-1,8)+1 c
   
6.         ,ROWNUM val
   
7.     FROM DUAL
   
8.    CONNECT BY ROWNUM<=64
   
9.   )
   
10. ,t(r,c,val,total,path) AS (
    
11.   SELECT r,c,val,val,','||CAST(id AS VARCHAR2(4000)) FROM d WHERE r=1 AND c=1
    
12.   UNION ALL
    
13.   SELECT d.r,d.c,d.val,d.val+t.total,t.path||','||d.id
    
14.     FROM t, d
    
15.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
16.          AND (d.r,d.c) IN ((t.r-1,t.c),(t.r+1,t.c),(t.r,t.c+1),(t.r-1,t.c+1),(t.r+1,t.c+1))
    
17.          AND d.val+t.total<:M
    
18.          and t.c<4
    
19.   )
    
20. ,t2(r,c,val,total,path) AS (
    
21.   SELECT r,c,val,val,CAST(id AS VARCHAR2(4000))||',' FROM d WHERE r=8 AND c=8
    
22.   UNION ALL
    
23.   SELECT d.r,d.c,d.val,d.val+t.total,d.id||','||t.path
    
24.     FROM t2 t, d
    
25.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
26.          AND (d.r,d.c) IN ((t.r+1,t.c),(t.r-1,t.c),(t.r,t.c-1),(t.r+1,t.c-1),(t.r-1,t.c-1))
    
27.          AND d.val+t.total<:M
    
28.          and t.c>5
    
29.   )
    
30. SELECT /*+ materialize no_merge use_concat ordered use_hash(t t2)   */t.path||'*'||t2.path FROM t,t2
    
31. WHERE (t.r=t2.r or t.r=t2.r-1 or  t.r=t2.r+1)AND t.c=4 and t2.c=4+1
    
32. AND t.total+t2.total=:M and rownum=1;
    
33. 
    
34. 
    

复制代码

rollingpig

原帖由 〇〇 于 2011-4-12 16:20 发表

pathstr?

0+1+9+17+25+33+41+49+57+58+50+59+51+43+35+27+19+11+3+4+12+20+28+36+44+52+60
0+61+53+45+37+29+21+13+5+6+14+22+30+38+46+54+62+63+55+47+39+31+23+15+7+8+16+24+32+40+48+56+64

rollingpig

AND t.total+t2.total=:M and rownum=1;
==>

AND t.total=:M- t2.total and rownum=1;

就成hash了

原帖由 〇〇 于 2011-4-12 17:04 发表
但是后边的几个算不出来，不知错在哪里


WITH d AS (
  SELECT to_char(ROWNUM,'fm09') id
        ,CEIL(ROWNUM/8) r
        ,MOD(ROWNUM-1,8)+1 c
        ,ROWNUM val
    FROM DUAL
   CONNECT BY ROWNUM

rollingpig

SELECT /*+ materialize no_merge use_concat ordered use_hash(t t2)   */t.path||'*'||t2.path FROM t,t2


==

SELECT /*+ ordered use_hash(t t2)   */t.path||'*'||t2.path FROM t,t2
去掉use_concat, 基本一秒没问题

rollingpig

and t.c<4
==>
and t.c<=4


and t.c>5
==>
and t.c>=4