1
$\begingroup$

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with

$$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ((a_1,a_2,\ldots,a_n), k) \hfill & \mapsto (b_1,b_2,\ldots,b_n)\\ \end{cases}$$

$f$ satisfies the following constraints:

  1. $(\forall b_{i=1,2,\ldots,n}\in \mathbb{Z})(\exists! a_{j=1,2,\ldots,n}\in \mathbb{Z}): b_i= a_j \pm k$
  2. $b_{\max} - b_{\min} \le a_{\max} - a_{\min}$

The task is to find a function $f$(or an algorithm) that satisfies the listed constraints. Could anyone give some hints how can I deal with this problem?

Examples:

Example 1: $$f((1,7),4)=(5,3)$$ First constraint: $$5 = 1 + 4$$ $$3 = 7 - 4$$

Second constraint: $$5 - 3 \le 7 - 1$$

Example 2: $$f((1,2,3,4,5,6,7),5)=(6,7,\ldots,12)$$ First constraint: $$6 = 1 + 5$$ $$7 = 2 + 5$$ $$\vdots$$ $$12 = 7 + 5$$ Second constraint: $$12 - 6 \le 7 - 1$$


I tried to solve this problem algorithmically. The following is an implementation using JAVA

public class MinDiff 
{
    public static void main(String[] args) 
    {
        int A[] = {1,7};
        int k = 4;
        System.out.println("Input a:=" + Arrays.toString(A) + ", k:=" + k);
        int d = find(A, k);
        System.out.println("Output a´:=" + Arrays.toString(A));
        System.out.println("Maximum difference is " + d);
    }

    private static int find(int a[], int k) 
    {       
        Arrays.sort(a);

        int n = a.length;
        System.out.println("Maximum difference is " + (a[n - 1] - a[0]));

        if (k >= a[n - 1] - a[0])
        {
            for (int i = 0; i < n; i++)
                a[i] += k;
            return a[n - 1] - a[0];
        }

        a[0] = a[0] + k;
        a[n - 1] = a[n - 1] - k;

        int max = Math.max(a[0], a[n - 1]);
        int min = Math.min(a[0], a[n - 1]);

        for (int index = 1; index < n - 1; index++) 
        {
            if (a[index] < min)
                a[index] += k;
            else if (a[index] > max)
                a[index] -= k;
            else if ((a[index] - min) > (max - a[index]))
                a[index] -= k;
            else
                a[index] += k;

            max = Math.max(a[index], max);
            min = Math.min(a[index], min);
        }

        return  max - min;
    }

The above implementation fail to give a solution for the following input: $$a:=(1,2,\ldots,7) \text{ and } k:=5$$

Generally I´m interedted in the following questions: Let $a:=(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n \text{ and } k \in \mathbb{N}^*$

  • What is the minimal distance that can we achieve? Could we answer this question a priori?
  • Could we also a priori answer the following question: Does $k$ lead $a$ to an increase or decrease(the $2^{th}$ constraint)

Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael May 29 '16 at 10:32
  • $\begingroup$ @Raphael What have you tried? I solved a part of the problem algorithmically(I will update my post to publish that). Where did you get stuck? I would mention that in the update. We do not want to just do your (home-)work for you; we want you to gain understanding: If you read my question carefully I did not ask for an answer instead for hints. However, as it is we do not know what your underlying problem is: I clearly defined the problem provided some examples illustrating the inputs and the expected outputs. $\endgroup$ – Ayoub Falah May 29 '16 at 10:50
  • $\begingroup$ 1. Unfortunately, asking for hints doesn't really fix the fundamental issues with such a question. 2. Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – D.W. May 29 '16 at 22:53
  • $\begingroup$ 3. I can't tell what constraint 1 is trying to say. What does the notation $\forall b_{i=1,2,\ldots,n}\in \mathbb{Z}$ mean? I know what the notation $\forall b \in \mathbb{Z}$ means, but I have no idea how to interpret that subscript. Can you rephrase, without using that notation in the subscript? 4. Also, can you elaborate what $\exists!$ means? I can think of two different meanings (there is a single value for $a_j$ that makes the statement valid; or, out of all of $a_1,\dots,a_n$, there is a single $j$ such that $a_j$ makes the statement valid). Please edit to clarify. Thank you! $\endgroup$ – D.W. May 29 '16 at 22:55
  • $\begingroup$ 4. If I understand correctly, there is no $f$ that satisfies all of the constraints. What is the value of $f((1,1,1),42)$ supposed to be? There seems to be no acceptable value for $f$ on this input. What about $f((0,20),10)$? Again, there seems to be no acceptable output for this input. $\endgroup$ – D.W. May 29 '16 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.