Only if you have binary operations.

Yeah, practically mine took 2.7 seconds but theoretically it should be 2-3 mins, no ?

about 2-3 mins theoretically, yeah should work. But wasnt expecting this tight. So I did miller rabin factorization.

What factorization method did you guys use in B2 ? Cuz the naive implementation would take 140 * sqrt(B) operations ~1.4 * 1e9 ?

How is this for an idea ?

lets say we find an undirected cycle. that is a->b->c->d and a->e->d. The undirected cycle is a b c d e a. I can convert the flow without changing source to sink flows by making it a->b->c->e->d. and adding the c->d flow to c->e and e->d. This reduced my edge by 1 whilst keeping the same flow. I can do this till I remove all the cycles ?

That is insightful. We also need some kind of randomisation... As the choice can't be greedy based on the val function you gave. maybe choose some top k candidates from these and try all. something like that or do a Monte Carlo tree search with your way of reward. .

Thank you for the tip but I want heuristics of the above problem which is NP hard.

Auto comment: topic has been updated by sharvil_cpp (previous revision, new revision, compare).