作者expiate (弯曲屎壳郎)
看板Math
标题[其他] 特殊排序(breadsorting)的理解与一般化
时间Wed Sep 23 09:07:54 2020
这是题目的网址：
https://open.kattis.com/problems/bread
这题目的重点如下：
- 三个相邻的数字可以做旋转，例如3,5,4 -> 4,3,5 -> 5,4,3
- 大小为n的array里面有n个相异的整数，其值为1,2,3,...,n
- 给你一个起始的数列与最终的数列，回答可否藉由旋转来完成转换
EX1:
n: 4
起始：1 3 4 2
最终：4 3 2 1
1 3 4 2
->4 1 3 2
->4 2 1 3
->4 3 2 1 (Possible)
我在网路上搜寻到的解法是，对於 1 2 3 4这个数列，起始与最终转换到1 2 3 4
是否满足某个性质：
对起始与最终数列，分别加总小於目前数值的个数，
其相差如果是偶数则是 possible
(如解释不清楚，可以参照我下面的程式码)
我对这演算法正确性的理解是
- 相异的数，所以两个数的关系不是小於就是大於
- 计算小於的个数等同於计算大於的个数
- 旋转的关系会导致小於个数的变化
- 当3个相邻的数时，我们只要确定相差是2的倍数即可保证可转换
- 一般化来讲，当k个相邻的数时，是否要相差k-1的倍数才可保证能转换?
+ 我是计算关系个数改变来做以上推断
我比较没有信心的部分是这种存在性，看似好像合理但我又不是很确定是否真的有
一系列的步骤可以完成这样的转换。也就是存在反例来打我脸XD
这边不知道有没有人可以理解我的担忧?
我觉得好像还差一个步骤来完成这个一般化证明
先谢谢了
code:
int count(vector<int> &arr, int idx, int n){
int cnt=0;
for(int i=idx+1;i<n;++i)
if(arr[i]<arr[idx])
++cnt;
return cnt;
}
int main(){
int n;
cin >> n;
vector<int> org(n);
vector<int> target(n);
for(int i=0;i<n;++i) cin >> org[i];
for(int i=0;i<n;++i) cin >> target[i];
int res1=0,res2=0;
for(int i=0;i<n;++i){
res1 += count(org,i,n);
res2 += count(target,i,n);
}
if(abs(res1-res2)%2==0)
cout << "Possible" << endl;
else
cout << "Impossible" << endl;
return 0;
}
--
天下英雄出我辈，一入江湖岁月催。
鸿图霸业谈笑间，不胜人生一场醉。
提剑跨骑挥鬼雨，白骨如山鸟惊飞。
尘世如潮人如水，只叹江湖几人回。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 98.207.101.195 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1600823286.A.845.html
1F：推 hwanger : 你对symmetric group和alternative group熟吗 09/23 09:26
2F：→ expiate : 抱歉，我连听都没听过。是代数相关吗? 09/23 09:31
3F：→ hwanger : 对 因为用这两个概念 马上就能验证程式的正确性 09/23 09:43
4F：→ hwanger : 因为A_n是由3-cycle所生成的 所以只要考虑两个 09/23 09:45
5F：→ hwanger : permutation的parity是否一样就可以 09/23 09:47
6F：→ hwanger : 冏 我晚点再看看你是怎麽理解的好了 09/23 09:48
7F：→ hwanger : typo: alternating group 09/23 10:24
8F：→ expiate : 好的，请问有什麽参考资料是我可以开始的? 09/23 10:48
9F：→ expiate : 可以先出一些作业让我先去理解我再跟你讨论好了 09/23 10:52
10F：→ hwanger : 真的? 那先看下面网址(不用管normal subgroup) 09/23 10:59
13F：→ hwanger : 可以先不管证明 理解各个定义 引理 定理想讲什麽就 09/23 11:07
14F：→ hwanger : 好了 09/23 11:07
15F：→ expiate : 好，我理解完会重新编辑我的文章再请你帮我看一下 09/23 11:37
16F：推 hwanger : 冏 没办法完全理解原PO想说的 很抱歉 然後 "- 一般 09/23 14:06
17F：→ hwanger : 化来讲，当k个相邻的数...">>这句话虽然我不是很理 09/23 14:07
18F：→ hwanger : 解 不过我想应该是没有这个结论的 例如n=5时 考虑 09/23 14:09
19F：→ hwanger : Ok 我想错了一些细节 不过应该就是没那个结论 09/23 14:19
20F：→ hwanger : Ok 我补足了一些细节 当n=5 k=4 基本任两种排列是可 09/23 14:36
21F：→ hwanger : 以互相转换的 [因为<(1,2,3,4),(2,3,4,5)>=S_5] 09/23 14:37
22F：→ hwanger : 所以没有那句话的结论 冏 09/23 14:45
23F：→ hwanger : 而[09/23 09:45]要改成A_n是由(1,2,3),(2,3,4),..., 09/23 14:55
24F：→ hwanger : (n-2,n-1,n)所生成的 09/23 14:56
25F：→ hwanger : 更进一步 随便一个n 考虑k=4 也就是我们可以让任意 09/23 15:03
26F：→ hwanger : 相邻四个做循环的话 则我们想要怎麽排就可以怎麽排 09/23 15:04
27F：→ hwanger : [因为<(1,2,3,4),...,(n-3,n-2,n-1,n)> = S_n] 09/23 15:06
28F：→ expiate : 谢谢你的帮忙，那我先学习完你给我的教材我再另外发 09/24 01:19
29F：→ expiate : 文章请教你好了 09/24 01:19