ChefGame
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, ..., Xksuch 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.
Input
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 Dspace-separated integers, denoting the coordinates of the given lattice points.
Output
For each test case, output the maximal score modulo 747474747.
Constrains
- 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.
Example
Input:
1
3 2
0 0
-1 -1
1 -1
Output:
8
Explanation
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.
-----------------------------------------------------------------editorial----------------------------------------------------------------------------------------
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
The best described in the problem statement.
QUICK EXPLANATION:
It is clear that we have a complete weighted graph where vertices are the points and weight of the edge is the square of the distance between points. The problem asks to find the cycle-free set of edges with maximal product of weights. At first sight it seems to be the maximum spanning tree in this graph. But since some edges can have zero weights we actually should maximize the product of non-zero edges in our spanning tree. Since graph is complete then naive implementation of Prim's algorithm would be the simplest way here.
Note that Prim's algorithm works in O(V * V) time while Kruskal algorithm in O(E * log E) time, where V is the number of vertexes in the graph and E is the number of edges. In our case the graph is complete, so E = V * (V − 1) / 2 and hence Kruskal algorithm is much slower (due to log E factor). It was intended that Kruskal should get TLE, while any implementation of Prim (with precalculating all edges or not) will get AC.
The main bottleneck of the Kruskal algorithm is sorting of edges (not DSU stuff) and in the Prim we have no sorting at all. That is the point.
EXPLANATION:
As noted above we can reformulate the problem as follows - find the spanning tree in constructed graph that has maximum possible product of non-zero edges in it. It is well-known that spanning tree found by general greedy algorithm (like Prim's or Kruskal's) will maximize any symmetric monotone function of edges (I read this remark 10 years ago in
Christofides book and still remember this). The product of non-zero edges is exactly one of such functions since we have no negative edges. Hence well-known algorithms for finding maximum spanning tree will work here.
The implementation of Prim's algorithm suited for this problem is provided below. Once maximum distance between marked and not marked vertexes becomes zero we could break from the cycle. Also we do not create the adjacency matrix and calculate each needed distance on the fly.
And the most important thing is - the squares of distances should be calculated and compared as is, take them modulo 747474747 only when you multiply them to the answer. For example, if we have only two points, and square of distance between them is 747474747 then in the case of taking this distance modulo at the beginning you break from the cycle and the answer will be 1, but the correct answer is 747474747 and you should output 0. The concrete example is
2 3
0 0 0
19265 19189 2849
The output should 0.
And finally the code snippet:
input points // they are numbered from 1 to N
// d[i] is the farthest distance from point i to the vertexes of the tree
fill d[1..N] by zeros // should be 64bit integer type
// vertex is marked if it is in the current tree
fill mark[1..N] by false // so initially tree is empty
mod = 747474747
ans = 1 // could be int
for iter = 1 to N do
j = 0 // will contain the farthest vertex from current tree
for i = 1 to N do
// we update j once we meet not marked vertex with larger distance to the tree
if (not mark[i] and (j = 0 or d[j] < d[i])) then
j=i
mark[j] = true // we add j to the tree
// now we update the answer
// when iter = 1 we create tree of one vertex
// so d[j] does not make sense
if iter > 1 then
if d[j] <= 1 then
break
else
// note that we take d[j] modulo mod
// otherwise 64bit type overflow is possible
ans = d[j] % mod * ans % mod
// now we should update array d[]
// clearly we need to update each d[i] for not marked i
// by distance to j since this is the only new vertex in the tree
for i = 1 to N do
if not mark[i] then
dist = square of distance between a[i] and a[j]
// use 64bit type here but don't use modulo or the order of edges will be broken
d[i] = max(d[i], dist)
=---------------------------------------------code-------------------------------------------------------------
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<cmath>
#include<cstring>
#include<cassert>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
ll read_int(ll mn, ll mx, char next){
int c, fg = 1, res = 0;
c=getchar();
if(c=='-') fg = -1, c = getchar();
assert('0'<=c && c<='9');
res = c - '0';
for(;;){
c = getchar();
if(c==' ' && next=='\n') continue;
if(c=='\r' && next=='\n') continue;
if(c==next) break;
assert(res!=0);
assert('0'<=c && c<='9');
res = res * 10 + (c - '0');
}
res *= fg;
assert(mn<=res && res<=mx);
return res;
}
void read_int_arr(int n, int res[], ll mn, ll mx){
int i;
rep(i,n-1) res[i] = read_int(mn, mx, ' ');
res[n-1] = read_int(mn, mx, '\n');
}
#define M 747474747
int N, D;
int p[6666][5];
// return distance^2 between points i and j
ll dist(int i, int j){
int k; ll res = 0, diff;
rep(k,D){
diff = p[i][k] - p[j][k];
res += diff * diff;
}
return res;
}
int main(){
int T, Nsum = 0;
int i, j, k;
ll res;
int visited[6666];
ll mxdist[6666];
ll mx; int ind;
T = read_int(1, 6666, '\n');
while(T--){
N = read_int(1, 6666, ' ');
D = read_int(1, 5, '\n');
rep(i,N) read_int_arr(D, p[i], -100000000, 100000000);
Nsum += N;
assert(Nsum <= 6666);
// prim with naive implimentation
res = 1;
rep(i,N) visited[i] = 0, mxdist[i] = 0;
visited[0] = 1;
rep(i,N) if(!visited[i]) mxdist[i] = max(mxdist[i], dist(0,i));
for(;;){
ind = -1; mx = 0;
rep(i,N) if(!visited[i] && mx < mxdist[i]) ind = i, mx = mxdist[i];
if(mx==0) break;
res = (res * (mx%M)) % M;
visited[ind] = 1;
rep(i,N) if(!visited[i]) mxdist[i] = max(mxdist[i], dist(ind,i));
}
printf("%d\n",(int)res);
}
assert( scanf("%*c")==EOF );
return 0;
}
--------------------------------------------------spoj similar prob----------------------------------------
DAVIDG - Davids Greed
The King David it’s a particularly miser character. He have all the gold in his kingdom, and never lends a single coin to anyone. Years passed, and the streets in his kingdom, made by his father, King Enrique, started to deteriorate. The villagers couldn’t traffic with their carts without dropping some of their content.
This problem was affecting the merchants, because they were losing food and other stuff that they sell. So they decided to go to the castle and block the entrance, so the king couldn’t get out until he promised that he would restore the streets.
The King, tired by the annoyance of the people, decided to promess to restore the streets of his kingdom, but because he’s too greedy, he will restore only the ones that are important for the city, let’s call them “vital streets”.
The vital streets connect a commercial point A to a commercial point B in the city such that there will never exist 2 ways to go from point A to point B. This is given by some coordinates X and Y, you can assume the commercial point will be a single point in a space.
The original streets, built by King Enrique, connects every point with the other points, so point A it’s connected with point B, C, D, and so on. So restore every street would be too expensive, that’s why King David will restore only the “vital streets”, but he is not really good at this type of calculations, so he need you to write a program that help him out.
The cost of restoring a street is given by its length and some value P, that tell how much cost to restore a single unit of distance. By example, if P = 3, and the distance of points A and B it’s 3.5, then the total cost of restoring that street would be 3.5 * 3. Note: you have to round up the total cost of the street.
Input
The first line of input will consist of an integer T, denoting the number of test cases. Every test case will have by first line 2 integers, N and P, denoting the number of points and the unitary cost. Then N lines follow, every of them having 2 numbers Xi and Yi , denoting the coordinates in the cartesian plane of every commerciant points.
Output
For each test case output a single line containing this: “Scenario #i: j”, where i is the number of the test case, starting in one, and j it’s the minimum cost of restoring the streets, such as the restored streets let the villagers to go from one point to another point. Since this number can be quite large, output j mod 10^9 + 7.
Example
Input:
2
4 1
35 46
29 13
44 0
27 17
3 18
18 0
11 17
2 31
Output:
Scenario #1: 56
Scenario #2: 631
Constraints:
1 ≤ N ≤ 1,000
-1,000 ≤ Xi , Yi ≤ 1,000
1 ≤ P ≤ 1,000
-----------------------------dsu solution but tle-------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define test() int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int p=i;p<n;p++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a) scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a);
#define pl(a) printf("%lld\n",a);
#define pi(a) printf("%d\n",a);
#define pd(a) printf("%lf\n",a);
#define pf(a) printf("%f\n",a);
#include<bits/stdc++.h>
using namespace std;
int rank[10000],parent[100000];
vector<pair<int,int> > graph[10000];
int read_int(){
char r;
bool start=false,neg=false;
int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
int find(int node)
{
if(parent[node]==node)
{
return node;
}
else
find(parent[node]);
}
int merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int tt=1;
test()
{
int n,m;
n=read_int();
m=read_int();
for(int i=0;i<=n+10;i++)
{
rank[i]=0;
parent[i]=i;
}
vector<pair<double,double> > v;
for(int i=0;i<n;i++)
{
int a,b;
a=read_int();
b=read_int();
v.pb(mp(a,b));
}
vector<pair< pair<int,int>,int> > ve;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++ )
{
double p1=v[i].ff-v[j].ff;
double p2=v[i].ss-v[j].ss;
p1=p1*p1;
p2=p2*p2;
double dist=(sqrt(double(p1)+double(p2)));
int dis=ceil(dist*m);
ve.pb(mp(mp(dis,i),j));
}
}
sort(ve.begin(),ve.end());
long long int cost=0;
int mm=ve.size();
for(int i=0;i<mm;i++)
{
int a=ve[i].first.second;
int b=ve[i].second;
if(find(a)!=find(b))
{
merge(a,b);
cost+=ve[i].first.first;
}
}
cout<<"Scenario #"<<tt++<<": "<<cost<<endl;
}
}
