All submissions for this problem are available.
Everyone knows that ChefLand is the best country in the world and all of its people are the happiest. However, nobody knows their secret of being happy.
Suraj is an Indian scientist and his goal is to research the life of ChefLandian people. He has already arrived in ChefTown, the capital of ChefLand, and met Chef. He promised to reveal their secret to Suraj if he gets maximal score in a special ChefLandian game. The game has following rules:
- In D-dimensional Euclidean space, N lattice points are given. Every pair of points are not connected initially. The points are not guaranteed to be distinct.
- Let (A1, A2, ..., AD) and (B1, B2, ..., BD) be the coordinates of the points A and B respectively, then the distance between A and B is defined as ( (A1−B1)2 + (A2−B2)2 + ... + (AD−BD)2 )1/2.
- The initial Suraj's score is 1.
- Suraj is allowed to take as many turns as he wants.
- In every turn, Suraj can connect an unconnected pair of two given points, if this new connection does not form a cycle. That is, Suraj cannot connect the pair of points A and B, if there exist points X1, X2, ..., Xk such that A connected to X1, X1 connected to X2, X2 connected to X3,..., and Xk connected to B.
- In every time Suraj connects some points, his score is multiplied by the square of the distance between them.
Now Suraj wonders what is the maximal score he can get. Write a program that will find this score. Since this number can be huge you should output it modulo 747474747.
The first line of input contains T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two space-separated-integers N and D. The next N lines contain D space-separated integers, denoting the coordinates of the given lattice points.
For each test case, output the maximal score modulo 747474747.
- 1 ≤ T ≤ 6666
- 1 ≤ N ≤ 6666
- 1 ≤ D ≤ 5
- The absolute value of any integer given in the input does not exceed 100000000 (108).
- The sum of N in one input file does not exceed 6666.
Input: 1 3 2 0 0 -1 -1 1 -1 Output: 8
The distance between the first point and the second point is ((0−(−1))2+(0−(−1))2)1/2 = 21/2.
The distance between the first point and the third point is ((0−1)2+(0−(−1))2)1/2 = 21/2.
The distance between the second point and the third point is (((−1)−1)2+((−1)−(−1))2)1/2 = 2.
One of the optimal ways is that Suraj connects the third and the second points, and then connects the first and the second points. The maximum score is 22 * (21/2)2 = 8.
|Tags||Rubanenko, april13, medium, mst, prim|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.