![:lol:](./images/smilies/icon_lol.gif)
10034 - Freckles
Moderator: Board moderators
-
- New poster
- Posts: 14
- Joined: Wed Oct 21, 2009 11:04 am
Re: 10034 - Freckles
got AC..didnt commented out freopen and tht ws causing problem.. ![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
-
- New poster
- Posts: 4
- Joined: Wed Nov 04, 2009 6:08 am
10034 WA
i'm getting WA. i can't find out the cause. help please. thanks in advance.
Code: Select all
#include <cstdlib>
#include<stdio.h>
#include<math.h>
using namespace std;
int main() {
int tc, n,i,j,k,count;
float **co,**gm,*nr,*d,res=0;
scanf("%d",&tc);
while(tc--){
scanf("%d",&n);
count=1;
co = new float*[(n + 1)*(3)];
gm = new float*[(n + 2)*(n + 2)];
for (i = 0; i <= n; i++) {
co[i] = new float[2];
gm[i] = new float[n + 1];
}
while(count<=n){
scanf("%f %f", &co[count][0],&co[count][1]);
count++;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
float x=co[i][0]-co[j][0];
float y=co[i][1]-co[j][1];
gm[i][j]=sqrt(x * x + y*y); //x*x+y*y;
}
}
d=new float[n+1];
nr=new float[n+1];
for (i = 2; i <= n; i++) {
nr[i] = 1;
d[i] = gm[1][i];
}
count = 0;
int vnear;
float min;
while (count != n - 1) {
min = 9999;
for (i = 2; i <= n; i++) {
if (0 <= d[i] && d[i] < min) {
min = d[i];
vnear = i;
}
}
d[vnear] = -1;
res+=min;
for (i = 2; i <= n; i++) {
if (d[i] > gm[i][vnear]) {
d[i] = gm[i][vnear];
nr[i] = vnear;
}
}
count++;
}
printf("%.2f\n" ,res);
if(tc>0)
printf("\n");
}
return 0;
}
Sarowar
Re: 10034 WA
- Have you looked at other discussions related to this problem?
- Don't create a new thread for a problem that already exists.
- Try to include the problem name as well in the subject name... instead of 10034 WA, you can use something like 10034 - Freckles.
- Don't create a new thread for a problem that already exists.
- Try to include the problem name as well in the subject name... instead of 10034 WA, you can use something like 10034 - Freckles.
-
- New poster
- Posts: 5
- Joined: Tue Oct 19, 2010 8:07 am
Re: 10034 - Freckles
Despite the fact that the first few posts suggest you need a newline after your last line, UVa has fixed it! Print a blank line *only* between test cases, otherwise you won't get an AC. However, terminating the last line is okay, i.e.
okay >> "0.00\n" << okay
WRONG >> "0.00\n\n" << WRONG
Also, if anybody is wondering, I had the cases of only one point, and I'm not sure if it makes a difference, but I also had a case if they entered 0 points to output 0.
Good luck!
okay >> "0.00\n" << okay
WRONG >> "0.00\n\n" << WRONG
Also, if anybody is wondering, I had the cases of only one point, and I'm not sure if it makes a difference, but I also had a case if they entered 0 points to output 0.
Good luck!
Re: 10034 - Freckles
Hello all, just want to ask - I still got WA for this problem
I think my algo is correct, I just compute the distance between each points and do Prim's algorithm to get the MST.
I'm just confused with the output scenario with that "print blank line" rules.
for this input:
Is this the correct output?
(with a single newline character at the end of output)
I think my algo is correct, I just compute the distance between each points and do Prim's algorithm to get the MST.
I'm just confused with the output scenario with that "print blank line" rules.
for this input:
Code: Select all
3
3
1.0 1.0
2.0 2.0
2.0 4.0
1
1.0 1.0
2
0.0 0.0
2.0 2.0
Code: Select all
3.41
0.00
2.83
Re: 10034 - Freckles
Hello
I've got WA
I've used Kruskal's algorithm.
Here is my solution
It gives same result like a previous post.
I've got WA
I've used Kruskal's algorithm.
Here is my solution
It gives same result like a previous post.
Code: Select all
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
Scanner scanner = new Scanner(reader);
try {
int cases = scanner.nextInt();
for (int i = 0; i < cases; i++) {
int frickles = scanner.nextInt();
double[][] vertexes = new double[frickles][2];
List<Edge> edges = new ArrayList<Edge>();
double previousX = scanner.nextDouble();
double previousY = scanner.nextDouble();
vertexes[0][0] = previousX;
vertexes[0][1] = previousY;
for (int j = 0; j < frickles - 1; j++) {
double x = scanner.nextDouble();
double y = scanner.nextDouble();
for (int k = 0; k <= j; k++) {
double[] vertex = vertexes[k];
edges.add(new Edge(j + 1, k, getLength(x, y, vertex[0], vertex[1])));
}
vertexes[j + 1][0] = x;
vertexes[j + 1][1] = y;
}
Collections.sort(edges);
Set<Integer> visitedVertex = new HashSet<Integer>();
double length = 0;
for (Edge edge : edges) {
if (visitedVertex.contains(edge.start) && visitedVertex.contains(edge.end)) {
continue;
}
visitedVertex.add(edge.start);
visitedVertex.add(edge.end);
length += edge.length;
if (visitedVertex.size() == frickles) {
break;
}
}
writer.write(String.format("%.2f", length));
if (i != cases - 1) {
writer.write("\n\n");
}
}
writer.flush();
} catch (IOException e) {
}
}
private static double getLength(double x, double y, double previousX, double previousY) {
double xLength = Math.abs(x - previousX);
double yLength = Math.abs(y - previousY);
return Math.sqrt(xLength * xLength + yLength * yLength);
}
static class Edge implements Comparable<Edge> {
int start;
int end;
Double length;
Edge(int start, int end, double length) {
this.start = start;
this.end = end;
this.length = length;
}
@Override
public String toString() {
return "Edge{" +
"start=" + start +
", end=" + end +
", length=" + length +
'}';
}
public int compareTo(Edge o) {
return length.compareTo(o.length);
}
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
You didn't property implement Kruskal's algorithm.
Input:Correct output 14.04
Input:
Code: Select all
1
4
1.0 1.0
1.0 2.0
10.0 10.0
10.0 11.0
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 1
- Joined: Fri Jan 04, 2013 3:06 pm
Problem 10034 : Freckles getting WA pls hlp
#include<stdio.h>
#include<math.h>
int root(int v,int p[]){
while(p[v] != v)
{v = p[v];}
return v;
}
void union_ij(int i,int j,int p[]){
if(j > i)
p[j] = i;
else
p = j;
}
int main()
{
int test,n,o,l,i,j,flag;
flag=0;
scanf("%d",&test);
for(o=0;o<test;o++)
{
scanf("%d",&n);
printf("\n");
double x[n],y[n],gra[n][n],weight;;
for(l=0;l<n;l++)
{
scanf("%lf%lf",&x[l],&y[l]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
gra[j]=9999;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
weight=sqrt(pow((x-x[j]),2)+pow((y-y[j]),2));
gra[j]=weight;
gra[j]=weight;
}
//kruskal algorithm
int count,p[n],u, v;
count = 0;
double sum,min;
sum = 0;
for(i = 0; i < n; i++)
{
p = i;
}
while(count < n)
{
min = 9999;
for(i = 0; i < n; i++)
{
for(j = 0;j < n; j++)
{
if(gra[j] < min)
{
min = gra[j];
u = i;
v = j;
}
}
}
if(min != 9999)
{
i = root(u, p);
j = root(v, p);
if (i != j)
{
sum += min;
union_ij(i,j,p);
}
gra[v] = gra[v] = 9999;
}
count++;
}
if (flag == 1)
printf("\n");
flag = 1;
printf("%0.2lf\n",sum);
}
return 0;
}
#include<math.h>
int root(int v,int p[]){
while(p[v] != v)
{v = p[v];}
return v;
}
void union_ij(int i,int j,int p[]){
if(j > i)
p[j] = i;
else
p = j;
}
int main()
{
int test,n,o,l,i,j,flag;
flag=0;
scanf("%d",&test);
for(o=0;o<test;o++)
{
scanf("%d",&n);
printf("\n");
double x[n],y[n],gra[n][n],weight;;
for(l=0;l<n;l++)
{
scanf("%lf%lf",&x[l],&y[l]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
gra[j]=9999;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
weight=sqrt(pow((x-x[j]),2)+pow((y-y[j]),2));
gra[j]=weight;
gra[j]=weight;
}
//kruskal algorithm
int count,p[n],u, v;
count = 0;
double sum,min;
sum = 0;
for(i = 0; i < n; i++)
{
p = i;
}
while(count < n)
{
min = 9999;
for(i = 0; i < n; i++)
{
for(j = 0;j < n; j++)
{
if(gra[j] < min)
{
min = gra[j];
u = i;
v = j;
}
}
}
if(min != 9999)
{
i = root(u, p);
j = root(v, p);
if (i != j)
{
sum += min;
union_ij(i,j,p);
}
gra[v] = gra[v] = 9999;
}
count++;
}
if (flag == 1)
printf("\n");
flag = 1;
printf("%0.2lf\n",sum);
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: Problem 10034 : Freckles getting WA pls hlp
Input:Correct output:
Code: Select all
2
3
1.0 1.0
2.0 2.0
2.0 4.0
3
1.0 1.0
2.0 2.0
2.0 4.0
Code: Select all
3.41
3.41
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 5
- Joined: Tue Mar 12, 2013 12:31 am
Re: 10034 - Freckles
Why wa? I used Kruskal's Mst algo.. I think its presentation error..
Here is my code:
Here is my code:
Code: Select all
AC.
While(1) Return Thanks.. :) ;
Last edited by Top Secret on Thu Mar 14, 2013 11:45 pm, edited 1 time in total.
Re: 10034 - Freckles
Top Secret wrote:Why wa? I used Kruskal's Mst algo.. I think its presentation error..
- Check out the output from your program with the sample case from the problem statement: http://ideone.com/QwUIBZ. It's printing "nan". Chances are this is related to the fact that you don't initialize the sum variable inside your mst function, so it starts out with "garbage". Try to configure your compiler to show you all warnings; it can help you catch this type of bugs.
- I'd suggest you avoid the "float" data type and use "double" instead.
- Take the time to go through the previous messages in this forum thread. There's a couple of posts from Mar 11, 2004, for example, which contain useful test cases.
-
- New poster
- Posts: 5
- Joined: Tue Mar 12, 2013 12:31 am
Re: 10034 - Freckles
WOW!!!!!!!!!!!! You know magic!
I changed float to double & initialized sum = 0 & got AC!!!!
Don't know how to thank you!
& I had tried each and every given test case in this forum. My code gave me the correct outputs for them. So I totally had no idea why I was getting WA.. But now I know...![:)](./images/smilies/icon_smile.gif)
Thanks again..![:)](./images/smilies/icon_smile.gif)
I changed float to double & initialized sum = 0 & got AC!!!!
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
& I had tried each and every given test case in this forum. My code gave me the correct outputs for them. So I totally had no idea why I was getting WA.. But now I know...
![:)](./images/smilies/icon_smile.gif)
Thanks again..
![:)](./images/smilies/icon_smile.gif)
Re: 10034 - Freckles
Code: Select all
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;
#define MAX 101
double freckles[MAX][2];
int u, v, cases;
double mst_cost;
vector<int> pset(1000);
priority_queue< pair< double, pair <double, double> > > edge_list;
double distance(double x1, double y1, double x2, double y2)
{
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
void read_input()
{
scanf("%d", &v);
memset(freckles, 0, sizeof freckles);
for (u = 0; u < v; u++)
{
scanf("%lf %lf", &freckles[u][0], &freckles[u][1]);
if (u == 0) continue;
edge_list.push(make_pair(-distance(freckles[u - 1][0], freckles[u - 1][1],
freckles[u][0], freckles[u][1]),
make_pair(u, u - 1)));
}
edge_list.push(make_pair(-distance(freckles[v - 1][0], freckles[v - 1][1],
freckles[0][0], freckles[0][1]),
make_pair(v - 1, 0)));
}
void init_set(int _size)
{
pset.resize(_size);
int i;
for (i = 0; i < _size; i++)
{
pset[i] = i;
}
}
double find_set(int i)
{
if (pset[i] == i)
{
return i;
}
else
{
return pset[i] = find_set(pset[i]);
}
}
void union_set(int i, int j)
{
pset[find_set(i)] = find_set(j);
}
bool is_same_set(int i, int j)
{
return find_set(i) == find_set(j);
}
int main()
{
scanf("%d\n", &cases);
int i;
for (i = 0; i < cases; i++)
{
read_input();
mst_cost = 0;
init_set(v);
while (!edge_list.empty())
{
pair< double, pair <double, double> > front = edge_list.top();
edge_list.pop();
if (!is_same_set(front.second.first, front.second.second))
{
mst_cost += (-front.first);
union_set(front.second.first, front.second.second);
}
}
if (i == cases - 1)
printf("%0.2lf\n", mst_cost);
else
printf("%0.2lf\n\n", mst_cost);
}
return 0;
}
Code: Select all
9
3
4.0 2.0
2.0 2.0
1.0 1.0
3
1.0 1.0
2.0 2.0
3.0 3.0
3
1.0 1.0
2.0 2.0
2.0 4.0
2
1.0 1.0
2.0 2.0
2
-1.0 -1.0
1.0 -1.0
1
1.0 1.0
2
2.0 2.0
2.0 2.0
4
1.0 1.0
1.0 2.0
10.0 10.0
10.0 11.0
1
1.0 -1.0
Code: Select all
3.41
2.83
3.41
1.41
2.00
0.00
0.00
14.04
0.00
Re: 10034 - Freckles
I found my error, I had to connect ALL dots with all other dots, I was missing some dots.
-
- New poster
- Posts: 48
- Joined: Sat Apr 06, 2013 6:02 pm
Re: 10034 - Freckles
Nice problem... Got ac . I solved this using Prim's algorithm. BUT my runtime is very bad. Any suggestion about optimizing my code will be appreciated. Thanks.