0-1 Knapsack Problem / UVa 10130

It’s a well known greedy algorithm, if you are not known with this algo,

You can go through a tutorial ,here is the link

Click this

If you are from bangladesh-flag-3d-icon-16 ,then you should go to Shafaet vaiya’s blog , click it

Implementation of this algorithm

http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Now  solution of Supersale

 

View Code

#include
using namespace std;

int knapsack(int W,int wt[],int val[],int n)
{
int i,j;
int k[n+1][W+1];
for(int i=0;i<=n;i++)
{
for(int w=0;w<=W;w++)
{
if(i==0 ||w==0)
k[i][w]=0;
else if(wt[i-1]<=w) k[i][w]=max(val[i-1]+k[i-1][w-wt[i-1]],k[i-1][w]); else k[i][w]=k[i-1][w]; }   } return k[n][W];   }   int main() { int t; cin>>t;
while(t–){

int m,W=-1;

cin>>m;
long long res=0;
int wt[m],val[m];
for(int i=0;i<m;i++) cin>>val[i]>>wt[i];
int n=0;
cin>>n;
while(n–)
{

cin>>W;
res+=knapsack(W,wt,val,m);
}

cout<<res<<endl;

}
}

 

  • Same Problem

→  The Knapsack

Large Knapsack

And more

A

 

Advertisements

A New Alphabet

 

Problem Link

Create an array to store the characters &store them

then take input if there is any uppercase ,change the character to lowercase then print the value

 

 

View Code
#include <bits/stdc++.h>
using namespace std;


int main()
{string s;
map<char,string>a;

a['a']="@";
a['b']="8";
a['c']="(";
a['d']="|)";
a['e']="3";
a['f']="#";
a['g']="6";
a['h']="[-]";
a['i']="|";
a['j']="_|";
a['k']="|<";
a['l']="1";


a['m']="[]\\/[]";
a['z']="2";
a['y']="`/";
a['x']="}{";
a['w']="\\/\\/";
a['v']="\\/";
a['u']="|_|";
a['t']="']['";
a['s']="$";
a['r']="|Z";
a['q']="(,)";
a['p']="|D";
a['o']="0";
a['n']="[]\\[]";

while(getline(cin,s)){
int l=s.size();
for(int i=0;i<l;i++)
{if(s[i]>='A' &&s[i]<='Z')
s[i]=s[i]+32;

if(a.count(s[i]))
cout<<a[s[i]];
else cout<<s[i];
}}
	return 0;
}

 

 

ACM

Problem:

HINT:

create two  array sizeof 30 (more than 26);

store the penalty time in one of them and other is used as a visited array

then for right verdict store the submission time & make it visited and if it is wrong add penalty time(20)

then last task to get total time and total solved problems by executing a for loop 0 to 25;

 

View Code

#include <bits/stdc++.h>
using namespace std;
int res[30];
bool rgt[30];
int main() {
int t;
memset(rgt,0,sizeof rgt);
while(1 )
{
cin>>t;
if(t==-1)
break;

char c;
cin>>c;
string s;
cin>>s;
if(s==”right”)
{
res[c-‘A’]+=t;
rgt[c-‘A’]=1;
}
else res[c-‘A’]+=20;

}
long long time=0,solved=0;
for(int i=0;i<26;i++)
if(rgt[i]) {time+=res[i];
solved++;
}
cout<<solved<<” “<<time<<endl;
return 0;
}

 

Stable Marriage

Stable Matching :

Stable marriage simply works on preference like seeking a better opportunities of matching ,

Finding out best choice from many choice can be done with stable marriage ,the working algorithm is

Gale Shapley Algorithm

in youtube,there are many videos,one of them is

https://www.youtube.com/watch?v=Qcv1IqHWAzg

There are some problems on this

One of them Codechef

 

+View Code

/*
Prog : Stable Marriage
User : Avijeet
Lang : C++
*/
const int N=505;
#include<bits/stdc++.h>
int pos[N][N],wP[N][N],mP[N][N],up[N],out[N];
using namespace std;
int main()
{
int i,j,w,m,t;
queue <int > mfree;

cin>>t;
while(t–)
{
int n;
cin>>n;

for(i=1;i<=n;i++) { cin>>w;
for(j=1;j<=n;j++) cin>>wP[w][j];

}
for(i=1;i<=n;i++) { cin>>m;
for(j=1;j<=n;j++) cin>>mP[m][j];

}

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
pos[i][wP[i][j]]=j;
//position of man in PL of each woman
//pos[w][m]=i if wP[w][i]=m
memset(out,0,(n+1)*sizeof(int));

for(i=1;i<=n;i++)
{
mfree.push(i);
up[i]=1;
}

while(!mfree.empty())
{
m=mfree.front();
w=mP[m][up[m]++];

if(out[w]==0)
{
out[w]=m;
mfree.pop();

}
else if(pos[w][m]<pos[w][out[w]])
{
mfree.pop();
mfree.push(out[w]);
out[w]=m;
}
}

for(w =1;w<=n;w++)
cout<<out[w]<<” “<<w<<endl;
}
}

 

1009: Back to Underworld

Problem Link

It is a bfs Problem

 

Try Enough?View Code

#include<bits/stdc++.h>
#define N 20005
using namespace std;
#define ll long long
vectorg[N];
int color[N];
#define pb push_back
#define bl 2
#define rd 1
#define nc 0

int bfs(int src)
{
queueq;
ll blck=0,red=0;
q.push(src);
color[src]=bl;
blck++;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(color[v]==0) { q.push(v); if(color[u]==bl) { color[v]=rd; red++; } else if(color[u]==rd) { color[v]=bl; blck++; } } } } return max(red,blck); } int main() { int t,cs=1,n=0; cin>>t;
while(t–)
{
cin>>n;
for(int i=0;i<N;i++) g[i].clear();
for(int i=0;i<n;i++) {int x,y; cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}

memset(color,0,sizeof color);
ll co=0;
for(int i=0;i<20005;i++)
{
if(!color[i] && !g[i].empty())
co+=bfs(i);
}
cout<<“Case “<<cs++<<“: “<<co<<endl;
}

}

 

1042 – Secret Origins

Problem Link

We know a way to count next number of same number of 1 bit

ll checkfor_same_count_ones(ll n)

{

ll co=0;

while(n)

{

co+=n&1;

n>>=1;  //  n/=2;

}

return co;

But the verdict will TLE ,because timelimit is .5 second;

                                                                 [So how to Solve]

  1.  First find the LSB  [ let store on c= (n & -n) // if n=2   -n =-2
  2.  add with the given number   [r=c+n]
  3. Then Xor it with n
  4. Shift 2 bit right
  5. divide them with (n&-n) and
  6. last of all ,the result found from 3-5 step ,final result will be found by using this result | (c+n)

        Need better  Explanation? 

 

View Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll num_of_same_1_count(ll n)
{
ll c=(n & -n);
ll r=n+c;
return ((r^n)>>2)/c|r;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t,n,cs=1;
cin>>t;
while(t–)
{
cin>>n;

cout<<“Case “<<cs++<<“: “<<num_of_same_1_count(n)<<endl;

}
return 0;
}