ACM题(#2634 Collecting Stones)

影之哀伤

找PATH的 可否提前计算好。。。

等表和其他参数固定后再运行，来提高效率呢？？？
把大师那个result当已知条件

newkid

PATH太多了，事先算好更不合算。

这个数据是从小到大，如果反过来从终点出发只要1秒多就能找到第一个答案：

WITH d AS (
  SELECT ROWNUM id
        ,CEIL(ROWNUM/8) r
        ,MOD(ROWNUM-1,8)+1 c
        ,ROWNUM val
    FROM DUAL
   CONNECT BY ROWNUM<=64
  )
,t(r,c,val,total,path) AS (
  SELECT r,c,val,val,','||CAST(id AS VARCHAR2(1000)) FROM d WHERE r=8 AND c=8
  UNION ALL
  SELECT d.r,d.c,d.val,d.val+t.total,t.path||','||d.id
    FROM t,d
   WHERE INSTR(t.path||',',','||d.id||',')=0
         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))
         AND d.val+t.total<=:M
         AND (t.r<>1 OR t.c<>1)
  )
SELECT path FROM t WHERE r=1 AND c=1 AND total=:M AND ROWNUM=1;

PATH
---------------------------------
,64,55,62,53,45,37,28,19,10,1

大数相加很快溢出所以能及早中止遍历。

〇〇

我这里第一个数据测的时间和newkid很接近
但题意没有说各个grid的stone有序，因此倒排不能作为优化办法

〇〇

第2个数据，已经运行了5分钟，临时表空间已经自动扩充到2G,还在增长。原题32M内存怎么够？

〇〇

google查到的思路
ID 2634
PROG Collecting Stones
CPLX C
CLS 搜索/暴力
DTL 这道题我是用二分法，先搜前四列，做成有序表。然后在搜完后四列后，二分查找前面的部分就可以了。

〇〇

WITH d AS (
  SELECT ROWNUM id
        ,CEIL(ROWNUM/8) r
        ,MOD(ROWNUM-1,8)+1 c
        ,ROWNUM val
    FROM DUAL
   CONNECT BY ROWNUM<=64
  )
,dl as (select * from d where c<=:n)  
,dr as (select * from d where c>:n)  
,t(r,c,val,total,path) AS (
  SELECT r,c,val,val,','||CAST(id AS VARCHAR2(1000)) FROM d WHERE r=1 AND c=1
  UNION ALL
  SELECT d.r,d.c,d.val,d.val+t.total,t.path||','||d.id
    FROM t,dL d
   WHERE INSTR(t.path||',',','||d.id||',')=0
         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))
         AND d.val+t.total<=:M
         AND (t.r<>8 OR t.c<>:n)
  )
SELECT path FROM t WHERE r=8 AND c=:n AND total=:M and rownum=1;



SQL> exec :m:=394

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\2634

PATH
--------------------------------
,1,9,17,25,33,42,43,51,52,60,61

已用时间:  00: 00: 04.08
SQL> exec :n:=4

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\2634

PATH
--------------------------------
,1,9,17,25,33,41,49,50,58,51,60

已用时间:  00: 00: 00.98
SQL> exec :n:=6

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> @c:\downloads\2634

PATH
--------------------------------
,1,9,17,25,33,41,42,51,52,61,62

已用时间:  00: 00: 10.96
SQL> exec :n:=7

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\2634

PATH
--------------------------------
,1,9,17,25,26,35,43,52,61,62,63

已用时间:  00: 00: 20.62
SQL> exec :n:=8

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> @c:\downloads\2634

PATH
--------------------------------
,1,9,17,18,27,36,44,53,62,63,64

已用时间:  00: 00: 28.04
SQL>

〇〇

把grid看作城市，stone看作里程，这道题就和第3题很像，不过变成给了固定的车费，怎么从起点到终点刚好花完

影之哀伤

问题改成 64个数里凑出来合出指定的值的话，问题是变难还是变简单了？

〇〇

如果没有限制,候选集会更大..

〇〇

SQL> exec :m:=900

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\26345

T.PATH||'*'||T2.PATH
--------------------------------------------------------------------------------------------
,01,02,03,04*13,21,29,37,30,38,46,54,62,63,55,47,39,31,23,15,07,16,24,32,40,48,56,64,

已用时间:  00: 00: 10.71
SQL> exec :m:=980

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> /

T.PATH||'*'||T2.PATH
--------------------------------------------------------------------------------------------
,01,10,19,20*21,29,37,45,53,61,62,54,63,55,47,39,31,23,15,07,08,16,24,32,40,48,56,64,

已用时间:  00: 02: 12.06