can anyone share correct approach for CodeChef: Practical coding for everyone
Edit: Whoops - wrong Problem - ignore 
was the problem wrong?
No, I originally linked to Share your approach for EXUNE - #4 by ssrivastava990, but then I noticed that that’s for EXUNE not EXUND, so I edited it out of my comment 
1 Like
umm well its kind of greedy like the number of child nodes of a particular node cannot be less than one (unless its a leaf in which case we will never remove its token). So the best case would always be to fill up all the leafs nodes and move up. So whats left will be the answer.
https://www.codechef.com/viewsolution/27251763
here this is my submission link.
3 Likes
I reverse sorted on the basis of no of nodes in each level.why this gives wa?
I used the exact same logic but still got WA in 4 test cases. Can you please tell me a case where I went wrong.
Link to my submission-
https://www.codechef.com/viewsolution/27258800
It doesn’t means the same except in case of binary trees.
like for this it’s not:
5
1 2
1 3
3 4
3 5
1
4 3
1 2
1 3
1 4
here this is where ur code goes wrong and its because u used mx.size()==n-1(remove it and keep track of elements normally ok). And please take care of the time limit, this code might show TLE if the cases are too strong, map has a log(n) complexity.
1 Like
Thanks a lot for looking into my code. Will try to correct it.
Is that the same as finding the number of nodes at distance \leq k from the closest leaf node (considering leaves to be at distance 1)?
Used the same approach of ‘chipping’ up all the unvisited leaves in one operation. I am getting correct answer for all the test cases that I think of, but still getting WA for most of the hidden test cases. Can someone please take a look into it or give me a case where my code fails? My code is here: CodeChef: Practical coding for everyone
Oh no thats not the same because there can be a leaf node directly attacked to root but its possible that root node is never filled so this logic will fail there
1 Like
Here's the implementation of what @newtech66 said
#include <iostream>
#include <vector>
#include <list>
int K;
int result;
std::vector<std::list<int>> adjacency_list;
int dfs_solve (const int& parent, const int& node) {
// initializing stuff
// flag : true => leaf node
// flag : false => non-leaf node
bool flag = true;
int height = 0x7FFFFFFF;
// height of node = 1 + min(height of all children)
for (const auto& _ : adjacency_list[node]) {
if (_ != parent) {
flag = false;
height = std::min(height, dfs_solve(node, _));
}
}
if (flag) {
// leaf node
height = 1;
} else {
// non-leaf node
++height;
}
// if height of node <= K, we chip that node
if (height <= K) {
++result;
}
return height;
}
int main (void) {
int T;
std::cin >> T;
while (T--) {
int N;
std::cin >> N >> K;
// initializing stuff
adjacency_list.clear();
adjacency_list.resize(N + 1);
result = 0;
// inserting into adjacency list
while (--N) {
int u, v;
std::cin >> u >> v;
adjacency_list[u].emplace_back(v);
adjacency_list[v].emplace_back(u);
}
// parent, node
dfs_solve(0, 1);
std::cout << result << std::endl;
}
return 0;
}
Submission link. All WAs. 
This is the reason:
So, we need to do it by checking for the maximum distance from the leaf nodes.
Submission link. All ACs.
Here's the code
#include <iostream>
#include <vector>
#include <list>
int K;
int result;
std::vector<std::list<int>> adjacency_list;
int dfs_solve (const int& parent, const int& node) {
// initializing stuff
// flag : true => leaf node
// flag : false => non-leaf node
bool flag = true;
int height = 0;
// height of node = 1 + max(height of all children)
for (const auto& _ : adjacency_list[node]) {
if (_ != parent) {
flag = false;
height = std::max(height, dfs_solve(node, _));
}
}
if (flag) {
// leaf node
height = 1;
} else {
// non-leaf node
++height;
}
// if height of node <= K, we chip that node
if (height <= K) {
++result;
}
return height;
}
int main (void) {
int T;
std::cin >> T;
while (T--) {
int N;
std::cin >> N >> K;
// initializing stuff
adjacency_list.clear();
adjacency_list.resize(N + 1);
result = 0;
// inserting into adjacency list
while (--N) {
int u, v;
std::cin >> u >> v;
adjacency_list[u].emplace_back(v);
adjacency_list[v].emplace_back(u);
}
// parent, node
dfs_solve(0, 1);
std::cout << result << std::endl;
}
return 0;
}
4 Likes
Yeah I realised, got AC instead by computing distances to farthest leaf node from current node and counting the ones with distance \leq k.
1 Like
Wow, that’s the exact same test case which made me realise that my logic was incorrect.
1 Like
I made a tester to check where my code went wrong by comparing my code with an AC solution. I made it only for small test trees just to check for correctness, so I didn’t care for the complexity of this tester at all. Also, the main motive was to find an incorrect output of my code, so small trees were best suited (as I could check the found case on paper as well).
And it uses UNIX commands, so to run on Windows or other OS platforms, one has to make simple changes in the commands. Otherwise tools like Cygwin or Linux Subsystems would be helpful.
It expects both A and B (executable files) to be in the present working directory.
Also, for languages other than C/C++, one has to change the run commands in the code, it’s very simple.
gen.cpp
/**
*
* Author: Ankush Khanna
*
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
char buf[16];
random_device rng;
while (true) {
ofstream fout("in.txt", ios_base::out);
fout << "1\n";
const int max_nodes = 5; // Maximum value for N
const int k_choice = 2; // Maximum value for K
int n = 2 + rng() % max(max_nodes - 1, 1);
int k = 1 + rng() % min(k_choice, n);
set<pair<int, int>> s;
vector<bool> vis;
vector<vector<int>> g(n + 1, vector<int>());
function<bool(int, int)> dfs = [&](int x, int p) -> bool {
vis[x] = true;
for (int y : g[x]) {
if (!vis[y]) {
if (dfs(y, x)) {
return true;
}
} else if (y != p) {
return true;
}
}
return false;
};
fout << n << ' ' << k << '\n';
for (int i = 1; i < n; i++) {
int u = i + 1;
int v = u;
while (u == v || s.find(make_pair(u, v)) != s.end()) {
v = 1 + rng() % n;
if (u > v) {
swap(u, v);
}
vis.assign(n + 1, false);
if (dfs(u, -1)) {
v = u;
}
}
s.insert(make_pair(u, v));
g[u].push_back(v);
g[v].push_back(u);
fout << u << ' ' << v << '\n';
}
fout.close();
string a = "", b = "";
FILE *fp = popen("./A < in.txt", "r"); // Your Code
if (fp == nullptr) {
cerr << "File Problem at line " << __LINE__ << '\n';
exit(0);
}
while (fgets(buf, sizeof(buf), fp) != nullptr) {
a += buf;
}
pclose(fp);
fp = popen("./B < in.txt", "r"); // Correct Code
if (fp == nullptr) {
cerr << "File Problem at line " << __LINE__ << '\n';
exit(0);
}
while (fgets(buf, sizeof(buf), fp) != nullptr) {
b += buf;
}
pclose(fp);
long aa = stol(a), bb = stol(b);
if (aa != bb) {
cout << "\n Me: " << aa << '\n';
cout << "Them: " << bb << "\n\nCounter Case:\n\n";
if (system("cat in.txt")) {
cerr << "Unexpected Error at line " << __LINE__ << '\n';
exit(0);
}
cout << '\n';
break;
}
}
return 0;
}
1 Like