ACM题(#2634 Collecting Stones)

rollingpig · 发表于 2011-4-12 15:16

也许可以再细分，12,3,4 这样的走

rollingpig · 发表于 2011-4-12 15:19

倒数第四行
and b.tst = :M - a.tst

也是个关键优化点，从 b.tst + a.tst = :M 改过来，使其走hash

〇〇 · 发表于 2011-4-12 15:31

原帖由 rollingpig 于 2011-4-12 15:10 发表
我尝试 12，34，87，65,14,85,18分步做

基本性能是这样的(不考虑

m=1912,是有解的,能算出来?

〇〇 · 发表于 2011-4-12 15:49

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

T.PATH||'*'||T2.PATH
--------------------------------------------
,01,02,03,04*13,14,23,32,40,48,56,64,
已用时间:  00: 00: 00.02
SQL> @c:\downloads\log

      J       V       J       V
---------- ---------- ---------- ----------
      3       58       4       242
已用时间:  00: 07: 06.94

〇〇 · 发表于 2011-4-12 15:58

58翻译增加2个<:M就快了

with
d(n) as (select level-1 n from dual connect by level<=8),
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 from dual union
select 1, 0 from dual union
select 1, -1 from dual union
select 0, 1 from dual union
select 0, -1 from dual ),
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(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
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 substr(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 -- 取得费用
and p.v+c.v<:M
),
path85(i, j, v, s) as
(
select 7, 7, v,
cast(substr(lpad(' ',64,' '), 1,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(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
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 substr(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 -- 取得费用
and p.v+c.v<:M
),
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 * from pa, pb
where
(pa.j = pb.j or pa.j = pb.j-1 or pa.j = pb.j+1)
and pa.v + pb.v = :M -- 取值
and rownum=1;

复制代码

SQL> @c:\downloads\log1

      J       V       J       V
---------- ---------- ---------- ----------
      3       58       4       242
已用时间:  00: 00: 00.72

〇〇 · 发表于 2011-4-12 16:00

不过数字大了还是不行。ms和ora的差别？

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

      J       V       J       V
---------- ---------- ---------- ----------
      0       52       1       748
已用时间:  00: 00: 14.77
SQL> @c:\downloads\26345

T.PATH||'*'||T2.PATH
-------------------------------------------------------------------------------------
,01,02,03,04*13,06,14,22,30,38,46,54,62,55,47,39,31,23,15,07,08,16,24,32,40,48,56,64,
已用时间:  00: 00: 00.46

lugionline · 发表于 2011-4-12 16:08

MS 好像是并行执行的，只要表中有数据，最后的那个查询就开始了，所以小数字很快能找到结果，不需要在path14,85中做限制

不过问题也在这里，数字大的时候比方1912，如果我先计算好两张临时表，然后直接join，基本1分钟出结果，但是如果使用CTE就很慢

我觉得这题要快还是要应用这个条件（总数量不超过2000001），C里面可以开个bit数组然后一查就知道了，SQL中...

rollingpig · 发表于 2011-4-12 16:11

170ms, 数字不管
1-8全拆散

var m number
exec :m:=1912
WITH
p1(srcblock,destblock,tst,pathstr) AS (
SELECT /*+ materialize no_merge */ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where
a.n=1 -- Start with first block
and b.n in (a.n + 8)
UNION ALL
SELECT /*+ materialize */
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p1 a , (select * from grid where mod(n,8) in (1)) b
WHERE b.n in (
a.destblock + 8
) and b.n!=1
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p2(srcblock,destblock,tst,pathstr) AS (
SELECT /*+ materialize no_merge */ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (2)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p2 a , (select * from grid where mod(n,8) in (2)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p3(srcblock,destblock,tst,pathstr) AS (
SELECT /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (3)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p3 a , (select * from grid where mod(n,8) in (3)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p4(srcblock,destblock,tst,pathstr) AS (
SELECT /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (4)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p4 a , (select * from grid where mod(n,8) in (4)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p5(srcblock,destblock,tst,pathstr) AS (
SELECT /*+ materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (5)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p5 a , (select * from grid where mod(n,8) in (5)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p6(srcblock,destblock,tst,pathstr) AS (
SELECT /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (6)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p6 a , (select * from grid where mod(n,8) in (6)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p7(srcblock,destblock,tst,pathstr) AS (
SELECT /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where mod(a.n,8) in (7)
and b.n in (a.n + 8, a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p7 a , (select * from grid where mod(n,8) in (7)) b
WHERE b.n in (
a.destblock + 8 , a.destblock - 8
)
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p8(srcblock,destblock,tst,pathstr) AS (
SELECT /*+materialize no_merge*/ a.n,b.n,a.st+b.st,cast(chr(a.n)||chr(b.n) as varchar2(100))
from grid a , grid b
where a.n=64
and b.n in (a.n -8 )
UNION ALL
SELECT
a.srcblock,b.n,
a.tst + b.st,--st
pathstr||chr(b.n)
FROM p8 a , (select * from grid where mod(n,8) in (0)) b
WHERE b.n in ( a.destblock - 8 )
AND a.tst + b.st <=:M
and instr(pathstr,chr(n))=0
),
p12 as (
select /*+ materialize no_merge use_concat ordered use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p1 a,p2 b
where
b.srcblock in (
a.destblock + 1 ,
a.destblock - 7 ,
a.destblock + 9
)
AND a.tst + b.tst <:M
),
p13 as (
select /*+ materialize no_merge ordered use_concat use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p3 b , p12 a
where
b.srcblock in (
a.destblock + 1 ,
a.destblock - 7 ,
a.destblock + 9
)
AND a.tst + b.tst <:M
),
p14 as (
select /*+ materialize no_merge ordered use_concat use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p4 b , p13 a
where
b.srcblock in (
a.destblock + 1 ,
a.destblock - 7 ,
a.destblock + 9
)
AND a.tst + b.tst <:M
) ,
p87 as (
select /*+ materialize no_merge use_concat ordered use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p8 a,p7 b
where
b.srcblock in (
a.destblock - 1 ,
a.destblock + 7 ,
a.destblock - 9
)
AND a.tst + b.tst <:M
),
p86 as (
select /*+ materialize no_merge ordered use_concat use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p6 b , p87 a
where
b.srcblock in (
a.destblock - 1 ,
a.destblock + 7 ,
a.destblock - 9
)
AND a.tst + b.tst <:M
),
p85 as (
select /*+ materialize no_merge ordered use_concat use_hash(a b) */ distinct b.destblock,a.tst+b.tst tst
from p5 b,p86 a
where
b.srcblock in (
a.destblock - 1 ,
a.destblock + 7 ,
a.destblock - 9
)
AND a.tst + b.tst <:M
),
p18 as (
select /*+use_hash(a b) */'Y' f from p14 a,p85 b
where
b.destblock in (
a.destblock + 1 ,
a.destblock - 7 ,
a.destblock + 9
) and b.tst = :M - a.tst
and rownum = 1
)
select nvl(max(f),'N') from p18

复制代码

〇〇 · 发表于 2011-4-12 16:13

nice

rollingpig · 发表于 2011-4-12 16:17

MAX(TST),MIN(TST)
1948,328

[精华] ACM题(#2634 Collecting Stones)

回复 #68 rollingpig 的帖子

浏览过的版块