amsen's blog

By amsen, history, 11 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Maybe this comment could be helpful.