You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFGAME - Editorial

7
1

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Prim's algorithm

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)

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be provided soon.
Tester's solution can be found here.

RELATED PROBLEMS:

SPOJ - DAVIDG - 11443. Davids Greed

This question is marked "community wiki".

asked 15 Apr '13, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138
accept rate: 12%

edited 17 Apr '13, 12:53

I know that won't be a big improvement, but we can use

if d[j] <= 1 then break
(16 Apr '13, 03:07) betlista ♦♦3★

I've also noticed this but decided to stay on "d[j] = 0" version.
But now I see that your version is better since if distances are allowed to be between 0 and 1 then your version is correct but mine not :)
So I've changed the code snippet.

(16 Apr '13, 13:17) anton_lunyov ♦6★

But in this problem d[j] cannot be in interval (0;1), points have integer coordinates. Btw: comparison is wrong >= instead of <=.

(16 Apr '13, 22:37) betlista ♦♦3★
1

Thanks, fixed. If double would be allowed than distance could be any positive real number and only your version is correct since multiplying the answer by number less than 1 will decrease it.

(17 Apr '13, 12:54) anton_lunyov ♦6★
1

Fun fact, modulo 747474747 is not a prime number :)

(17 Apr '13, 19:18) tungnk19934★

Similar Problem:

www.spoj.pl/problems/DAVIDG

link

answered 15 Apr '13, 21:34

dragon52's gravatar image

4★dragon52
12115
accept rate: 0%

Thanks. It has been added.

(15 Apr '13, 21:39) anton_lunyov ♦6★

Hm, I used algorithm for spanning tree and got TLE (tried Java and C++), any idea what is inefficient in my code?

http://www.codechef.com/viewsolution/2007442

link

answered 15 Apr '13, 15:09

betlista's gravatar image

3★betlista ♦♦
16.8k49115224
accept rate: 11%

3

You are using Kruskal algorithm that for complete graph has complexity O(V^2 * log V) (due to sort of edges) and is asymptotically slower than Prim's algorithms.

It was expected that such approach will get TLE.

(15 Apr '13, 15:11) anton_lunyov ♦6★

I see, thanks for your answer ;-)

(15 Apr '13, 16:05) betlista ♦♦3★

Me too used Kruskal's algorithm with ranked-union, path compression, everything!! Only to find later that the sorting of edges is taking too much time :( (The complete solution took ~24 seconds for a large test case, on my local machine.)

Link to Solution: http://www.codechef.com/viewplaintext/2045584

PS: Never thought Prim's algorithm can do the trick!!

link

answered 15 Apr '13, 17:07

tijoforyou's gravatar image

3★tijoforyou
4.1k52364
accept rate: 14%

@tijoforyou same here calculaton of distances and sorting of edges took all the time I was also getting TLE due to the same reason :(

(15 Apr '13, 17:49) amitupadhyay2★

can you plz provide me a case where my solution fails, http://www.codechef.com/viewsolution/2052988

link

answered 15 Apr '13, 15:35

joshi's gravatar image

3★joshi
1
accept rate: 0%

2

1
2 3
0 0 0
19325 19339 149
The answer should be 0 while your answer is 747474747.

(17 Apr '13, 12:56) anton_lunyov ♦6★

thnx a lot :)

(17 Apr '13, 17:52) joshi3★

@anton_lunyov I tried with kruskal and got TLE in edge distance calculation and sorting. I thought of prim's algorithm too but don't you think all the edge distances will have to be calculated in prim's too? :o ... I was getting TLE because for kruskal I calculated distance between every pair of vertices and then sorted according to the distance. Please clear my doubts. and pleasse refer to my solution and if possible tell me the bad places because of which i got TLE. Thanks in advance

link

answered 15 Apr '13, 18:03

amitupadhyay's gravatar image

2★amitupadhyay
1.4k92241
accept rate: 14%

@amitupadhyay the problem is not with filling of the graph (n(n-1)/2 edges). But with the sorting of edges also some over head due to union-find.

I have precalculated all the distance (V^2) than applied prim's.

http://www.codechef.com/viewsolution/2026500

(15 Apr '13, 19:15) nirajs2★

@nirajs got it :( my bad. thanks btw:)

(15 Apr '13, 19:22) amitupadhyay2★

Isn't time complexity for Prims and Kruskals same : O(ElogV) where E = V^2 for complete graph. It may be the case that prims is faster than kruskals because it doesn't require all the edges to be sorted before hand, right?

link

answered 15 Apr '13, 20:06

KK123's gravatar image

3★KK123
11
accept rate: 0%

according to wikipedia, Prim's complexity is O(V^2) - http://en.wikipedia.org/wiki/Prim's_algorithm#Time_complexity

(15 Apr '13, 20:36) betlista ♦♦3★

@betlista : Using binary heap Prim's complexity can be brought down to O(ElogV)

(16 Apr '13, 12:46) KK1233★

I saw that on wikipedia, but when E=V^2, is this better? I don't think so, or I missed something?

(16 Apr '13, 13:28) betlista ♦♦3★

Can delaunay triangulation be used here to bring down the complexity to O(VlogV)???

link

answered 16 Apr '13, 01:28

donofgaya's gravatar image

4★donofgaya
10423
accept rate: 0%

AFAIK O(V * log V) solution exists only in the case of plane (D = 2).

(16 Apr '13, 01:41) anton_lunyov ♦6★

The delaunay triangulation cannot be used for dimensions greater than 3 . And for the higher dimensions the research is still on. Check this wiki page for more information http://en.wikipedia.org/wiki/Delaunay_triangulation#section_2

(16 Apr '13, 13:23) viaan2★

Hi programmers,

I tried to implement Prim's algorithm, but I'm getting WA. I compared the results with my previous Kruskal implementation and I'm getting same result. Is there some corner case, that's not covered by my random tests (or any other bug)?

My submission is here - http://www.codechef.com/viewsolution/2056473

Thanks

link

answered 17 Apr '13, 11:14

betlista's gravatar image

3★betlista ♦♦
16.8k49115224
accept rate: 11%

1

You should take distance modulo only before you multiply it to the answer. Refer to my code snippet in editorial (I've changed it a bit to explain this bug).

(17 Apr '13, 12:41) anton_lunyov ♦6★

Thank you very much that was the problem. Probably I have same bug in my Kruskal implementation so I didn't find it.

(17 Apr '13, 13:10) betlista ♦♦3★

http://ideone.com/Judb8O

can anyone explain NZEC ?

link

answered 17 Apr '13, 11:21

piyushgoyal's gravatar image

2★piyushgoyal
312
accept rate: 0%

Hello @all,

I have tried to implement Prim's Algorithm...but I am getting TLE,I have used a stl::priority queue for the finding the min distance...could you all have a look into my program and tell me where my program is getting slow.

ideone link: http://www.codechef.com/viewsolution/2038046

Thanks in advance.

link

answered 18 Apr '13, 17:45

rahul_nexus's gravatar image

3★rahul_nexus
7741923
accept rate: 13%

Complexity of your solution is O(N^2 * log N).
It is slow in this problem.
Refer to code snippet in editorial.
It contains simple O(N^2) solution without any data structures.

(18 Apr '13, 21:13) anton_lunyov ♦6★

Firstly thanks for the reply,secondly could you please explain me how did you come up with that complexity...actually I thought that my complexity is O(N*log N)..considering the log N was the insertion time in the priority queue..Thanks in advance again...:)

(18 Apr '13, 21:46) rahul_nexus3★
1

At each step of algorithm (N-1 times) for each unvisited vertex you push pair (u, j) to the heap.
So total number of pushes is about N*N/2.
Also you should not take distance modulo MOD when create adjacency matrix.
Please read the editorial carefully (the bold sentence).

(18 Apr '13, 21:49) anton_lunyov ♦6★

Thanks a lot...will keep in mind next time.

(19 Apr '13, 00:09) rahul_nexus3★

can anyone tell where this code fails i have tried many test cases it is giving correct answer but still getting wa on the judge my submission id is : http://www.codechef.com/viewsolution/2060320

link

answered 20 Apr '13, 16:37

pawan55's gravatar image

4★pawan55
02
accept rate: 0%

k+=(a*a) should be k += (long long)a * a
sum=(sum*k)%MOD should be sum = k%MOD * sum % MOD
But most likely after this it will get TLE.

(20 Apr '13, 16:55) anton_lunyov ♦6★

thank you very very much for your help i made the changes and it worked.......got ac after 10 wa

(20 Apr '13, 17:07) pawan554★

Congrats!
You were lucky to pass with O(N^2 * log N) solution which supposed to get TLE in this problem.
This is probably because of own-written heap class.

(20 Apr '13, 17:10) anton_lunyov ♦6★

can you explain how the complexity comes out to be O(N^2 * log N) .as in the while loop i build the heap which is o(n)and this loop will occur n times so overall complexity should be O(n^2)

(20 Apr '13, 17:19) pawan554★

Your solution is quite unclear. But it seems to me that maxheapify has complexity O(log(n/i)) in the worst case. And build call it for all i from 1 to n/2. So build has complexity O(n * log n).

(20 Apr '13, 17:23) anton_lunyov ♦6★

I couldn't determine why this submission of mine was failing. Please help.

http://www.codechef.com/viewsolution/2035885

link

answered 20 Apr '13, 17:30

animan123's gravatar image

3★animan123
1112
accept rate: 0%

1

Read editorial. Your mistakes are mentioned there.

(20 Apr '13, 21:59) anton_lunyov ♦6★

Thank you. AC :)

(21 Apr '13, 12:29) animan1233★

Well I also can't get it right. I always get wrong answer. Could anyone help me? :)

My "solution"

link
This answer is marked "community wiki".

answered 20 Apr '13, 19:26

bigredone's gravatar image

2★bigredone
11
accept rate: 0%

edited 20 Apr '13, 19:50

1

When maksi becomes zero you should break from the cycle.

(20 Apr '13, 22:01) anton_lunyov ♦6★

Well of course :D Thanks Anton!

(20 Apr '13, 22:13) bigredone2★

Hey I have tried implementing the same solution as mentioned in the editorial - http://www.codechef.com/viewsolution/2170014

I am getting WA. Can anyone point out the mistake in this solution?

Thanks.

link

answered 19 May '13, 22:19

codetrash's gravatar image

3★codetrash
163
accept rate: 0%

I would really appreciate someone looking at the solution

(21 May '13, 00:46) codetrash3★

I had a doubt regarding the time complexity of Prim's algorithm. Isn't Prim without a heap and using adjacency list O(V*E) because the outer loop is O(V) and the inner that computes the greedy minimum values O(E).Won't the simple implementation give TLE in this case?

link

answered 12 Jun '13, 19:40

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

Getting WA.But am not able to work out any corner cases.Can somebody give me some test cases.Help?

Code

link

answered 23 Jun '13, 01:15

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

edited 23 Jun '13, 17:42

I am getting WA in my approach for a similar problem DAVIDG on spoj
Can you help me figure out the mistake ?
It is on similar lines. My Code

link

answered 25 Jan '16, 11:42

kk_pheonix's gravatar image

4★kk_pheonix
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×1,831
×50
×15
×14
×4

question asked: 15 Apr '13, 15:00

question was seen: 9,001 times

last updated: 25 Jan '16, 11:42