Codeforces #277 (Div. 2) C. Palindrome Transformation

Problem link -http://codeforces.com/contest/486/problem/C

Logic:

Check the number of characters that need to be changed inorder to make the given string palindrome.let the count be stored in variable ‘diff’.

It is optimal and sufficient to make changes to characters in any one of half of the string.

Lets choose the first half.

Case 1:

p is in first half of the string.

ans=diff+minimum number of steps required to move to all character positions that needs to be changed from position p

Case 2:

p is in 2nd half of the string.

Now reverse the string and make p=n-p+1

ans=diff+minimum number of steps required to move to all character positions that needs to be changed from position p

Thats all !

	#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 main(){
	int n,p;
	string str;
	scanf("%d%d",&n,&p);
	p--;
	cin>>str;
	int firstr;
	firstr=n/2-1;
	int diff=0;
	//maxi - index of the rightmost character that needs to be changed in the first half of the string
	//mini - index of the leftmost character that needs to be changed in the first half of the string
	int mini=99999,maxi=-1;
	if(p>firstr){
	reverse(str.begin(),str.end());
	p=n-1-p;
	}
	REP(i,firstr+1){
	if(str[i]!=str[n-1-i]){
	diff+=min((abs(str[i]-str[n-1-i])),abs(('z'-max(str[i],str[n-1-i]))+min(str[i],str[n-1-i])-'a'+1));
	mini=min(mini,i);
	maxi=max(maxi,i);
	}
	}
	if(maxi>p&&mini<p){
	if(abs(p-maxi)<abs(p-mini)){
	diff+=abs(p-maxi)*2;
	diff+=abs(p-mini);
	}
	else{
	diff+=abs(p-mini)*2;
	diff+=abs(p-maxi);
	}
	}
	else if(maxi>p)
	diff+=abs(p-maxi);
	else if(mini<p)
	diff+=abs(p-mini);
	cout<<diff;
	}

view raw Palindrome Transformation.cpp hosted with ❤ by GitHub

Codeforces #252 (Div.2) C. Valera and Tubes

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

The logic is very simple. Test cases might be misleading. Each tube has to be of length>=2.

So first find the points in zig zag path of the table.(i.e move from left to right and then go the next row and move from right to left and vice versa)

Let the first k-1 tubes be of length 2. Assign 2 points from the path for each tube.

Kth tube(last tube) will have the remaining cells in the zig zag path.

	#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 arr[305][305];
	int visited[305];
	int n,m,k;
	int withinBoundary(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<m)
	return 1;
	else
	return 0;
	}
	int main(){
	cin>>n>>m>>k;
	vector<pair<int,int> >q;
	int dir=1;
	int x=0,y=0;
	q.pb(mp(0,0));
	while(true){
	y+=dir;
	if(y==m){
	dir*=-1;
	y=m-1;
	x++;
	}
	if(y==-1){
	dir*=-1;
	y=0;
	x++;
	}
	if(x==n)
	break;
	q.pb(mp(x,y));
	}
	int j=0;
	REP(i,k-1){
	cout<<"2 ";
	cout<<q[j].first+1<<" "<<q[j].second+1<<" "<<q[j+1].first+1<<" "<<q[j+1].second+1<<endl;
	j+=2;
	}
	cout<<(n*m)-(2*(k-1))<<" ";
	while(j<q.size()){
	cout<<q[j].first+1<<" "<<q[j].second+1<<" ";
	j++;
	}
	return 0;
	}

view raw Valera and Tubes.cpp hosted with ❤ by GitHub