Блог пользователя aviroop123

Автор aviroop123, история, 5 лет назад, По-английски

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 ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор aviroop123, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор aviroop123, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор aviroop123, история, 6 лет назад, По-английски
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор aviroop123, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится