Codeforces #273 (Div.2) C.Table Decorations

Problem link: http://codeforces.com/problemset/problem/478/C

Logic:

Case 1:

If (number of maximum colored balloon)/2 is greater than or equal to sum of rest of the 2 colored balloons, then we can decorate each table with 2 balloons from maximum colored balloon and 1 balloon from either of the 2 other colored balloons.

Case 2:

If (number of maximum colored balloon)/2 is lesser than the sum of rest of the 2 colored balloons, then maximum number of tables that we can decorate would be (total number of balloons available)/3.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	int main(){
	ll arr[3];
	REP(i,3){
	cin>>arr[i];
	}
	sort(arr,arr+3);
	if(arr[0]+arr[1]<=arr[2]/2){
	cout<<arr[0]+arr[1];
	}
	else{
	cout<<((arr[0]+arr[1]+arr[2])/3);
	}
	}

view raw TableDecorations.cpp hosted with ❤ by GitHub

Codeforces #260(Div 1) A.Boredom

problem link: http://codeforces.com/problemset/problem/455/A

This problem can be solved using dp approach.

Whenever the contraint on n is around 10^5 you have to think in terms of single dimensional recurrence relation.

Let count[i]=number of times i occured in the input array

dp[i]=maximum points that can be obtained by considering elements upto i

There can be 2 possibilities

case 1: i is selected

If you selecting i, then you have to select all such occurences of i to maximize the points. Also element i-1 cannot be selected because it will be eliminated.

So points scored in this case= i*count[i]+dp[i-2]

case 2: i is not selected

If you are not selecting i, then you have to move over to the next element to score points which is i-1 .

So points scored in this case = dp[i-1]

So thus we get the recurrence relation dp[i]=max(dp[i-1],dp[i-2]+count[i]*i)

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 100005
	typedef long long int ll;
	ll dp[MAX];
	ll count1[MAX];
	int main(){
	int n,x;
	cin>>n;
	REP(i,n){
	cin>>x;
	count1[x]++;
	}
	dp[0]=0;
	dp[1]=count1[1];
	for(int i=2;i<MAX;i++){
	dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);
	}
	cout<<dp[MAX-1];
	}

view raw Boredom.cpp hosted with ❤ by GitHub

Codeforces #266 (Div 2) – Number of Ways

Problem link : http://codeforces.com/contest/466/problem/C

Logic:

Let sum of elements in array = S

If S%3==0 then the array cannot be divided into 3 equal parts . So print zero.

Otherwise,

Have a count array where count[i]=number of subarrays in arr[i…n] whose sum is equal to S/3

Now iterate from the first element and add elements to a variable called “temp”

At iteration i, if temp==S/3 then we have found first part of the “3 equal parts array”.count[i+2] will give you the number of ways the rest of the 2 equal parts of the array could be arranged.

The logic here is “if arr[0…i] sums upto S/3 and if arr[i+j…n] sums upto S/3 then inbetween elements arr[i+1…j-1] will also sum upto S/3 ” here j varies from 2 to n-2.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	int arr[1000005];
	int count1[1000005];
	int main(){
	int n;
	cin>>n;
	ll s=0;
	REP(i,n){
	cin>>arr[i];
	s+=arr[i];
	}
	if(s%3!=0){
	cout<<"0";
	return 0;
	}
	ll sum=s/3;
	ll temp=0;
	for(int i=n-1;i>=0;i--){
	temp+=arr[i];
	if(temp==sum){
	count1[i]+=1;
	}
	}
	for(int i=n-2;i>=0;i--){
	count1[i]+=count1[i+1];
	}
	temp=0;
	ll ans=0;
	for(int i=0;i+2<n;i++){
	temp+=arr[i];
	if(temp==sum){
	ans+=count1[i+2];
	}
	}
	cout<<ans;
	}

view raw TheNumberOfWays.cpp hosted with ❤ by GitHub