Moscow Pre-Finals Workshop 2019. KAIST Contest Problem C

Правка en4, от amsen, 2020-09-12 21:48:31

Hi all!

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


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 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?



  Rev. Язык Кто Когда Δ Комментарий
en4 Английский amsen 2020-09-12 21:48:31 17 Tiny change: 'number of none unit length cycles in' -> 'number of cycles in'
en3 Английский amsen 2020-09-12 21:44:17 22
en2 Английский amsen 2020-09-12 21:37:48 27 Tiny change: '(\n\nIn th' -> '(\n\nIn th'
en1 Английский amsen 2020-09-12 21:34:37 965 Initial revision (published)