0
$\begingroup$

Suppose the are two lists X,Y each has numbers from 1 to 110 , we are given given a element from X,Y each, then we have to find number of possible pair of factors from X,Y so that the product of each pair is less than the product of given pair. And if we select number from X, then it cannot be used to make pairs with same X value. And if we select number from Y, then it cannot be used to make pairs with same y value. For example I am given 1,4 then I cannot use 1 from X in any pair, Also I cannot use 4 as Y in any pair, And I have to find number of pairs whose product is less than 4 in this case, if we use 2,1 as pair then we cannot use 2 as X or 1 as Y again. I am not able to approach towards the solution. Can anyone help me in doing this?

$\endgroup$
  • $\begingroup$ are you allowed to use linear programming (i.e., a computer ?) $\endgroup$ – Kuifje Aug 19 '19 at 9:50
  • $\begingroup$ yes we can use linear programming $\endgroup$ – Xuji Kide Aug 20 '19 at 12:33
0
$\begingroup$

Let $x_i$ be a binary variable that takes value $1$ if and only if element $i$ from $X$ is selected, and likewise with $y_j$, $Y$.

Let $\hat{x}$ and $\hat{y}$ be the given items.

So you are looking for a pair $(x_i,y_j)$ such that $i \times j \le \hat{x} \times \hat{y}$.

You can minimize a dummy objective function (e.g., $0$) subject to : $$ ix_ij y_j \le \hat{x}\hat{y} \\ \sum_{i, x_i \neq \hat{x} } x_i = 1 \\ \sum_{j, y_j\neq \hat{y} } x_j = 1 \\ x_i,y_j \in \{0,1\} \\ $$

You need to linearize the product for the first constraint. See for example here.

This will give you one pair. Then, iteratively, run the linear program and forbid existing pairs by adding constraints such as $$ \sum_{i\in B_1} x_i + \sum_{i \in B_0} \left( 1-x_i \right )\le |B_1|+|B_0| $$ where $B_1$ is the set of variables that take value $1$ is the solution and $B_0$ is the set of variables that take value $0$.

$\endgroup$

Your Answer

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

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