Moscow Pre-Finals Workshop 2019. KAIST Contest Problem C

Revision en3, by amsen, 2020-09-12 21:44:17

Hi all!

I was trying to understand tutorial for problem C and I think I find a mistake in it.

tutorial

In the third line it says Observe that flipping the direction of an odd cycle changes the sign of the permutation that is obviously wrong. for example in n = 3 and P = 2, 3, 1 when you flip the directions of edges P become 3, 1, 2 that has the same number of inversions(=2) and it can be proven that the parity of number of inversions depends only on number of none unit length cycles in permutation's graph.

I think the solution is not the way that described in tutorial because tutorial's answer for a triangle is zero but AC solutions print 2 for triangle that is correct.

Can anyone or ko_osaga explain solution or the tutorial?

thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English amsen 2020-09-12 21:48:31 17 Tiny change: 'number of none unit length cycles in' -> 'number of cycles in'
en3 English amsen 2020-09-12 21:44:17 22
en2 English amsen 2020-09-12 21:37:48 27 Tiny change: '(https://ibb.co/GHmb3hR)\n\nIn th' -> '(https://i.imgur.com/OM5tSst.jpg)\n\nIn th'
en1 English amsen 2020-09-12 21:34:37 965 Initial revision (published)