Puzzleup 2010 比赛快开始了，大家用SQL解答啊

newkid

原帖由 lastwinner 于 2010-9-16 10:58 发表
我考虑到一种情况，不知对否
假设有一编码c0，按规则翻转后得到集合gc0，gc0中包含c1,c2和其他一些翻转结果，c1不能按规则翻转得到c2
c1和c2分别按规则翻转后得到集合gc1和gc2，gc1和gc2中肯定都包含c0，并且还会包含一些相同的编码，当然剩下的就是不同的编码了

比如c0＝ABCC
c1＝BACC  -- 1,2位反序
c2＝CCBA  -- 1,2,3,4位反序


这时候保留c0，就不如保留c1、c2

——————————————————————————————————————

当然，以上是就个体而言，如果从整体来看，可能选谁都能得到最大的编码数

看不出这个猜测有什么道理？因为你没办法考虑未来所有的翻转。

比如下面这个组合就包含了ABCC，而且达到了最大数：
AACB,ABAC,ABCB,ABCC,ACBA,BABC,BACA,BBCA,BCAB,BCAC,CABB,CABC,CBAA,CBCA,CCAB

newkid

我真是鲁钝！刚才灵光一闪才想到，147楼确实给出了更好的人肉方法。在三个字母组成的编码中，只需考虑ABCC, 其他如ABBC, AABC都是互斥且对称的，只要把总数再乘以3就行了。
至于2个字母的情况，原来速度已经很快了就不再折腾了。

WITH c AS (  ---- 求出所有NUM个不同字符构成的四位编码
   SELECT num,n,POWER(2,ROW_NUMBER() OVER(PARTITION BY num ORDER BY n)) id
     FROM (SELECT 4-NVL(LENGTH(TRANSLATE('ABCD','$'||n,'$')),0) num,n
             FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') n
                     FROM (SELECT CHR(64+ROWNUM) n FROM DUAL CONNECT BY ROWNUM<=4)
                    WHERE LEVEL=4
                    CONNECT BY LEVEL<=4
                   )
           )
     WHERE num<>3 AND TRANSLATE(n,'$'||SUBSTR('ABCD',1,num),'$') IS NULL
           OR num=3 AND REPLACE(REPLACE(n,'A'),'B')='CC'  ---- 当num=3时只需考虑ABCC的组合，其他都是对称且互斥的
    )
,s AS ( ----求出所有发生冲突的编码
SELECT t1.num,t1.id,t1.n,SUM(t2.id) rev_bits  ---- 这些都是不能出现的id, 每个占一位，按照二进制的位求和就得到所有发生冲突的id的一个总集合
  FROM c t1,c t2
WHERE t1.num=t2.num AND
       t2.n IN (t1.n
                --- 两位反序
               ,SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,2)     -- 2134
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,4,1)     -- 1324
               ,SUBSTR(t1.n,1,2)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)     -- 1243
                --- 三位反序
               ,SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)     -- 3214
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)     -- 1432
                --- 四位反序
               ,SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)     -- 4321
               )
GROUP BY t1.num,t1.id,t1.n
)
,com (num,cc) AS (
   SELECT 1,26 FROM DUAL
   UNION ALL
   SELECT num+1,cc*(26-num)/(num+1) FROM com WHERE num<4
   )
,t(num,id,cnt,bits,path) AS ( ---- 递归求出所有不冲突的编码的集合
   SELECT num,id,1,id,n FROM s
   UNION ALL
   SELECT t.num,s.id,t.cnt+1,t.bits+s.id,t.path||','||s.n
     FROM t,s
    WHERE t.num=s.num AND t.id<s.id AND BITAND(t.bits,s.rev_bits)=0  ---- 和所有ID都没有冲突
)
SELECT SUM(DECODE(t2.num,3,3*cnt*cc,cnt*cc))
  FROM (SELECT t.*,ROW_NUMBER() OVER(PARTITION BY num ORDER BY cnt DESC) rn FROM t) t2
      ,com
WHERE t2.rn=1
       AND t2.num=com.num
;


SUM(DECODE(T2.NUM,3,3*CNT*CC,CNT*CC))
-------------------------------------
                               159926

Elapsed: 00:00:00.23

〇〇

２４－〉０．２３ｓ，太厉害

newkid

原帖由 〇〇 于 2010-9-20 14:33 发表
２４－〉０．２３ｓ，太厉害

受海尔兄弟的启发后三个字母的递归深度从15降到5, 所以大有提高。

〇〇

Sum of Differences


We have 20 different positive integers. The sum of the differences of all pairs of integers (differences by subtracting smaller integer from the larger for every pair) is 5000.

What is the maximum possible sum of differences of 15 numbers that remains after the removal of 5 of the original 20.

Example: For A<B<C, the sum of differences is (B-A)+(C-A)+(C-B).
[ You can answer this problem starting from Thursday at 11:00 (GMT) ]

〇〇

设20个数从小到大分别a1 a2 ...a20
5000=(a20-a1)+...(a20-a19)
+ (a19-a1)+..(a19-a18)
+。。。。
因为每个数加同一个数不影响差的总和，因此a1=1

〇〇

5000=a20*19+a19*18 +...+a3*2+a2*1 - a1*19 -a2*18-...-a18*2-a19*1
=a20*19+a19*17+a18*15 -a1*18
要使得15个数的差和最大，尽量把中间的数去掉，留下2头差距大的

newkid

有20个不同的正整数，它们之间两两的差距的总和为5000.
去除其中的5个数，再对剩下15个数的两两之差求和，这个和最大值为多少？

例如，A<B<C, 它们的两两之差再求和 = (B-A)+(C-A)+(C-B)

求出两两之差的公式：

VAR N NUMBER;
EXEC :N:=20;

WITH t AS (
   SELECT LEVEL id,'X'||LEVEL n FROM DUAL CONNECT BY LEVEL<=:N
)
SELECT SUM(DECODE(rn,1,-1,1)) c
      ,DECODE(rn,1,t1.n,t2.n) n
  FROM t t1, t t2, (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=2)
WHERE t1.id<t2.id
GROUP BY DECODE(rn,1,t1.n,t2.n)
ORDER BY TO_NUMBER(SUBSTR(n,2));

    C N   
----- -----
  -19 X1   
  -17 X2   
  -15 X3   
  -13 X4   
  -11 X5   
   -9 X6   
   -7 X7   
   -5 X8   
   -3 X9   
   -1 X10  
    1 X11  
    3 X12  
    5 X13  
    7 X14  
    9 X15  
   11 X16  
   13 X17  
   15 X18  
   17 X19  
   19 X20  

当N=20的时候，这个和的公式为：

S20=19(X20-X1) + 17(X19-X2) + 15(X18-X3) + 13(X17-X4) + 11(X16-X5) + 9(X15-X6) + 7(X14-X7) + 5(X13-X8) + 3(X12-X9) + 1(X11-X10) = 5000

代入N=15, (去掉第16~20)
EXEC :N=15;

执行结果：

    C N
----- ----------------
  -14 X1
  -12 X2
  -10 X3
   -8 X4
   -6 X5
   -4 X6
   -2 X7
    0 X8
    2 X9
    4 X10
    6 X11
    8 X12
   10 X13
   12 X14
   14 X15

S15=14(X15-X1) + 12(X14-X2) + 10(X13-X3) +  8(X12-X4) +  6(X11-X5) + 4(X10-X6) + 2(X9-X7)

为了让这个值保持最大，被减数应该尽可能的大，把公式中的X9~X15替换为X14~X20可得到最大值：
MAX_S15=14(X20-X1) + 12(X19-X2) + 10(X18-X3) +  8(X17-X4) +  6(X16-X5) + 4(X15-X6) + 2(X14-X7)

这是去掉X8~X13的任意五个时的公式，也就是说去掉X8~X13的任意五个，这个和就可以保持最大。

两个公式相减，
S20 - MAX_S15 = 5*((X20-X1) + (X19-X2) + (X18-X3) + (X17-X4) + (X16-X5) + (X15-X6) + (X14-X7) + (X13-X8)) + 3(X12-X9) + 1(X11-X10)

要使得MAX_S15最大则右边必须最小。

假设d10=X20-X1, d9=X19-X2, .....

代入S20公式：
19*d10 + 17*d9 + 15*d8 + 13*d7 + 11*d6 + 9*d5 + 7*d4 + 5*d3 + 3*d2 + 1*d1 = 5000

其中d10>d9>d8>....d1, 均为正整数, 且d10>=19, d9>=17, d8>=15, ... d1>=1。

S20 - MAX_S15 = 5*(d10+d9+d8+d7+d6+d5+d4+d3)+3*d2+d1

找到一组d10,d9,...d1满足=5000的等式，并且让S20 - MAX_S15能保持最小，MAX_S15也能求出来。

到目前为止有没有错误？

[ 本帖最后由 newkid 于 2010-9-22 22:51 编辑 ]

〇〇

想问题睡不着，起来果然看到了newkid的解答...

偶数项的分析和奇数好像不一样
比如3个数，中间那个是无所谓的，因此15个数，实际上是选14个

当5000时，x20的最大值是固定的
=(5000-1^2-3^2-5^2 ...17^2)/19+1

newkid

原帖由 〇〇 于 2010-9-22 23:53 发表
想问题睡不着，起来果然看到了newkid的解答...

偶数项的分析和奇数好像不一样
比如3个数，中间那个是无所谓的，因此15个数，实际上是选14个

当5000时，x20的最大值是固定的
=(5000-1^2-3^2-5^2 ...17^2)/19+1

确实是14个，我上面也说“去掉X8~X13的任意五个”都可以，这六个数都是不包含在MAX_S15公式中的。

我现在已经转换为求满足和=5000的10个d值的组合了，组合数很多，需要再人肉一下。我数学底子不好，目前没想出什么办法。