### Iremia's blog

By Iremia, 22 months ago,

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

 » 22 months ago, # | ← 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); } 
•  » » 22 months ago, # ^ |   0 Thanks for pointing that out, but it still doesn’t work. :(