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

Why does applying Kuhn's algorithm for each prime not work? Please help , been stuck for a long time.
Автор Iremia, 3 года назад, По-английски

In 498C - Array and Operations , I am applying maximum matching using Kuhn's algorithm.

My solution:

I have split the graph into two parts(even and odd). I am using multisets to store the prime factors of all the elements of the array.

We will always divide by primes so for each prime I am building a graph containing only those edges whose vertices contain the current prime. Then using Kuhn algorithm I am finding the match for each vertex and removing the current prime(only 1) for this vertex and its match from their respective multisets and I also increment the answer by 1.Then I repeat this process for the current prime till there are no more matchings and then move to the next prime.

My submission: 126390066

Please give me a counter case or tell me where I am wrong, I will really appreciate it.

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

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Perhaps an error in implementing Kuhn's algorithm is not the reason for the WA.

After the a[i] factorization loop, you are writing:

if(x!=1) f[i].insert(x);

Shouldn't you have added x to the set of primes here as follows:

if (x != 1) { 
   f[i].insert(x), 
   primes.insert(x); }
→ Ответить