作者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/m.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