Sereja's blog

CodeChef November Cook-Off
By Sereja, history, 9 years ago, translation, In English

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
Contest Admin: Praveen Dhinwa
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!!

  • Vote: I like it
  • +28
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, didn't mentioned this.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had only exponential solution with proved worst case :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how to solve the last problem? There's no editorial available.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by Sereja (original revision, translated revision, compare)

→ Reply
»
9 years ago, # |
← Rev. 7   Vote: I like it -30 Vote: I do not like it

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

include <stdio.h>

include

include

using namespace std;

const long long mod=1e9+7;

int n,m,t,x,y; long long ans; long long dp[600][30000],a[30000];

vector v[1000],g[30000];

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[1][i])%mod;

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

}

return 0; }

I have problem to put link of solution.

→ Reply