ACM题(#2634 Collecting Stones)

rollingpig

勉强在3秒内算出374.

1. 
   
2. var m number
   
3. exec :m:=374
   
4. 
   
5. WITH
   
6. routes2way1(srcblock,destblock,stones) AS( -- 把grid里的blocknumber改为相应的blockud,同时，构造双向通道表。
   
7. select (BLOCKNUMBER-8),(BLOCKNUMBER),stones from grid where mod(BLOCKNUMBER-8,8)<=4 and  mod(BLOCKNUMBER+8,8)>0 and BLOCKNUMBER-8>0   -- Move down
   
8. union all
   
9. select (BLOCKNUMBER+8),(BLOCKNUMBER),stones from grid where mod(BLOCKNUMBER+8,8)<=4 and  mod(BLOCKNUMBER+8,8)>0 and (BLOCKNUMBER+8)<=64 and BLOCKNUMBER!=1  --Move up
   
10. union all
    
11. select (BLOCKNUMBER-1),(BLOCKNUMBER),stones from grid where mod(BLOCKNUMBER-1,8)<4 and mod(blocknumber,8) !=1--Move right     
    
12. union all
    
13. select (BLOCKNUMBER-9),(BLOCKNUMBER),stones from grid where mod(blocknumber-1,8)<4 and mod(blocknumber,8)!=1 and BLOCKNUMBER-9>0  --Move down right
    
14. union all
    
15. select (BLOCKNUMBER+7),(BLOCKNUMBER),stones from grid where mod(blocknumber+7,8)<4 and mod(blocknumber,8)!=1 and BLOCKNUMBER+7<=64  --Move down right
    
16. ) ,
    
17. routes2way2(srcblock,destblock,stones) AS( -- 把grid里的blocknumber改为相应的blockud,同时，构造双向通道表。
    
18. select (BLOCKNUMBER+8),(BLOCKNUMBER),stones from grid where (mod(BLOCKNUMBER+8,8)>4 or mod(BLOCKNUMBER+8,8)=0) and BLOCKNUMBER+8<=64 -- Move up
    
19. union all
    
20. select (BLOCKNUMBER-8),(BLOCKNUMBER),stones from grid where (mod(BLOCKNUMBER-8,8)>4 or mod(BLOCKNUMBER-8,8)=0) and (BLOCKNUMBER-8)>0 and BLOCKNUMBER!=64--Move down
    
21. union all
    
22. select (BLOCKNUMBER+1),(BLOCKNUMBER),stones from grid where (mod(BLOCKNUMBER+1,8)>5 or mod(BLOCKNUMBER+1,8)=0) --Move left     
    
23. union all
    
24. select (BLOCKNUMBER-7),(BLOCKNUMBER),stones from grid where (mod(BLOCKNUMBER-7,8)>5 or mod(BLOCKNUMBER-7,8)=0) and BLOCKNUMBER-7>0  --Move down left
    
25. union all
    
26. select (BLOCKNUMBER+9),(BLOCKNUMBER),stones from grid where (mod(BLOCKNUMBER+9,8)>5 or mod(BLOCKNUMBER+9,8)=0) and BLOCKNUMBER+9<=64  --Move up right
    
27. ) ,
    
28. pathprobe1 (levelN,srcblock,destblock,totalstones) AS ( --先探测3级内的路径
    
29.   SELECT  /*+materilize */ 1, srcblock,destblock,routes2way1.stones+grid.stones
    
30.   from routes2way1 , grid
    
31.    where srcblock =  1  and grid.blocknumber=1    -- Start with first block
    
32.   UNION ALL
    
33.   SELECT        levelN+1,--递归层数
    
34.   a.srcblock,b.destblock,--出发、到达block
    
35.   a.totalstones + b.stones--stones
    
36.   FROM  pathprobe1 a , routes2way1 b
    
37.   WHERE        a.destblock = b.srcblock --join
    
38.   AND a.totalstones + b.stones <=:M
    
39. ) CYCLE destblock SET cycle_flag TO 'Y' DEFAULT 'N'
    
40. ,
    
41. path1 as
    
42. (
    
43. select  destblock,totalstones
    
44. from pathprobe1
    
45. where srcblock=1 and mod(destblock,8)=4
    
46. and  cycle_flag='N'
    
47. )
    
48. ,
    
49. pathprobe2 (levelN,srcblock,destblock,totalstones) AS ( --先探测3级内的路径
    
50.   SELECT  /*+materilize */ 1, srcblock,destblock,routes2way2.stones+grid.stones
    
51.   from routes2way2 , grid
    
52.    where srcblock =  64  and grid.blocknumber=64    -- Start with first block
    
53.   UNION ALL
    
54.   SELECT        levelN+1,--递归层数
    
55.   a.srcblock,b.destblock,--出发、到达block
    
56.   a.totalstones + b.stones--stones
    
57.   FROM  pathprobe2 a , routes2way2 b
    
58.   WHERE        a.destblock = b.srcblock --join
    
59.   AND a.totalstones + b.stones <=:M
    
60. ),
    
61. path2 as (
    
62. select destblock,totalstones from pathprobe2
    
63. where  srcblock=64 and mod(destblock,8)=5
    
64. )  select /*+use_hash(p1 p2)*/ * from  
    
65. path1 p1  , path2  p2
    
66. where
    
67. (
    
68. p1.destblock+1 = p2.destblock  or  --Right
    
69. p1.destblock+9 = p2.destblock  or --Down right
    
70. p1.destblock-7 = p2.destblock -- Up rigth
    
71.   )  and  p1.totalstones = :M - p2.totalstones
    
72.   and rownum = 1
    
73. 
    

复制代码

影之哀伤

嗯 确认下

1 根据题意，那么左上和右下两个石头是必选的了？

2 如果有多个解，需要输出所有的么，还是需要输出全部？

〇〇

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

T.PATH||'*'||T2.PATH
----------------------------------------
,01,02,03,04*13,22,30,38,46,47,48,56,64,
已用时间:  00: 00: 00.07

〇〇

题意是只要输出yes no但为了好验证还是要输出1个，如果有

lugionline

with
d(n) as (select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7),
cost(i, j, v) as (select d1.n, d2.n, d1.n * 8 + d2.n + 1 from d d1, d d2),
direction(i, j) as
(
        select 1, 1 union
        select 1, 0 union
        select 1, -1 union
        select 0, 1 union
        select 0, -1),
path14(i, j, v, s) as
(
        select 0, 0, v,
                cast('x' as char(64)) s from cost where i = 0 and j = 0
        union all
        select p.i + d.i, p.j + d.j, p.v + c.v,
                cast(stuff(p.s, 8 * (p.i + d.i) + p.j + d.j + 1, 1, 'x') as char(64)) s
        from path14 p, direction d, cost c
        where p.i + d.i >= 0 and p.i + d.i < 4 -- 在网格内
                and p.j + d.j >= 0 and p.j + d.j < 8
                and substring(p.s, 8 * (p.i + d.i) + p.j + d.j + 1, 1) <> 'x' -- 没访问过
                and p.i + d.i = c.i and p.j + d.j = c.j -- 取得费用
),
path85(i, j, v, s) as
(
        select 7, 7, v,
                cast(stuff(space(64), 8 * 7 + 7 + 1, 1, 'x') as char(64)) s
        from cost where i = 7 and j = 7
        union all
        select p.i - d.i, p.j - d.j, p.v + c.v,
                cast(stuff(p.s, 8 * (p.i - d.i) + p.j - d.j + 1, 1, 'x') as char(64)) s
        from path85 p, direction d, cost c
        where p.i - d.i >= 0 and p.i - d.i >= 4 -- 在网格内
                and p.j - d.j >= 0 and p.j - d.j < 8
                and substring(p.s, 8 * (p.i - d.i) + p.j - d.j + 1, 1) <> 'x' -- 没访问过
                and p.i - d.i = c.i and p.j - d.j = c.j -- 取得费用
),
pa(j, v) as (select j,v from path14 where i=3),
pb(j, v) as (select j,v from path85 where i=4)
select top 1 * from pa, pb
where
        (pa.j = pb.j or pa.j + 1 = pb.j or pa.j - 1 = pb.j)
        and pa.v + pb.v = 374 -- 取值

lugionline

pa, pb 基本上2秒就出来了，就是最后连接慢，这个大家可以想想办法，有路径的时候是很快的，但是没路径......

第5步其实用 C很容易做

lugionline

374在我这里只要19ms

〇〇

原帖由 lugionline 于 2011-4-12 13:54 发表
374在我这里只要19ms

不知道我翻译对了没有

1. 
   
2. with
   
3. d(n) as (select level-1 n from dual connect by level<=8),
   
4. cost(i, j, v) as (select d1.n, d2.n, d1.n * 8 + d2.n + 1 from d d1, d d2),
   
5. direction(i, j) as
   
6. (
   
7.         select 1, 1 from dual union
   
8.         select 1, 0 from dual union
   
9.         select 1, -1 from dual union
   
10.         select 0, 1 from dual union
    
11.         select 0, -1 from dual ),
    
12. path14(i, j, v, s) as
    
13. (
    
14.         select 0, 0, v,
    
15.                 cast('x' as char(64)) s from cost where i = 0 and j = 0
    
16.         union all
    
17.         select p.i + d.i, p.j + d.j, p.v + c.v,
    
18.                 cast(substr(p.s,1, 8 * (p.i + d.i) + p.j + d.j + 1-1)|| 'x'||substr(p.s, 8 * (p.i + d.i) + p.j + d.j + 1+1) as char(64)) s
    
19.         from path14 p, direction d, cost c
    
20.         where p.i + d.i >= 0 and p.i + d.i < 4 -- 在网格内
    
21.                 and p.j + d.j >= 0 and p.j + d.j < 8
    
22.                 and substr(p.s, 8 * (p.i + d.i) + p.j + d.j + 1, 1) <> 'x' -- 没访问过
    
23.                 and p.i + d.i = c.i and p.j + d.j = c.j -- 取得费用
    
24. ),
    
25. path85(i, j, v, s) as
    
26. (
    
27.         select 7, 7, v,
    
28.                 cast(substr(lpad(' ',64,' '), 1,8 * 7 + 7 + 1-1)|| 'x' as char(64)) s
    
29.         from cost where i = 7 and j = 7
    
30.         union all
    
31.         select p.i - d.i, p.j - d.j, p.v + c.v,
    
32.                 cast(substr(p.s, 1,8 * (p.i - d.i) + p.j - d.j + 1-1)|| 'x'||substr(p.s, 8 * (p.i - d.i) + p.j - d.j + 1+1) as char(64)) s
    
33.         from path85 p, direction d, cost c
    
34.         where p.i - d.i >= 0 and p.i - d.i >= 4 -- 在网格内
    
35.                 and p.j - d.j >= 0 and p.j - d.j < 8
    
36.                 and substr(p.s, 8 * (p.i - d.i) + p.j - d.j + 1, 1) <> 'x' -- 没访问过
    
37.                 and p.i - d.i = c.i and p.j - d.j = c.j -- 取得费用
    
38. ),
    
39. pa(j, v) as (select j,v from path14 where i=3),
    
40. pb(j, v) as (select j,v from path85 where i=4)
    
41. select * from pa, pb
    
42. where
    
43.         (pa.j = pb.j or pa.j + 1 = pb.j or pa.j - 1 = pb.j)
    
44.         and pa.v + pb.v = 374 -- 取值
    
45. and rownum=1;
    
46. 
    
47. SQL> @c:\downloads\log
    
48. 
    
49.          J          V          J          V
    
50. ---------- ---------- ---------- ----------
    
51.          1         53          2        321
    
52. 已用时间:  00: 00: 35.61
    

复制代码

rollingpig

我尝试 12，34，87，65,14,85,18分步做

基本性能是这样的(不考虑<M带来的裁剪)：

step, rows count , times(ms)
12,    183 , 15
34,    1464 , 93
14,    5806 , 400
87,    183, 15
65,    1464, 93
85,    5806, 400
18,    0, 800

最终800ms(M比较大的情况),我这里很难再提升了

rollingpig

优化关键在于12/34，87/65做join.

1. 
   
2. WITH                                                                                                  
   
3. p12  (srcblock,destblock,tst,pathstr) AS (
   
4.   SELECT  /*+ */ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
   
5.   from grid a , grid b
   
6.    where
   
7.    a.n=1    -- Start with first block
   
8.    and mod(b.n,8) in (1,2)
   
9.    and b.n in (
   
10.     a.n + 1,
    
11.     a.n - 7,
    
12.     a.n + 9,
    
13.     a.n + 8,
    
14.     a.n - 8)  
    
15.   UNION ALL
    
16.   SELECT
    
17.   a.srcblock,b.n,
    
18.   a.tst + b.st,--st
    
19.   pathstr||chr(b.n)
    
20.   FROM  p12 a , (select * from grid where mod(n,8) in (1,2)) b
    
21.   WHERE         b.n in (
    
22.   a.destblock + 1,
    
23.   a.destblock - 7,
    
24.   a.destblock + 9,
    
25.   a.destblock + 8,
    
26.   a.destblock - 8
    
27.   ) and b.n!=1
    
28.   AND a.tst + b.st <=:M
    
29.   and instr(pathstr,chr(n))=0
    
30. ),
    
31. pp12 as (
    
32. select /*+ */ distinct destblock,tst from p12
    
33. where mod(destblock,8)=2
    
34. ),
    
35. p34  (srcblock,destblock,tst,pathstr) AS (
    
36.   SELECT   a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
    
37.   from grid a , grid b
    
38.    where  mod(a.n,8) =3    -- Start with first block
    
39.    and b.n in (
    
40.     a.n + 1,
    
41.     a.n - 7,
    
42.     a.n + 9,
    
43.     a.n + 8,
    
44.     a.n - 8
    
45.    )
    
46.    and mod(a.n,8) in (3,4)
    
47.   UNION ALL
    
48.   SELECT
    
49.   a.srcblock,b.n,--出发、到达block
    
50.   a.tst + b.st,--st
    
51.    pathstr||chr(b.n)
    
52. FROM  p34 a , (select * from grid where mod(n,8) in (3,4)) b
    
53.   WHERE         b.n in (
    
54.   a.destblock + 1,
    
55.   a.destblock - 7,
    
56.   a.destblock + 9,
    
57.   a.destblock + 8,
    
58.   a.destblock - 8
    
59.   )
    
60.   AND a.tst + b.st <:M
    
61.   and instr(pathstr,chr(n))=0
    
62. ) ,
    
63. pp34 as (
    
64. select /*+ */ distinct srcblock,destblock,tst from p34
    
65. where mod(destblock,8)=4
    
66. ) ,
    
67. p14 as(
    
68. select /*+  use_concat ordered use_hash(a b)   */ distinct b.destblock,a.tst+b.tst  tst
    
69. from pp12 a,pp34 b
    
70. where
    
71.   b.srcblock in (
    
72.   a.destblock + 1 ,
    
73.   a.destblock - 7 ,
    
74.   a.destblock + 9
    
75. )
    
76.   AND a.tst + b.tst <:M
    
77. ),
    
78. p87  (srcblock,destblock,tst,pathstr) AS (
    
79.   SELECT  /*+ */a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
    
80.   from grid a , grid b
    
81.    where  a.n=64    -- Start with last block
    
82.    and b.n in (
    
83.     a.n - 1,
    
84.     a.n - 9,
    
85.     a.n + 7,
    
86.     a.n + 8,
    
87.     a.n - 8
    
88.   )
    
89.   and mod(b.n,8) in (0,7)
    
90.   UNION ALL
    
91.   SELECT
    
92.   a.srcblock,b.n,--出发、到达block
    
93.   a.tst + b.st,--st
    
94.   pathstr||chr(b.n)
    
95.   FROM  p87 a , (select * from grid where mod(n,8) in (0,7)) b
    
96.   WHERE         b.n in (
    
97.     a.destblock - 1,
    
98.     a.destblock - 9,
    
99.     a.destblock + 7,
    
100.     a.destblock + 8,
     
101.     a.destblock - 8
     
102.   ) and b.n!=64
     
103.   AND a.tst + b.st <:M
     
104.   and instr(pathstr,chr(n))=0
     
105. ),
     
106. pp87 as (
     
107. select /*+ */ distinct destblock,tst from p87
     
108. where mod(destblock,8)=7
     
109. ),
     
110. p65  (srcblock,destblock,tst,pathstr) AS ( --先探测3级内的路径
     
111.   SELECT   a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
     
112.   from grid a , grid b
     
113.    where  mod(a.n,8) =6    -- Start with first block
     
114.    and b.n in (
     
115.     a.n - 1,
     
116.     a.n - 9,
     
117.     a.n + 7,
     
118.     a.n + 8,
     
119.     a.n - 8
     
120.    )
     
121.    and mod(a.n,8) in (5,6)
     
122.   UNION ALL
     
123.   SELECT
     
124.   a.srcblock,b.n,--出发、到达block
     
125.   a.tst + b.st,--st
     
126.    pathstr||chr(b.n)
     
127. FROM  p65 a , (select * from grid where mod(n,8) in (5,6)) b
     
128.   WHERE         b.n in (
     
129.     a.destblock - 1,
     
130.     a.destblock - 9,
     
131.     a.destblock + 7,
     
132.     a.destblock + 8,
     
133.     a.destblock - 8
     
134.   )
     
135.   AND a.tst + b.st <=:M
     
136.   and instr(pathstr,chr(n))=0
     
137. )
     
138. ,
     
139. pp65 as (
     
140. select /*+ */ distinct srcblock,destblock,tst from p65
     
141. where mod(destblock,8)=5
     
142. )  ,
     
143. p85 as(
     
144. select /*+ use_concat ordered use_hash(a b)  */ distinct b.destblock,b.tst+a.tst tst
     
145. from pp87 a,pp65 b
     
146. where
     
147.   b.srcblock in (
     
148.   a.destblock - 1 ,
     
149.   a.destblock + 7 ,
     
150.   a.destblock - 9
     
151. )
     
152. and b.tst+a.tst<:M
     
153. ),
     
154. p18 as (
     
155. select /*+use_hash(a b)  */'Y' f from p14 a,p85 b
     
156. where
     
157.   b.destblock in (
     
158.   a.destblock + 1 ,
     
159.   a.destblock - 7 ,
     
160.   a.destblock + 9
     
161. ) and  b.tst = :M - a.tst
     
162. and rownum = 1
     
163. )
     
164. select nvl(max(f),'N') from p18  
     
165. 
     

复制代码