Dividing the Students
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In the city of "M", there are N girls who attend a certain high school. Historically, all of the students of this school are divided into two groups, not necessarily equal in size, right before they start to study.
Each girl in the city of "M" has an integer ID number Ai, that somehow corresponds to her interests, ideology and beliefs. Each girl is unique, so each ID is unique as well.
Some of the girls have similar interests. For any pair of girls, say the i-th and the j-th one, we call the value of similarity the number min(AiAj mod (109+7), AjAi mod (109+7)).
The teachers have decided that they want the students in each group to be as diverse as possible. This way they will be encouraged to become acquainted and make friends faster. For this reason they want to divide the students in such a way that the maximal similarity value of any two girls' IDs in the same group is as small as possible.
Please help them and find the minimal possible maximal similarity value of two girls' IDs within a single group after the optimal division.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case starts with a single integer N - the number of students.
Then, there is a line containing N space-separated integers A1, A2, ..., AN - the IDs of the girls.
For each test case output a single line with a single integer - the answer to the problem.
- 1 ≤ T ≤ 1000
- 1 ≤ Ai ≤ 109
Input: 1 4 1 2 1024 1025 Output: 1048576
The first and the fourth girl will form the first group; the second and the third will form the second group.
|Tags||binary, bipartite, easy, graph, ltime18, xcwgf666|
|Time Limit:||1 - 5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.