Cowntagion(2020 Dev Silver 1)

Problems and Contests
#1

I tried solving this problem(http://usaco.org/index.php?page=viewproblem2&cpid=1062). My approach is basically to DFS through every node and counts the number of nodes it connects to and adds to the total number of days. Here is my code that runs for only the first 3 testcases(meaning that it doesn’t work for cases where all nodes are not attached to the first node).

#include <bits/stdc++.h>
using namespace std;
ifstream fin("x.in");
ofstream fout("x.out");

int n;
vector<int> adj[100002];
bool visited[100002]={false};
int days = 0;

void dfs(int node){
  visited[node] = true;
  // Check if node is 1 to ensure that 1 is not subtracted from nodes being checked 
  if(node==1){
    days+=ceil(log2(adj[node].size()));
  }
  // Subtracts 1 from size to account for the fact we are not counting the previous node it came from
  else{
    days+=ceil(log2(adj[node].size() - 1));
  }
  for(auto u: adj[node]){
    // Make sure we haven't been to the node before
    if(!visited[u]){
      // Make sure that the node we are going to is not a leaf
      if(adj[u].size()>=2) dfs(u);
      // Increment days anyways if the previous if condition is met
      days++;
    }
  }
}

int main(){
  cin>>n;
  for(int i=0; i<n-1; i++){
    int a,b;
    cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1);
  cout<<days;
}

I tried simulating this with another testcase, and it outputs 9 instead of 12

7
1 2
2 3
3 4
3 5
1 6
2 7

Can anyone please help with telling me where my code goes wrong? Thanks

#2

I solved the question and here is the solution with my comments in the solution

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100002];
bool visited[100002]={false};
int days = 0;

void dfs(int node){
  visited[node] = true;
  int children = 0;
  // Count all the children of the current node excluding previous ones
  for(int u : adj[node]) if(!visited[u]) ++children;
  // Solve how many days it takes to get the necessary cows to move forward
  int cows = 1;
  while(cows <= children) cows *= 2, ++days;
  for(auto u: adj[node]){
    // Make sure we haven't been to the node before
    if(!visited[u]){
      // Make sure that the node we are going to is not a leaf
      if(adj[u].size()>=2) dfs(u);
      // Increment days anyways if the previous if condition is met
      days++;
    }
  }
}

int main(){
  cin>>n;
  for(int i=0; i<n-1; i++){
    int a,b;
    cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1);
  cout<<days;
}
#3

If you’ve already generated a small counter-test, you’re expected to figure out why it isn’t working on your own.

2 Likes