monyet's blog

By monyet, history, 8 years ago, In English

Hello, can you give me a hint on how to solve this problem? I read the editorial, but still can not solve it. According to the editorial, we have to "prune the graph". I don't know how to do that. Thanks so much.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By monyet, 10 years ago, In English

Hello, i'm trying to solve this problem http://www.spoj.com/problems/PT07X/. I wrote a brute force algorithm. I was expecting a Time Limit Exceeded response, but I got WA instead. What is wrong with my code? Thanks!

vector<pair<int,int> > edge;
     int n , a , b ,mini;
     
     scanf("%d",&n);
     for (int i = 1; i<=n-1; i++)
     {
         scanf("%d%d",&a,&b);
         a--; b--;
         edge.push_back(make_pair(a,b));
     }
     
     mini = INF;
     for (int mask = 0; mask < (1<<n); mask++)
     {
         bool can = true;
         for (int i = 0 ; i<edge.size(); i++)
         {
             if ( (mask&(1<<edge[i].first))==0 && (mask&(1<<edge[i].second))==0) 
             {
                  can = false;
                  break;
             }
         }
         
         if (can)
         {
             int on = 0;
             for (int i = 0 ; i<n; i++) if ( (mask&(1<<i))!= 0) on++;
             mini = min(mini,on);
         }
     }
     
     printf("%d\n",mini);

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By monyet, 10 years ago, In English

Hello guys, sometimes i'm having trouble proofing my algorithm correctness. I've seen many Editorial where the author make some lemmas and proof their correctness. Is there a book where I can learn something like that? I've read several books this , it doesn't help much.

Thanks guys!

Full text and comments »

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

By monyet, 10 years ago, In English

Hello codeforces fella!

I hope you guys can give me some suggestions.

I am second year CS student in Indonesia. I have wasted lots of my time practicing algorithm in various online judges. I really enjoy doing it, but i don't think competitive programming will give me a job in the future (CMIIW).

Now the question is, is it worth doing it? Or should I just learn something that can give me a job like Web Design etc ?

Full text and comments »

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