Ohh Thanks… I think you are right… Taking mod will not compare the value of the children correctly… I got my mistake…
such greedy strategies won’t work obviously. try creating a test case yourself. I tried the same approach first but then realize that structure of trees does have significant contribution
Can somebody explain why this soln is getting wrong on 3 cases ?
Submission link - CodeChef: Practical coding for everyone
the approach is exactly as mentioned in editorial
Can someone explain why I am getting wrong answer in task 3 and 6.
I have already tried removing % inf in line 35, but that gives wrong answer for more tasks.
https://www.codechef.com/viewsolution/46608840
I dont know why testcase 3 and 6 and not giving AC, can anyone find the bug ?
If someone can help me find the silly mistake in this submission that would be very helpful.
language - CPP CodeChef: Practical coding for everyone
The code was working partially till here: CodeChef: Practical coding for everyone
UPDATE: found out that accumulate() was the problem but still even after removing all %mod except from the final ans still not getting AC any input would be helpful
Latest submission: CodeChef: Practical coding for everyone
this is the code i wrote for tree house …bot I’m getting wrong and in case 0,1 and 6…can anyone plz tell me whats wrong with my approach…i have used greedy way only…
#include
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int t;
cin>>t;
long long int mod=1e9+7;
while(t>0){
map<int,vector>m;
int n;long long int x;cin>>n>>x;
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
m[a].push_back(b);
}
long long int sum=x;
multimap<long long int,long long int,greater<>>m1; unordered_map<long long int,long long int>m2;
m2[1]=x;
for(auto el1:m){
for(auto el2:el1.second){
// m1[m[el2].size()]=el2;
m1.insert(make_pair(m[el2].size(),el2));
//cout<<m[el2].size()<<" ";
}
// cout<<endl;
int i=1; x=m2[el1.first];
for(auto el3:m1){
long long int g=i*x;
// cout<<"heee "<<" ";
sum=(sum+g+mod)%mod;
m2[el3.second]=g;
i++;
}
m1.clear();
}
cout<<sum<<endl;
t–;}
return 0;
}
Plz plz plz tell me why my first 2 cases are not working
Solution Link: https://www.codechef.com/viewsolution/46614847
Thanks in advance.
Plz help me…
remove mod at line 55 and use mod directly for answer.
1 Like
My approach worked for 8 test sets but failed in 2. Maybe I am leaving any test cases , so if anyone can help me with this please.
Approach => Large subtree , minimum value
For E.g.
If a tree rooted at node u has 3 children , then in one dfs I calculated subtree size of each node and then sorted the nodes in decreasing order of subtree size.
Finally I assigned values to each node starting from the initial value(x) , in the same way as in editorial i.e. x , 2x , 3x , 4x … and so on. In this way within the constraints , I assigned minimum possible value to a node with higher subtree size.
So where I may be wrong ?
Can anyone help me I am getting wa in test case 7. I am not able to find my mistake. I think I did it according to the editorial. Thanks
https://www.codechef.com/viewsolution/46229813
remove mod in line 33 and 34
Hello Leo, please let me know for which test case it is falling
Solution: 46363012 | CodeChef
https://www.codechef.com/viewsolution/46363012
Nice explanation Sir
In your code in line no. 32-35 you shudn’t take modulo there because if the overall exceeds 1e9+7 just assume like it becomes 1e9+8, then at the end of the day u r storing the sum as 2 while there was another sum which is like say 5,then now ur code would prioritise 5 over 2 which is wrong. I hope this helps.
Your corrected AC code:
Summary
#include <bits/stdc++.h>
using namespace std;
#define max(a, b) (a < b ? b : a)
#define min(a, b) ((a > b) ? b : a)
#define mod 1000000007LL
#define FOR(a, c) for (int(a) = 0; (a) < ©; (a)++)
#define FORL(a, b, c) for (int(a) = (b); (a) <= ©; (a)++)
#define FORR(a, b, c) for (int(a) = (b); (a) >= ©; (a)–)
#define endl “\n”
#define INF 1000000000000000003
typedef long long int ll;
typedef vector vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
#define POB pop_back
#define MP make_pair
ll rec(vi A[], ll V[], ll x) {
if(A[x].size() == 0) {
V[x] = 1;
return V[x];
} else {
vector child(A[x].size());
for(ll i=0; i<A[x].size(); i++) {
child[i] = rec(A, V, A[x][i]);
}
sort(child.begin(), child.end(), greater());
ll sum = 0;
ll i = 1;
for(ll y : child) {
y = y;
sum += (i * y);
i++;
}
V[x] = sum + 1;
return V[x];
}
}
void make_dag(vi G[], vi A[], ll x, vector &visit) {
visit[x] = true;
for(ll y : G[x]) {
if(visit[y] == false) {
make_dag(G, A, y, visit);
A[x].push_back(y);
}
}
}
void solve()
{
ll n;
ll x;
cin >> n >> x;
vector A[n+1];
vector G[n+1];
vector visit(n+1, false);
ll V[n+1];
ll u, v;
FOR(i, n-1) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
make_dag(G, A, 1, visit);
rec(A, V, 1);
V[1] = V[1] % mod;
x = x % mod;
ll ans = (V[1] * x) % mod;
ans = ans % mod;
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t–)
{
solve();
}
return 0;
}
what exactly are you doing? if you are sorting nodes by no. of nodes in the subtree or no. of immediate children of the nodes then it won’t work. structure of the tree is crucial. The top two cases are especially countering above mentioned greedy approaches.
Can anyone help me what’s wrong with the code getting WA for last test case…
Please help…
https://www.codechef.com/viewsolution/46634807