Click here to Skip to main content
15,613,866 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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.
Updated 26-Jan-22 13:23pm

1 solution

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.
Share this answer
CPallini 27-Jan-22 2:46am    
Patrice T 27-Jan-22 3:11am    
Thank you.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900