作者expiate (彎曲屎殼郎)
看板Math
標題[其他] 怎麼證明這樣的排序和輸入一定可行？
時間Thu Sep 17 06:06:33 2020
我在做一道題如下：
https://nus.kattis.com/problems/longswaps
這道題我的作法是先排序然後在跟原來的輸入一個字元一個字元比較
如果不同，就檢查在限制k下能否跟其它字元做交換。
雖然通過測試的case，但我想是否有嚴謹的數學能證明呢？
謝謝了
下面是我的code，希望有幫助
int main(){
string str;
int k;
cin >> str >> k;
string sorted = str;
sort(sorted.begin(),sorted.end());
for(int i=0;i<str.size();++i){
if(str[i]!=sorted[i] && i-k<0 && i+k>=str.size()){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
--
與怪物戰鬥的人，應當小心自己不要成為怪物。
當你遠遠凝視深淵時，深淵也在凝視你。
弗里德里希·威廉·尼采
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.207.101.195 (美國)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1600294001.A.8D5.html
1F：→ hwanger : 看不懂原PO的算法 冏 提供一個 若|s|>=2k 則任意相 09/17 09:41
2F：→ hwanger : 鄰兩個都可以在其他不動的情況下互換 如考慮 09/17 09:44
3F：→ hwanger : (a1,a2,a3,a4, ,2)要換a3,a4 則a1,a3互換 a1,a4互 09/17 09:46
4F：→ hwanger : 換 a1,a3再互換 09/17 09:47
5F：→ hwanger : 但當|s|<2k時 a_{n-k},...,a_k是不能動的 但a1,..., 09/17 09:53
6F：→ hwanger : a_{n-k-1},a_k,a_{k+1},...,an是可以排序的(先把比 09/17 09:55
7F：→ hwanger : 較小的都丟到頭 比較大都丟到尾 再用泡泡) 09/17 09:57
8F：→ hwanger : 所以只要檢查排序前後的子字串a_{n-k},...,a_k是否 09/17 09:58
9F：→ hwanger : 一樣即可 09/17 09:59
10F：→ hwanger : 上面|s|<2k的情況打錯了 比較a_{n-k+1},...,a_k才對 09/17 10:12
※ 編輯: expiate (98.207.101.195 美國), 09/17/2020 11:08:35
11F：→ hwanger : 如果code就是原PO原本的算法 那上面就是證明的大綱 09/17 11:24
12F：→ hwanger : (任意相鄰兩個都可以在其他不動的情況下互換保證了 09/17 11:25
13F：→ hwanger : 泡泡) 09/17 11:25
14F：→ expiate : 請問你|s|是指string長度嗎？s的起始狀態都不會影響 09/17 11:32
15F：→ expiate : 最後的結果嗎？還是你認為|s|>=2k保證可以排序? 09/17 11:34
16F：→ hwanger : |s|是string長度 不是我的符號 是你的網頁裡的符號 09/17 12:31
17F：→ hwanger : |s|>=2k 不論s是何 都可以排序 重點在這個情況 我 09/17 12:36
18F：→ hwanger : 們可以做到任意兩個相鄰位置的字符可以互換而不變 09/17 12:36
19F：→ hwanger : 動其他字符的位置 如此再依Bubble sort即可 09/17 12:36
20F：→ hwanger : 在你的code中 但當|s|>2k時 你for迴圈裡的if條件是 09/17 12:41
21F：→ hwanger : 永不滿足的唷 09/17 12:41
22F：推 hwanger : typo: |s|>=2k 09/17 12:48
23F：→ expiate : 我想我可以理解，那數學上的證明就這樣解釋即可嗎？ 09/17 13:07
24F：→ hwanger : Lemma: Assume |s|>=2k. Then we can exchange the 09/17 13:08
25F：→ hwanger : characters at i-th and (i+1)th positions without 09/17 13:09
26F：→ hwanger : change the positions of other characters. 09/17 13:09
27F：→ hwanger : Proof: Assume the string is "(a1)(a2)...(an)". 09/17 13:09
28F：→ hwanger : Case 1: If i<k, then consider 09/17 13:10
29F：→ hwanger : swap(ai,an)→swap(a{i+1},an)→swap(ai,an) 09/17 13:11
30F：→ hwanger : Case 2: If i>k, then consider 09/17 13:11
31F：→ hwanger : swap(ai,a1)→swap(a{i+1},a1)→swap(ai,a1) 09/17 13:11
32F：→ hwanger : Case 3: If i=k, then consider 09/17 13:12
33F：→ hwanger : swap(a{k+1},a1)→swap(a1,an)→swap(ak,an) 09/17 13:13
34F：→ hwanger : →swap(a1,an)→swap(a{k+1},a1) 09/17 13:13
35F：→ hwanger : 這樣有一點程式基礎的人都可以理解 對數學而言稍微 09/17 13:14
36F：→ hwanger : 可以接受 如果要全部轉成數學語言的也是可以 09/17 13:15
37F：→ hwanger : 讓(a1,a2,...,an)為一個1到26的有限序列 考慮所有的 09/17 13:17
38F：→ hwanger : permutation σ使得(a_σ(1),...,a_σ(n))為遞增 09/17 13:19
39F：→ hwanger : 收集所有這樣的σ的集合稱作S 並令G為symmetric 09/17 13:22
40F：→ hwanger : group S_n的子群 G:=< (i,j) : |i-j|>=k > 則問題變 09/17 13:24
41F：→ hwanger : 成問S和G的交集是否非空 而證明這個問題的想法基本 09/17 13:25
42F：→ hwanger : 上就和一開始提到的想法一樣 此時swap的角色就是 09/17 13:26
43F：→ hwanger : symmetric group裡的transposition 09/17 13:27
44F：→ hwanger : 而上面的Lemma基本上就是說G包含(1,2),(2,3),..., 09/17 13:30
45F：→ hwanger : (n-1,n) 所以G就是S_n 自然而然S交G非空 09/17 13:32
46F：→ hwanger : 而對於n<2k 也是一樣轉換過來即可 09/17 13:34
47F：→ hwanger : 實際上在些情形下 G是由(1,2),(2,3),..,(n-k-1,n-k) 09/17 13:36
48F：→ hwanger : (k+1,k+2),...,(n-1,n)和(1,n)所生成的 也就是G是 09/17 13:37
49F：→ hwanger : {1,2,...,n-k,k+1,k+2,...,n}的permuation group 09/17 13:39
50F：→ hwanger : 此時S交G非空意味著存在一個σ在S中 使得σ(i)=i 對 09/17 13:42
51F：→ hwanger : 於所有i = n-k+1,...,k 09/17 13:43
52F：→ hwanger : 最後這些討論只是為了嚴謹而存在 沒有給出任何新知 09/17 13:55
53F：→ hwanger : 識唷 冏 09/17 13:56
54F：→ expiate : 非常感謝大大詳細的解說，您總是這麼熱心回答大家 09/18 01:30
55F：→ expiate : 的問題。再次感恩 09/18 01:30
56F：推 wohtp : 補充一下，s < 2k 就一定存在做不到的case。這樣加 09/18 03:42
57F：→ wohtp : 起來才算完整解答原po的問題。 09/18 03:42
58F：→ expiate : 也感謝上面大大，真的謝謝你們撥冗回答問題 09/18 04:15