Mohammad Erfan Hossain's Blog

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...