### Sereja's blog

By Sereja, history, 6 years ago, translation, Hello CodeForces Community,

I’d like to invite you to CodeChef November Cook-Off at https://www.codechef.com/COOK64.

Time: 22nd November 2015 (2130 hrs) to 23rd November 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK64

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Problem Setter: Sergii Nagin
Russian Translator: Sergii Nagin
Editorialist: Sunny Aggarwal
Problem Tester: Istvan Nagy
Mandarin Translator:: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

It promises to deliver on an interesting set of algorithmic problems with something for all.

Good Luck! Hope to see you participating!!  Comments (7)
 » Just wondering, did authors have linear (n log MOD) solution for the last problem?Ps: you know that your post is marked Russian, don't you?
•  » » Thanks, didn't mentioned this.
•  » » I had only exponential solution with proved worst case :)
•  » » Can you please explain how to solve the last problem? There's no editorial available.
•  » » » I found this formula after simplifying a bit. I'm not sure how to prove it though.First, check some small things like sum of degrees is 2 * (n — 1), and no degree is n or larger. Now, let f[i] be the number of nodes that need to be degree i.Then, the answer is n! * (n-1)! * 2 / (product of f[i]! over all i from 0 to n-1). This can all easily be computed in O(n) time.
 » Auto comment: topic has been translated by Sereja (original revision, translated revision, compare)
»
6 years ago, # |
Rev. 7

I really like problemset :) I solved 1st,2nd and 4th task. I had solution for the third, but it gave WA. Can someoe check my solution? Trees aren't my strong side :)

Here is the code:

# include

using namespace std;

const long long mod=1e9+7;

int n,m,t,x,y; long long ans; long long dp,a;

vector v,g;

void dfs(int par, int tr)

{

for (int i=0;i<v[tr].size();i++)
if (v[tr][i]!=par) dfs(tr,v[tr][i]);

for (int i=1;i<=m;i++)
a[i]=0;
for (int i=1;i<=m;i++)
for (int j=0;j<g[i].size();j++)
a[g[i][j]]=(a[g[i][j]]+dp[tr][i])%mod;

for (int i=1;i<=m;i++)
dp[par][i]=((dp[par][i])*a[i]) % mod;

} int p;

int main()

{

scanf("%d",&t);

for (int i=1;i<=20000;i++) {

p=1;
while (p*p<i)
{

if (i %p==0)

{
g[i].push_back(p);
g[i].push_back(i/p);
}
p++;
}
if (p*p==i) g[i].push_back(p);
}

for (int w=0;w<t;w++) {

scanf("%d%d",&n,&m);

for (int i=1;i<=500;i++)
for (int j=1;j<=20000;j++)
dp[i][j]=1;

for (int i=1;i<=n;i++)
v[i].clear();

for (int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}

dfs(0,1);

ans=0;

for (int i=1;i<=m;i++)
ans=(ans+dp[i])%mod;

printf("%lld\n",ans);

}

return 0; }

I have problem to put link of solution.