Click here to Skip to main content
15,608,738 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 anlgorithm that could help me solve the following example problem.

First of 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 Algorith in this example should inject a maximum of 3 1s into the list so that every 4th element would contain as fewer 1 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 asnwer 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 aproach that checks for best injections for all injections, meanning that each time i inject i inject at the best possible possition 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.
Gerry Schmitz 21-Dec-21 13:29pm    
If you're wondering how to Insert into a List:
Dave Kreskowiak 21-Dec-21 14:20pm    
Sure there's an algorithm for it. That's the point of the assignment. YOU have to create one.
BillWoodruff 22-Dec-21 4:12am    
Start experimenting and post code here with specific questions.

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

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