An Interesting Problem On Array Conversion [AtCoder]

Revision en1, by rachitiitr, 2017-06-29 21:48:20

Hi CF community,

http://rachitiitr.blogspot.in/2017/06/an-interesting-problem-on-array.html

Continuing my journey of sharing the problems that I really liked, please read the above blog post talking about a problem where you have to convert an array into another given array.

This is a problem I really liked from AGC 16. The editorial mentioned can be overwhelming for some of the beginners, and I tried my best to explain the theory behind the solution.

By this problem, you might also learn a scenario that frequently appears in the world of competitive programming which is the property of graph obtained when edges are directed from a[i] to b[i], where a is an array and b is a permutation of array a.

Overall, I had fun solving this problem and working on the analysis. It will be better if you read my blog + editorial mentioned at AtCoder too.

Tags atcoder, directed graph, hamiltonian

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rachitiitr 2017-06-29 21:48:20 938 Initial revision (published)