My solution is just an optimized version of permutating active tasks and calculating minimum time needed, so it's supposed to work.

The current reference solution returns suboptimal answers in some cases, for example:

1. Wash: meat (takes 2 minutes)
2. Wash: eggs (takes 1 minutes)
3. Peel: eggs (takes 6 minutes)
4. Cut: cheese (takes 2 minutes)
5. Fry: cheese for 13 minutes
6. Grate: cheese (takes 2 minutes)
7. Fry: cheese for 30 minutes
8. Wash: eggs (takes 3 minutes)
9. Wash: eggs (takes 2 minutes)

As shown in the Gantt chart below, the optimal answer is no more than (4) + (5) + (6) + (7) = 47 minutes, while the reference solution returns 48.

The current reference solution returns a clearly incorrect answer in the following test case:

poly1 = [
    (Fraction(-27, 1), Fraction(153, 1)), 
    (Fraction(31, 1), Fraction(70, 1)), 
    (Fraction(156, 1), Fraction(81, 1)), 
    (Fraction(68, 1), Fraction(14, 1)), 
    (Fraction(121, 1), Fraction(-71, 1)), 
    (Fraction(8, 1), Fraction(-29, 1)), 
    (Fraction(-85, 1), Fraction(-93, 1)), 
    (Fraction(-66, 1), Fraction(0, 1)), 
    (Fraction(-176, 1), Fraction(46, 1)), 
    (Fraction(-51, 1), Fraction(61, 1))
]
poly2 = [
    (Fraction(11, 1), Fraction(-47, 1)), 
    (Fraction(-161, 1), Fraction(-100, 1)), 
    (Fraction(-91, 1), Fraction(-4, 1)), 
    (Fraction(-243, 1), Fraction(63, 1)), 
    (Fraction(-42, 1), Fraction(59, 1)), 
    (Fraction(36, 1), Fraction(153, 1)), 
    (Fraction(90, 1), Fraction(54, 1)), 
    (Fraction(290, 1), Fraction(46, 1)), 
    (Fraction(122, 1), Fraction(-11, 1)), 
    (Fraction(168, 1), Fraction(-111, 1))
]

In Fixed Tests - Simple Case - Test 1, I got the following message:

(
    (Fraction(20, 1), Fraction(0, 1)), 
    (Fraction(20, 1), Fraction(11, 1)), 
    (Fraction(30, 1), Fraction(15, 1)), 
    (Fraction(15, 1), Fraction(30, 1)), 
    (Fraction(11, 1), Fraction(20, 1)), 
    (Fraction(0, 1), Fraction(20, 1)), 
    (Fraction(0, 1), Fraction(0, 1))
)
should match
[
    (Fraction(0, 1), Fraction(0, 1)), 
    (Fraction(0, 1), Fraction(20, 1)), 
    (Fraction(11, 1), Fraction(20, 1)), 
    (Fraction(15, 1), Fraction(30, 1)), 
    (Fraction(30, 1), Fraction(15, 1)), 
    (Fraction(20, 1), Fraction(11, 1)), 
    (Fraction(20, 1), Fraction(0, 1))
]

Could you explain why my answer is incorrect? 🤔

Failed to import gmpy2. Raise an issue in the discourse if you think that what you try to import is legit.

I think it would be sufficient to add some of the following test cases to the edge_cases. :)

[49642174589, 193955449959, 126248698889, 796947697, 248436823711, 577556373, 260754049275]

In rare cases (e.g. when n is 936093677463), the reference solution returns clearly wrong answers.

Sure, I'll update it to Python once the improved random tests in C++ are done by the author.

Nope, I will add it if needed.

• Python translation

• performance tag could be used

• Example : all Gaussian primes with norm less than 50 are

  (1, 0), (3, 0), (2, 1), (7, 0), (11, 0), (3, 2), (1, 4), (19, 0), (23, 0), (2, 5), (31, 0), (1, 6), (4, 5), (43, 0), (47, 0)
  

  2 + i, 2 - i, 1 - 2i... satisfy conditions, but choose only one of them.

  It should be

  (1, 1), (1, 2), (2, 1), (3, 0), (2, 3), (3, 2), (1, 4), (4, 1), (2, 5), (5, 2), (1, 6), (6, 1), (4, 5), (5, 4), (7, 0)
  

• When two different Gaussian primes have the same norm, you should specify how to sort them.

Special test cases suggestion:

special_test_cases = [
    2, 4,
    40487, 40487 ** 2, 2 * 40487, 2 * 40487 ** 2,
    6692367337, 6692367337 ** 2, 2 * 6692367337, 2 * 6692367337 ** 2
]

FYI, my $O(n\log p)$ solution passes in 6 to 9 seconds.

Multiplication and division of large integers is not $O(1)$ so your solution is not really linear. :)