http://codeforces.com/blog/entry/70

From Above I Downloaded some of Petr's video.

There is constant buzzing sound in the background (Is it his brainwaves :P ) , I want to Improve the Sound Quality, Is there a simple way .

Or If Anyone has better quality version of that?

And Are there other such tutoring videos available somewhere ?

Each Element lie in range [0,n^100] .

Space : O(n)

The RUBIX Organizing Committee had planned to start publicizing their festival on the 29^th of Jan,2011. Due to a last minute mishap they lost the document which contained the information as to which volunteer would visit which college on what day!
They turned to their God Rubixius to help them out with the planning for the next week. They provide him with the number of volunteers and the maximum number of people each volunteer can attract per day. Being God Rubixius knows how many people will be present at each college each day. Rubixius has cast a spell which puts you in his shoes for this job. You have to help the OC by telling them the maximum number of people they can get each day along with the actual plan.

Input

The first line contains an integer T with the number of test cases. Each test case will have 2 integers N and C representing the number of volunteers and the number of colleges respectively. The next line will have N integers with the maximum each volunteer can attract per day. Then C lines follow each having 6 integers representing the number of people present at that college from Monday to Saturday respectively.

Output

For each case print a line with the maximum number of people the volunteers can get.

Input:
1
3 3
1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Output:
18


I believe that it is NP-Hard .  Can Anyone Throw some light !

I am in 90% sleep state...pardon me but the timing of hacker-cup was not suitable for India , it was at night 2:30 am :( .

Why is it so time taking...

<#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<numeric>
#include<vector>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()
#define sz(a) (a).size()
#define pb push_back

using namespace std;

typedef long long ll;
ll modu = 1000000007;
map <string,ll> mp;
int c=0;
ll f(string s)
{
//cout<<"here:"<<s<<" ";

if(sz(s) == 1) return 0;

if(mp[s]!=0) {return mp[s];}
ll sum = 0;
ll tmp,tmp2;
int arr[2];

arr[0] = 0;
arr[1] = 0;
for(int i = sz(s) ; i >= 2;i--)
{
for(int j = 0; j + i <=sz(s) ; j++)
{
c++;

tmp = 0;
tmp2 = 0;
// int p = 0;
for(int k = j ; k < j + i ; k++)
{
if(s[k] == 'a') { arr[0] = 1;}

if(s[k] == 'b') { arr[1] = 1;}
}
if(arr[0] == 1) {string new_s = s.substr(0,j)+'a'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp = 1 + f(new_s);
}
if(arr[1] == 1){string new_s = s.substr(0,j)+'b'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp2 = 1 + f(s.substr(0,j)+'b'+s.substr(j+i));
}
arr[0] = 0;
arr[1] = 0;

sum =(sum + tmp % modu + tmp2 % modu) % modu;
// mp[s]+=sum;
}
}
mp[s] = sum;
//cout<<mp[s];
return sum;
}


int main()
{
int T;
cin>>T;
string s="aa";
mp[s] = 1;
s="bb";
mp[s] = 1;
s="ab";
mp[s] = 2;
s="ba";
mp[s] = 2;
string S;
while(T--)
{
cin>>S;
c=0;
cout<<(f(S)+1)%1000000007;
cout<<endl;
// cout<<endl<<sz(mp)<<endl;
// cout<<c<<endl;
mp.clear();
}
return 0;
}

why is it exponential  :( :'(  :'(  .

Actually I know why is it exponential, I want to ask, can I change it to polynomial, without changing overall structure of my program.
>

I need to divide a set of players into two teams such that the team is balanced as far as possible .

Balancing is with respect to their skill values.

One of the team must have floor(n/2) players.

I initially thought it to be a NP-Complete problem , but I am now thinking that it a DP problem may be.

Can anyone tell how to solve this question.

Example:

Players: 5

Skill values:

Player 1 : 4

Player 2 : 1

Player 3 : 4

Player 4 : 56

Player 5 : 3

Optimal solution will have two teams of Total Skill values 11 and 57 respectively.

Now Constraints ( These contraints may also be helpful in solving the problems ):

Skill value of each player <= 570

Total Number of players  <  200

----------------------------------------------

Plz tell how to solve , any method You think of as the best  , plz write it .  

Can anyone tell me where to find ..really nice article on it....