0
$\begingroup$

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the minimum amount of elements as possible. Each element can cover an amount of elements to the left (x direction) and an amount of elements to the right direction (y direction) I'm trying to get all of them connected, meaning that if i pick one element z, each pair of adjacent elements i and i+1 should be covered from z.

Let me explain with an example:

I have placed n=7 boxes here (the boxes are i=0,1,2,3,4,5,6)

In each box i have put the range it can cover from the x and y list i provided, for example, in box 0, we can see that it covers element from 0 to 1, box 1 can cover element 0,1,2,3, box 2 can cover from 1-3, etc. example input

The goal is to find the minimum amount of elements in order to cover the entire 1 to n elements.

This is an example:
If n= 7 
x= 0 1 1 2 1 1 1 [how many elements you can cover to the left]
y= 1 2 1 2 1 1 0 [how many elements you can cover to the right]

#as you can see you can cover 1 element to the left from element 2, and 2 elements to the right from element 2

To clarify, the reason it is 0 in the first x element, is because you can cover 0 elements to the left, and 0 in the last y element because you can cover 0 elements to the right. So from each element i, you can cover everything from i-xi and i+yi.

Answer: we could pick elements 2, 4 and 7 to cover all of the 7 elements (there are many other combinations). So the minimum would be 3 which is the right answer for this input

The reason why I dont pick element 2 and 6,(one might think they cover all of them) is because that would leave a gap between element 4 and 5 where they are not connected. So the minimum is not 2, but 3

What algorithm can solve this? I have looked at interval scheduling, as well as vertex cover, but vertex cover would not solve that just because you can cover for example element 6 from element 4, it does not imply vice versa. (if you look at the example) I have looked at dynamic programming and greedy algorithms, but they do not seem to solve the connecting issue, and would give the output of 2 and not 3, so Im a but clueless in how to tackle this so I am hoping that there is someone out there that can help me solve this, any advice, recommendations, youtube clips, pages and such are highly appreciated if you dont know or have the time to help Thank you in advance. If there are any clarifications needed let me know.

A solution i tried: Lets say i merge the two lists x and y to create an upper and lower bound we will get (0,1) (0,3) (1,3) (1,5) (3,5) (4,6) (5,6) meaning that index 0 can cover from 0 to 1, index 1 can cover from 0 to 3 etc. if i start from the left, and pick each square that covers a new element, in this case it would be correct, because it would pick 1,3 and 5. but what if i have the edgecase (0,1) (0,3) (1,3) (1,5) (3,5) (4,6) (0,6) then i would start from the left, and pick 1,3,5, when in fact, the right answer would be to only pick 6 (since it covers all of the elements)

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't understand what "if i pick one element z, each pair of adjacent elements i and i+1 should be covered from z" means. Can you edit your question to rephrase that? I don't know what "covered from z" means. $\endgroup$
    – D.W. ♦
    May 26 at 6:36
  • $\begingroup$ I have provided an example, Im hoping it clarifies the constraints $\endgroup$
    – Ally Zane
    May 27 at 15:29

1 Answer 1

Reset to default
0
$\begingroup$

Create the set of intervals $[3i - 3 \, x[i] - 2, 3 \, 3i + y[i] - 4]$, i.e., the left endpoint of the $i$th interval is $3i - 3 \, x[i]+1$ and the right endpoint is $3i + y[i] - 1$. Now look for a minimal cover of all integers $1,2,3,\dots,3n-4$ using these intervals. THe solution to that will be a solution to your problem as well. You can find the minimal cover very efficiently, in particular in $O(n \log n)$ time, using the method in https://stackoverflow.com/q/293168/781723.

Improve this answer
$\endgroup$
3
  • $\begingroup$ i thought that the left and the right endpoint for each element would be lower endpoint: i-xi and upper point: i+yi? $\endgroup$
    – Ally Zane
    May 26 at 18:35
  • $\begingroup$ @AllyZane, No, that won't meet your requirements. I'm trying to address the requirement you have about overlap between intervals (e.g., in your example about why not pick 2 and 6). That's the reason for the multiply by 3 business. $\endgroup$
    – D.W. ♦
    May 26 at 19:11
  • $\begingroup$ That said, I am not clear on the precise details that requirement. I have asked you to edit your question to state that more clearly, but I haven't seen an edit yet to respond to this request. I would suggest that you first edit the question to state that requirement precisely. Then, work through some examples, both with the formulation you are proposing and with my formulation, and check which ones does what you want. $\endgroup$
    – D.W. ♦
    May 26 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.