Livu_sz's blog

By Livu_sz, history, 2 days ago, In English

Sorry for making blog here. Actually I asked it as comment in announcement's page( Link ) on codeforces, but unfortunately no one replied.

So I decided to ask the same question as blog.

Can any one please the explain this line of editorial :

Here, if the elements in P are scanned from left to right, there must always be more left elements than right elements. The number of such arrangements corresponds to that of parenthesis sequences.

What I understood is that, lets say we have (1,2),(3,4),(5,6),(7,8) as corresponding (ai and bi).
Permutation : (1,2,4,3,5,6,7,8) have more right elements(2) than left elements(1) in first 3 elements (1,2,4) but still it can be divided it into two sequences A(1,3,5,7) and B(2,4,6,8), but in editorial it is told that it should not be possible ( as per I understood ) .
I know I have understood it wrong.
Anyone who did this problem or got the editorial please explain the line in blue

Editorial link : Link

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

There's a line before that, which says — "There are 2^N ways to “direct” the pairs in P, that is, to decide which of each pair is the left element.". In your example permutation, you have swapped the direction of the pair (3, 4) to (4, 3), so 4 would be considered as the left element, and 3 as the right.