Help on Moocast

Problems and Contests
#1

Hey guys! It’s my first time on the forum so sorry if I am asking the question incorrectly. I was working through the problem Moocast, when I encountered an error with my code. I don’t know exactly what I’m doing wrong here, so help would be appreciated. I downloaded the test cases from the site and I am failing to diagnose the exact problem, but I think my program can be divided into 3 main sections: the input, the adjacency vector, and the dfs to find the maximum.

I’m sure the input is 100% good due to cout testing, and I’m also fairly sure the dfs algorithm is solid, so I suppose the issue lies with the adjacency vector. Some help would be greatly appreciated!

/*
ID: theparadox
TASK: moocast
LANG: C++                 
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

const int MAXSIZE = 200;

int N;
int x[MAXSIZE];
int y[MAXSIZE];
float power[MAXSIZE];
bool visited[MAXSIZE];
vector<int> adj[MAXSIZE];

//Counts All Nodes Reachable Starting from Base Node
int dfs(int cow){
	int visCount = 1;
	visited[cow] = true;
	for(auto neighbour : adj[cow]){
		if(!visited[neighbour]){
			visCount+= dfs(neighbour);
		}
	}
	return visCount;
}

//Resets Visited Array
void resetVisited(){
	for(int i = 0; i < N; i++){
    	visited[i] = false;
    }
}

//Distance Between Two Cows Calculator
float distance(int x1, int y1, int x2, int y2) { 
    return sqrt(pow(x2 - x1, 2) +  pow(y2 - y1, 2) * 1.0); 
} 

int main() {
    ofstream fout ("moocast.out");
    ifstream fin ("moocast.in");
    fin >> N;
    //Put Info in arrays
    int powerVal;
    int xVal;
    int yVal;
    for(int i = 0; i < N; i++){
    	fin >> xVal;
    	fin >> yVal;
    	fin >> powerVal;
    	x[i] = xVal;
    	y[i] = yVal;
    	power[i] = powerVal;
    }

    //Make Directed Adjacency Vector
    for(int i = 0; i < N; i++){
    	for(int j = i + 1; j < N; j++){
    		if(distance(x[i],y[i],x[j],y[j]) <= power[i]){
    			adj[i].push_back(j);
    		}
    	}
    }
    //Find Maximum Cows Reachable
    int maximum = 0;
    int num;
    for(int i = 0; i < N; i++){
    	//Reset
    	resetVisited();
    	//Find
       	num = dfs(i);
    	if(num > maximum){
    		maximum = num;
    	}
    	//Repeat
    }
    fout << maximum;
    return 0;
}
#2

How does it fail? Runtime error, TLE, or WA?

#3

WA, I’m good on time for all of them, and I am getting test cases 1 and 5 right.

#4

I think I see the problem with your code. It is indeed in generating the adjacency array.

    for(int i = 0; i < N; i++){
    	for(int j = i + 1; j < N; j++){
    		if(distance(x[i],y[i],x[j],y[j]) <= power[i]){
    			adj[i].push_back(j);
    		}
    	}
    }

If, say, 2 could transmit a message to 1, I don’t think that it would be logged in the array because you’re only calculating for cows i + 1 and up.

#5

Ah that makes perfect sense! I’ll give the code a whirl and mark it as a solution if it works. Thank you once again!

#6

It was THAT SIMPLE! Much love, thanks.

1 Like
#7

In the future, please follow the directions here first (in particular, following all of the suggestions in the debugging module).