Codeforces #264 (Div. 2) C. Gargari and Bishops

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

To find 2 positions such that bishops in these positions cannot attach each other, we have to select 2 coordinates such that sum of x,y(row,column) in one coordinate is even and odd in other one.

Find the sum of primary and secondary diagonal and calculate the max amount of money for each position. After that iterate through each position and find the maximum money,position in even sum index set and odd sum index set.

	#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 secondary[4001];
	ll primary[4001];
	pair<int,int> evenIndex;
	pair<int,int> oddIndex;
	ll value[2];
	int arr[2001][2001];
	//value 0 denotes even
	//value 1 denotes odd
	int main(){
	memset(value,-1,sizeof value);
	int n;
	cin>>n;
	REP(i,n){
	REP(j,n){
	scanf("%d",&arr[i][j]);
	secondary[i+j]+=arr[i][j];
	primary[i-j+n-1]+=arr[i][j];
	}
	}
	ll candidate;
	REP(i,n){
	REP(j,n){
	candidate=secondary[i+j]+primary[i-j+n-1]-arr[i][j];
	if((i+j)&1){
	if(candidate>value[1]){
	value[1]=candidate;
	oddIndex.first=i;
	oddIndex.second=j;
	}
	}
	else{
	if(candidate>value[0]){
	value[0]=candidate;
	evenIndex.first=i;
	evenIndex.second=j;
	}
	}
	}
	}
	cout<<value[0]+value[1]<<endl;
	if(value[0]>value[1]){
	cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<" ";
	cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<endl;
	}
	else{
	cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<" ";
	cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<endl;
	}
	}

view raw Gargari and Bishops.cpp hosted with ❤ by GitHub

Codeforces #296 (Div. 2) B. Error Correct System

problem link – http://codeforces.com/contest/527/problem/B

This problem can be solved correctly if one knows to use the correct datastructure which will give a optimized solution.

here we use a 2D array called sameIndex

This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
if sameIndex[0][1]=1 then it means ‘a’ from String S and ‘b’ from String T are in same index
if sameIndex[1][0]=1 then it means ‘b’ from S and ‘a’ from T are in same index

There are 3 cases to look into

Case 1: perfect swapping pair is found and hamming distance is decremented by 2

Case 2: a swapping fair is found and hamming distance is decremented by 1

Case 3: hamming distance remains the same

These cases are explained in the code comments

	#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;
	int main(){
	int n;
	string str1,str2;
	cin>>n;
	cin>>str1>>str2;
	//This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
	//if sameIndex[0][1]=1 then it means 'a' from String S and 'b' from String T are in same index
	//if sameIndex[1][0]=1 then it means 'b' from S and 'a' from T are in same index
	int sameIndex[26][26]={0};
	//The below array is used to store the indexes of the mismatched characters in string T
	//NOTE: String S and T are represented by str1 and str2 in the code and comments from now on
	int match[26];
	int ham=0;
	int f=0;
	pair<int,int> ans;
	memset(match,-1,sizeof match);
	REP(i,n){
	sameIndex[str1[i]-'a'][str2[i]-'a']=1;
	if(str1[i]!=str2[i]){
	match[str2[i]-'a']=i;
	ham++;
	}
	}
	REP(i,n){
	if(str1[i]!=str2[i]){
	//Case 1
	//If characters str1[i] and str2[i] are different
	//check if character str2[i] in string str1 and str1[i] in string str2 are present in same index
	//if present then the 2 characters can be swapped and thus hamming distance will be decremented by 2
	if(sameIndex[str2[i]-'a'][str1[i]-'a']){
	ham-=2;
	f=1;
	REP(j,n){
	if(str1[j]==str2[i]&&str2[j]==str1[i]){
	ans.first=i+1;
	ans.second=j+1;
	break;
	}
	}
	break;
	}
	}
	}
	if(!f){
	REP(i,n){
	//Case 2
	//check if mismatched character belonging to str1 is present in mismatched character set of str2
	//if present then we can swap str1[i] with the index where str1[i] is present in str2
	if(str1[i]!=str2[i]){
	if(match[str1[i]-'a']!=-1){
	f=1;
	ans.first=i+1;
	ans.second=match[str1[i]-'a']+1;
	ham--;
	break;
	}
	}
	}
	}
	cout<<ham<<endl;
	if(f){
	cout<<ans.first<<" "<<ans.second<<endl;
	}
	else{
	cout<<"-1 -1";
	}
	}

view raw Error Correct System.cpp hosted with ❤ by GitHub