## 10720 - Graph Construction

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Can someone show me a graph for the case below?

10 3 3 3 3 3 3 3 3 3 3
(the first number is the number of vertices)
This graph realizes it, for example:

Code: Select all

``````    *---*---*
/ \  |  / \
*---* | *---*
\ /  |  \ /
*---*---*

``````

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 10720 - Graph Construction

Need Help I am getting "Wrong Answer".....

I applied Erdos-Gallis Theorem..

Code: Select all

``````import java.io.*;
import java.util.*;
class IntegerPair implements Comparable {
Integer _first;

public IntegerPair(Integer f) {
_first = f;
}
public int compareTo(Object o) {
return ((IntegerPair )o).first() - this.first();
}
Integer first() { return _first; }
}
public class Main{
public static void main(String[] args)throws IOException {
PrintWriter z = new PrintWriter(System.out);
ArrayList<IntegerPair> q;
String line;
StringTokenizer s = new StringTokenizer(line);
int n = Integer.valueOf(s.nextToken());
q = new ArrayList<IntegerPair>();
//int [] d = new int[s.countTokens()+1];
while(s.hasMoreTokens()){
}
Collections.sort(q);
int k = n;
int sum = 0;
boolean first = true;
int sumA = 0;
boolean aso = true;
for(int i = 1;i<=k;i++){
sumA = sumA + Integer.valueOf(q.get(i).first()+"");
int sumB = 0;
for(int ii = k+1;ii<=n;ii++){
if(aso){
sumA = sumA + Integer.valueOf(q.get(ii).first()+"");
aso = false;
}
sumB = sumB + Math.min(Integer.valueOf(q.get(ii).first()+""), k);
}
sumB = sumB + (k*(k-1));
int cheq = Integer.valueOf(q.get(i).first()+"");
if(cheq>sumB){
first = false;
break;
}
}
if(first && sumA%2==0) z.println("Possible");
else z.println("Not possible");
}
z.flush();
}
}``````
Last edited by raj on Wed Oct 30, 2013 1:42 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10720 - Graph Construction

It should be "Not possible" instead of "Not Possible".
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Wrong Answer: 10720 - Graph Construction

Thanks sir for finding the mistake but still i am getting Wrong Answer

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10720 - Graph Construction

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!