2022 PUZZLEUP

newkid

〇〇 发表于 2022-11-28 21:09
把要猜的长方形改为任意4个格，也能用二分法吗

总共有C(25,4)=12650种，即使想分，也十分困难，验证也很困难，就没有趣味性了。

newkid

#7 PAWNS

Pawns will be placed on an 9xA square chess board. For any two columns if the number of rows with exactly one pawn should be at least 5, what can be the maximum number of columns (A) on this board?

Example for three columns:
(Columns a-b, a-c and b-c satisfy the conditions.)

棋子被放置在一个 9xA 方格的棋盘上。如果对于任意两列，至少有五行恰好有一个棋子，则该棋盘的最大列数 (A) 是多少？

三列的示例：（a-b、a-c 和 b-c 列满足条件。）

(图中a列的棋子所在行数为12469，b列1358, C列245789)

newkid

聪明的办法应该是反证法、抽屉原理之类的逻辑推理方法。
笨办法是用图论。棋盘总共9行，每列看作一个二进制数，这个数是 2^9=512 种的其中之一。
要求任何两个列的异或结果中，1的个数>=5。

问题转化为512个顶点的无向图中最大的连通子图有多少个顶点。

构造这个无向图所有的边：
with n as (select level-1 n from dual connect by level<=512)
    ,b as (select power(2,level-1) b from dual connect by level<=9)
select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and bitand(n1.n+n2.n-bitand(n1.n,n2.n*2),b.b)>0
group by n1.n ,n2.n
having count(*)>=5;

无向图的极大团、最大团(Bron-Kerbosch算法):
https://blog.csdn.net/yo_bc/article/details/77453478

〇〇

bitand(n1.n,n2.n*2)为什么要*2

newkid

笔误，括号放错位置了，应该是：
and bitand(n1.n+n2.n-bitand(n1.n,n2.n)*2,b.b)>0
异或公式：
BITXOR(x,y) = BITOR(x,y) - BITAND(x,y) = (x + y) - BITAND(x, y) * 2;

〇〇

如果是每列三行，任意两列和为1的行大于等于二，那么肯定不能有8列，因为全1那列只能与全零或两个零的列组合才能符合要求，所以，有它就没有两个一的列

〇〇

with recursive n as (select i-1 n from generate_series(1,8)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,3)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and xor(n1.n,n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=2)
,t as(select 1 lv,[n1,n2]a from p
union all
select lv+1,a+[n] from t,n where (a[-1],n) in( select (n1,n2) from p q)and(a[-2],n) in( select (n1,n2) from p q)
)
select lv,a from t order by lv;

┌───────┬──────────────┐
│  lv   │      a       │
│ int32 │   int64[]    │
├───────┼──────────────┤
│     1 │ [1, 2]       │
│     1 │ [0, 3]       │
│     1 │ [1, 4]       │
│     1 │ [3, 4]       │
│     1 │ [0, 5]       │
│     1 │ [2, 5]       │
│     1 │ [1, 6]       │
│     1 │ [3, 6]       │
│     1 │ [5, 6]       │
│     1 │ [0, 7]       │
│     1 │ [2, 7]    │
│     1 │ [4, 7]    │
│     1 │ [2, 4]    │
│     1 │ [3, 5]    │
│     1 │ [0, 6]    │
│     1 │ [1, 7]    │
│     2 │ [1, 2, 4]    │
│     2 │ [0, 3, 5]    │
│     2 │ [0, 3, 6]    │
│     2 │ [0, 5, 6]    │
│     2 │ [3, 5, 6]    │
│     2 │ [1, 2, 7]    │
│     2 │ [1, 4, 7]    │
│     2 │ [2, 4, 7]    │
│     3 │ [0, 3, 5, 6] │
│     3 │ [1, 2, 4, 7] │
├───────┴──────────────┤
│  26 rows (20 shown)  │
└──────────────────────┘

〇〇

其实漏写了lv=2时还要判断a[-3]条件，结果刚好满足，但这样写512是不可行的

〇〇

〇〇 发表于 2022-12-4 10:44
其实漏写了lv=2时还要判断a[-3]条件，结果刚好满足，但这样写512是不可行的

postgresql居然支持在递归里写count(*)
with recursive n as (select i-1 n from generate_series(1,8)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,3)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=2)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where a[lv+1]<n and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and n2=n)
)
select lv,a from t order by lv;
lv |     a
----+-----------
  1 | {0,5}
  1 | {1,4}
  1 | {0,3}
  1 | {0,6}
  1 | {2,4}
  1 | {3,4}
  1 | {5,6}
  1 | {2,7}
  1 | {2,5}
  1 | {1,6}
  1 | {0,7}
  1 | {3,5}
  1 | {3,6}
  1 | {1,7}
  1 | {1,2}
  1 | {4,7}
  2 | {0,5,6}
  2 | {1,4,7}
  2 | {0,3,5}
  2 | {0,3,6}
  2 | {2,4,7}
  2 | {3,5,6}
  2 | {1,2,4}
  2 | {1,2,7}
  3 | {0,3,5,6}
  3 | {1,2,4,7}
(26 行记录)

〇〇

6行还行，7行就算不动了
with recursive n as (select i-1 n from generate_series(1,128)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,7)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=4)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where a[lv+1]<n and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and n2=n)
)
--select lv,a from t order by lv;
select max(lv)+1 from t;
~~~~~~~~~~~~~~~~~
Cancel request sent
ERROR:  canceling statement due to user request
Time: 235055.623 ms (03:55.056)

----
with recursive n as (select i-1 n from generate_series(1,64)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,6)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=4)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where a[lv+1]<n and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and n2=n)
)
--select lv,a from t order by lv;
select max(lv)+1 from t;
?column?
----------
        4
(1 行记录)


Time: 4547.475 ms (00:04.547)