### aviroop123's blog

By aviroop123, history, 5 years 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 ?

• +1

By aviroop123, history, 5 years 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 ?

• +6

By aviroop123, history, 6 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.

• 0

By aviroop123, history, 6 years ago,
• +16

By aviroop123, history, 6 years ago,

Can someone tell why my submission is giving tle ... I have tried to bring down the complexity by reducing the number of maps and sets used, but it still gives TLE.

Problem — 506D - Mr. Kitayuta's Colorful Graph
Submission — 36886321

• 0