May 2022

[Max0526]

https://research.ibm.com/haifa/ponde...s/May2022.html

[Max0526]

It seems that the May challenge is too easy.
Python produces the first solution for the regular challenge in under a second, and the the first bonus "*" solution in under 3 minutes on one core.

[uau]

Originally Posted by Max0526

It seems that the May challenge is too easy.
Python produces the first solution for the regular challenge in under a second, and the the first bonus "*" solution in under 3 minutes on one core.

Even that is slower than necessary - there's a straightforward O(n²) algorithm.

By the way, the way to present the problem feels slightly weird to me - the introduction about how every size 2n set contains a size n subset with sum divisible by n doesn't seem to have all that much to do with actual problem. The added constraint removes most of the similarity, as there generally isn't a solution any more for arbitrary lists (consider a list starting with a pair of ones and the rest zeros).

[ryanp]

Also feels too simple... my dumb (recursive) Python program is about 15 lines and produces a solution for the first part in a few milliseconds, the second one in 3 seconds.

[Max0526]

Originally Posted by ryanp

Also feels too simple... my dumb (recursive) Python program is about 15 lines and produces a solution for the first part in a few milliseconds, the second one in 3 seconds.

As a proof of concept, I wrote a long one-line solution in Python.
A 300 loop usually guarantees a solution for both (regular and bonus *) challenges.

[SmartMersenne]

Originally Posted by Max0526

As a proof of concept, I wrote a long one-line solution in Python.
A 300 loop usually guarantees a solution for both (regular and bonus *) challenges.

I would love to see that one line after the challenge is over.

[Max0526]

Originally Posted by SmartMersenne

I would love to see that one line after the challenge is over.

Do you want me to drop it via PM?

[Max0526]

The first names are posted, seven of my students among them: https://research.ibm.com/haifa/ponde...s/May2022.html.

[tgan]

Originally Posted by Max0526

The first names are posted, seven of my students among them: https://research.ibm.com/haifa/ponde...s/May2022.html.

That is very good sign that you are excellent professor

[SmartMersenne]

Originally Posted by Max0526

The first names are posted, seven of my students among them: https://research.ibm.com/haifa/ponde...s/May2022.html.

103 solvers!