Mohammad Erfan Hossain's Blog

Waking up brain Solution uva id : erfan05 Accepted Time : 0.000 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<set> #include<map> using namespace std; typedef set<char> set_char; typedef map<char, set_char> map_char_set_char; typedef map_char_set_char::iterator map_char_set_char_iterator; typedef set_char::iterator set_char_iterator; int main(){ map_char_set_char mymap; set_char_iterator sit,it; map_char_set_char_iterator mit; set_char life,life_progress; string str; char ch1, ch2; int i, n, year, row; while (cin >> n >> row){ cin >> str; life.clear(); life_progress.clear(); mymap.clear(); life.insert(str[0]); life.insert(str[1]); life.insert(str[2]); for (i = 0; i < row; i++){ cin >> str; ch1 = str[0]; ch2 = str[1]; sit = life.find(ch1); if (sit == life.end()){ mit = mymap.find(ch1); if (mit == mymap....

  Matrix Transpose Solution uva id : erfan05 Accepted Time : 0.000 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> #include<set> #include<string> using namespace std; typedef vector<int> vector_int; typedef map<int, vector_int> map_int_vector_int; int main(){ freopen("input.txt", "r", stdin); map_int_vector_int index_map,value_map; vector_int index, value; int i, j, m, n, val, pos, x; while (cin >> m >> n){ index_map.clear(); value_map.clear(); for (i = 1; i <= n; i++){ vector_int v1,v2; index_map[i] = v1; value_map[i] = v2; } for (i = 1; i <= m; i++){ cin >> x; if (x == 0) continue; index.clear(); for (j = 1; j <= x; j++){ cin >> pos; index_map[pos].push_back(i); index.push_back(pos); } for (j = 0; j < x; ...

The Forrest for the Trees  #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> #include<set> #include<string> using namespace std; typedef vector<char> vector_char; typedef map<char, vector_char> map_vector_char; typedef set<char> set_char; typedef map_vector_char::iterator map_vector_char_iterator; typedef set_char::iterator set_char_iterator; int main(){ freopen("input.txt", "r", stdin); int i,test,forest,acorn; string str; char ch1,ch2; map_vector_char mymap; map_vector_char_iterator mit; set_char myset; set_char_iterator sit; queue<char> q; cin >> test; getchar(); while (test--){ mymap.clear(); while (true){ getline(cin, str); if (str[0] == '*') break; ch1 = str[1]; ch2 = str[3]; mit = mymap.find(ch1); if (mit == mymap.end()){ vector_c...

uva 11503 Virtual Friends #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<map> #include<string> using namespace std; map<string, int> mymap; map<string, int> ::iterator mit; int val[100005], parent[100005]; int findParent(int x){ if (parent[x] == x) return x; else return findParent(parent[x]); } int main(){ int i, x, y, n, test; string str1, str2; cin >> test; while (test--){ cin >> n; for (i = 0; i < 100005; i++){ parent[i] = i; val[i] = 1; } mymap.clear(); for (i = 0; i < n; i++){ cin >> str1 >> str2; mit = mymap.find(str1); if (mit == mymap.end()){ x = mymap.size(); mymap[str1] = x; } else{ x = mit->second; } mit = mymap.find(str2); if (mit == mymap.end()){ y = mymap.size(); mymap[str2] = y; } else{ y = mit->second; } x = findParent(x); y = findParent(y); if (...

uva - 11995 I Can Guess the Data Structure! #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<queue> #include<vector> #include<functional> #include<stack> using namespace std; int main(){ int arr[3]; stack<int> st; queue<int> q; priority_queue<int> pq; int i, z, n, x, y; while (cin >> n){ arr[0] = arr[1] = arr[2] = 0; while (!st.empty()) st.pop(); while (!q.empty()) q.pop(); while (!pq.empty()) pq.pop(); for (i = 0; i < n; i++){ cin >> x >> y; if (x == 1){ if (arr[0] != 2) st.push(y); if (arr[1] != 2) q.push(y); if (arr[2] != 2) pq.push(y); } else{ if (!q.empty() && arr[1] != 2){ z = q.front(); if (z == y) arr[1] = 1; else arr[1] = 2; q.pop(); } else{ arr[1] = 2; } if (!st.empty() && arr[0] != 2){ z = st.top(); ...

uva - 540 Team Queue Solution uva id: erfan05 Accepted Time: 0.070 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<map> #include<algorithm> #include<queue> #include<string> using namespace std; int arr[1000000], task_value[1000]; int main(){ map<int, queue<int>> mymap; map<int, queue<int>>::iterator mit; map<int, int> task_value_map; int  n, x, i, team, max_value, y, kase=1; string str; while (cin >> team){ if (team == 0) break; cout << "Scenario #" << kase++ << endl; for (i = 1; i <= team; i++){ cin >> n; while (n--){ cin >> x; arr[x] = i; } } max_value = 1; fill(task_value, task_value + team + 1, 0); mymap.clear(); while (cin >> str){ if (str[0] == 'E'){ cin >> x; y = arr[x]; if (task_value[y] == 0){ task_value[y] = max_value; queue...

uva - 10194 - Football (aka Soccer) Solution #include<iostream> #include<string> #include<vector> #include<algorithm> #include<map> #include<string.h> #include<stdio.h> using namespace std; class Team{ public: string name; int b, c, d, e, f, g, h, i; Team(){ b = c = d = e = f = g = h = i = 0; } }; void split_string(string &str, string delimiter, vector<string> &result){ string temp,temp2; temp.resize(str.length()); copy(str.begin(), str.end(),temp.begin()); int pos; while (true){ if (temp.length() == 0) break; pos = temp.find(delimiter); if (pos == -1){ result.push_back(temp); break; } temp2 = temp.substr(0, pos); if (temp2.length()!=0) result.push_back(temp2); temp = temp.substr(pos + delimiter.length()); } } int string_to_int(string str){ int i, sum = 0, len = str.length(),mul=1; for (i = len - 1; i >= 0; i--){ sum += (str[i] - 48)*mul; ...

Algorithm   :  Binary Search #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <vector> #include <stdio.h> using namespace std; class Car{ public: string name; long low_cost; long high_cost; }; bool car_sort_with_low_cost(Car *c1, Car *c2){ if (c1->low_cost < c2->low_cost) return true; return false; } vector<Car*> vec; void car_binary_search(int start, int end, int val, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; int val1 = vec[mid]->low_cost; int val2 = vec[mid+1]->low_cost; if (val > val1 && val <= val2){ index = mid; return; } if (val2 == val){ car_binary_search(mid + 1, end, val, index); return; } if (val1 == val){ index = mid; return; } if (val1>val){ car_binary_search(start, mid,val,index); return; } if (val2 > ...

Simple dynamic problem!!! -- Take a 2D array size [105][105] -- calculate all set of product and store in array for future use. -- First fill diagonal element with input array elements. -- Then traverse diagonal wise, element value is array[i][j]= array[i][i]*array[i+1][j];     traversing end point at reaching array[0][n-1]; calculate max after calculating each product. import java.math.BigInteger; import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner sc=new Scanner(System.in);         BigInteger max=BigInteger.valueOf(-999999);         BigInteger [][] arr=new BigInteger[105][105];         int x,n,i,j,y;         n=1;         while(sc.hasNext()){          x=sc.nextInt();          if(x!=-999999){         ...

#include<iostream> using namespace std; int arr[1005][1005],sum[1005][1005]; int main(){ freopen("test.txt","r",stdin); int i,j,k,m,n,temp; unsigned long long val; bool flag=false; while(cin>>n>>m){ if(flag) cout<<endl; flag=true; for(i=n-1;i>=0;i--) for(j=0;j<n;j++) cin>>arr[i][j]; sum[0][0]=0; for(i=0;i<m;i++) for(j=0;j<m;j++) sum[0][0]+=arr[i][j]; val=sum[0][0]; for(j=1;j<=n-m;j++){ temp=sum[0][j-1]; for(i=0;i<m;i++){ temp=temp-arr[i][j-1]+arr[i][j+m-1]; } sum[0][j]=temp; val=val+temp; } for(i=1;i<=n-m;i++){ for(j=0;j<=n-m;j++){ temp=sum[i-1][j]; for(k=j;k<j+m;k++){ temp=temp-arr[i-1][k]+arr[i+m-1][k]; } sum[i][j]=temp; val=val+temp; } } for(i=n-m;i>=0;i--) for(j=0;j<=n-m;j++) cout<<sum[i][j]<<endl; cout<<val<<endl; } ret...

Algorithm : Kadane Algo. #include<iostream> #include<vector> using namespace std; void kasane_algo(int *arr,int n,int &start_index,int &end_index){ int temp,i,diff,max; temp=max=arr[0]; start_index=0; vector<int> vec; if(temp>0){ vec.push_back(1); vec.push_back(2); } for(i=1;i<n;i++){ if(temp<0){ start_index=i; temp=0; } if(max<0 && arr[i]<0){ temp=-1; }else{ temp=temp+arr[i]; if(temp>=max){ if(temp>max){ vec.clear(); max=temp; } vec.push_back(start_index+1); vec.push_back(i+2); } } } diff=0; max=vec.size(); for(i=0;i<max;i=i+2){ if((vec[i+1]-vec[i])>diff){ diff=vec[i+1]-vec[i]; start_index=vec[i]; end_index=vec[i+1]; } } } int main(){ int arr[20001],i,kase,start_index,end_index,test_case,n; bool flag; cin>>kase; test_case=1; while(kase>=test_case){ cin>>n; flag=true...

Algorithm : Kadane's Algorithm (calculate max sum for sub array) Create 4 matrix for input matrix. Suppose input is 4*4 then store it 8*8 matrix. Suppose input 3*3 matrix a1 a2 a3 b1 b2 b3 c1 c2 c3 store it 6*6 matrix like a1 a2 a3 a1 a2 a3 b1 b2 b3 b1 b2 b3 c1 c2 c3 c1 c2 c3 a1 a2 a3 a1 a2 a3 b1 b2 b3 b1 b2 b3 c1 c2 c3 c1 c2 c3 calculate max sum for all 3*3 size matrix. Code: #include<iostream> #include<algorithm> using namespace std; int max_sum_sub_array(int *arr,int n){ int max,i,cur_sum; max=cur_sum=arr[0]; for(i=1;i<n;i++){ if(cur_sum<0) cur_sum=0; if(max<0 && arr[i]<0){ if(max<arr[i]) max=arr[i]; }else{ cur_sum=cur_sum+arr[i]; if(max<cur_sum) max=cur_sum; } } return max; } int main(){ int arr[160][160],i,j,k,n,kase,temp[160],max,ans,x,y; cin>>kase; while(kase--){ cin>>n; max=0x80000000; for(i=1;i<=n;i++){ for(j=1;j<=n;j++...

#include<iostream> using namespace std; void binary_search(int *arr,int start,int end,int val,int &pos){ if (start == end){ if (arr[start] > val) pos = start; else pos = -1; return; } int mid = (start + end) / 2; if (arr[mid] > val){ binary_search(arr, start, mid, val, pos); } else if (arr[mid + 1] > val){ pos = mid + 1; } else{ binary_search(arr, mid + 1, end, val, pos); } } int main(){ int arr[50001], pos, x, i, m, n,z; cin >> n; cin >> arr[0]; z = 0; for (i = 1; i < n; i++){ cin >> x; if (arr[z] != x){ z++; arr[z] = x; } } cin >> m; for (i = 0; i < m; i++){ cin >> x; if (z == 0){ if (arr[0] == x) cout << "X X" << endl; else if (arr[0] < x) cout << arr[0] << " X" << endl; else cout << "X " << arr[0] << endl; } else{ binary_s...