There is this question(UVa 11212 — Editing a Book):↵
↵
You have n equal-length paragraphs numbered 1 to n. Now you want to arrange them in the order of 1, 2, . . . , n. With the help of a clipboard, you can easily do this: Ctrl-X (cut) and Ctrl-V (paste) several times. You cannot cut twice before pasting, but you can cut several contiguous paragraphs at the same time — they’ll be pasted in order.↵
↵
I will not spoil the answer in case you want to solve it too. But I need to prove that for n = 9 (btw this is the n limit) maximum possible answer is 5. I suck at math so I cant prove it, could you help me?↵
↵
Try to prove: Worst possible situation is A = {9, 8, 7, 6, 5, 4, 3, 2, 1} (I couldn't x_x)↵
If so, Try to prove: Answer of A before is 5 (I am too skill issue that I couldn't find any answer better than 6)↵
↵
The reason I say it is 5 is the book says it so (Steven Halim, Felix Halim, Suhendry Effendy — Competitive Programming 4 Book 2).
↵
You have n equal-length paragraphs numbered 1 to n. Now you want to arrange them in the order of 1, 2, . . . , n. With the help of a clipboard, you can easily do this: Ctrl-X (cut) and Ctrl-V (paste) several times. You cannot cut twice before pasting, but you can cut several contiguous paragraphs at the same time — they’ll be pasted in order.↵
↵
I will not spoil the answer in case you want to solve it too. But I need to prove that for n = 9 (btw this is the n limit) maximum possible answer is 5. I suck at math so I cant prove it, could you help me?↵
↵
Try to prove: Worst possible situation is A = {9, 8, 7, 6, 5, 4, 3, 2, 1} (I couldn't x_x)↵
If so, Try to prove: Answer of A before is 5 (I am too skill issue that I couldn't find any answer better than 6)↵
↵
The reason I say it is 5 is the book says it so (Steven Halim, Felix Halim, Suhendry Effendy — Competitive Programming 4 Book 2).
