15,613,866 members
See more:
I would like to know if there is an algorithm that could help me solve the following example problem.

First off we have a list of 1 and 0:
011001010111 of length 12.

Then we have an x number of 1 to inject anywhere in the list, for instance x=3 (not necessary to inject all 3).

Lastly, we have a number y that checks the list for every y-th element for a 1.

For instance, y=4 which means the program in this example before injections will output 2 as 4th element contains a 0, but both 8th and 12th contain a 1.

The algorithm in this example should inject a maximum of three 1s into the list so that every 4th element would contain as few 1s as possible.

A correct answer for this example could look something like this:

(Injecting into list with first index being 1)

1. Injection at index 7 => list=0110011010111, length=13, output=1.
2. Injection at index 10 => list=01100110110111, length=14, output=1.
3. Injection at index 10 => list=011001101110111, length=15, output=0.

Another correct answer can also look like this:

1. Injection at index 1 => list=1011001010111, length=13, output=2.
2. Injection at index 1 => list=11011001010111, length=14, output=3.
3. Injection at index 1 => list=111011001010111, length=15, output=0.

Lenght=<10000, x=<50, y=<10000

What I have tried:

So far I have tried a simple approach that checks for the best injections for all injections, meaning that each time I inject, I inject at the best possible position that returns the least amount of 1. I was also told that this can be solved using dynamic programming with a matrix of x * (n/y). So if anyone can point me at the right direction or help me understand the implementation using the matrix would much appreciate it.
Posted
Updated 26-Jan-22 13:23pm
v2

## Solution 1

Quote:
I would like to know if there is an algorithm that could help me solve the following example problem.

This problem is furiously looking like a problem from a challenge site. For this kind of problem, the solution is never simple minded or strait forward, the solution is always a unique combination algorithms.
Finding a good enough solution always needs a deep understanding of the problem.
Generally speaking, a vast knowledge of algorithm is almost mandatory.

If no idea, start with a brut force program, make it print every try it does.
Then study the prints to see if program does something stupid where it spend worthless time.
Improve code accordingly and repeat tests.
The key to success is your understanding of the problem.

CPallini 27-Jan-22 2:46am
5.
Patrice T 27-Jan-22 3:11am
Thank you.