Iremia's blog

Why does applying Kuhn's algorithm for each prime not work? Please help , been stuck for a long time.
By Iremia, 3 years ago, In English

In 498C - Массив и операции , 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.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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); }
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing that out, but it still doesn’t work. :(

    → Reply