Ctrl+X and CTRL+V question n=9 worst case

Revision en1, by Onur_Ilgaz, 2023-10-04 16:02:59

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).

Tags math, prove, help, book

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Onur_Ilgaz 2023-10-04 20:50:59 37
en1 English Onur_Ilgaz 2023-10-04 16:02:59 1010 Initial revision (published)