### aviroop123's blog

By aviroop123, history, 16 months ago, I'm not able to understand the editorial clearly. I'm stuck in the last part. It says "We should minimize the value of f(a,b) under the constraint that d(x,y) ≤ x*a + y*b + f(a,b) for all 1 ≤ x ≤ A, , 1 ≤ y ≤ B." Why do we have to minimize f(a,b)? Can someone give more mathematical proof or intuition ?

By aviroop123, history, 20 months ago, Brief problem description : Given a permutation of length n <= 12 and a list of m <= n*(n-1)/2 possible swaps, what is the minimum number of swap operations required to change the permutation to an identity permutation ( i.e p_1 = 1, p_2 = 2, ... p_n = n). Here's the problem link : https://wcipeg.com/problem/coci092p5.

The editorial uses A* algorithm with heuristics to solve this problem. I was only able to come up with a 90 pts (here's the code) solution using A*. Can anyone share any idea on how to get 100 pts efficiently ?

By aviroop123, history, 2 years ago, Recently I was trying to solve this problem. Somewhere I had seen that the intended solution uses dp with broken profile. But I had a much simpler solution using MCMF. But the problem with this solution is that negative cycles are getting formed. Is there any way to handle negative cycles in MCMF ? I am not familiar with the MCMF algorithm, so it would be better if someone provides the implementation. Thanks in advance. mcmf, zoj,
By aviroop123, history, 2 years ago, By aviroop123, history, 2 years ago,  