aviroop123's blog

By aviroop123, history, 5 months ago, In English,

Problem Link : Link

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 ?

Read more »

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

By aviroop123, history, 9 months ago, In English,

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 ?

Read more »

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

By aviroop123, history, 16 months ago, In English,

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.

Read more »

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

By aviroop123, history, 16 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

By aviroop123, history, 19 months ago, In English,

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 - Цветной граф мистера Китаюта
Submission — 36886321

Read more »

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