I have already used the above mentioned hints and solved the problem with 100 points... So I guess it works :-)
I have already used the above mentioned hints and solved the problem with 100 points... So I guess it works :-)
No... DFS and BFS are only required for INOI
We can't change the school system and these teachers won't improve.....
Since you are in Class 12 it will be best to focus on jee and get into a good College and then you can go for contests like ACM-ICPC...
I used the similar approach explained by Mohit Gurumukhani...
Wonder how my program gave the wrong answer... :(
I got the expected output.
Here is my Code:
#include<bits/stdc++.h>#define ll long long#define int ll#define pb push_back#define INF 1000000000#define MOD 1000000007#define mp make_pairconst double PI=3.141592653589793238462643383279502884197169399375105820974944;#define REP(i,n) for (int i = 0; i < n; i++)#define FOR(i,a,b) for (int i = a; i < b; i++)#define REPD(i,n) for (int i = n-1; i >= 0; i--)#define FORD(i,a,b) for (int i = a; i >= b; i--)#define remax(a,b) a = max(a,b)#define remin(a,b) a = min(a,b)#define pii pair<int,int>#define F first#define S second#define mii map<int,int>#define vi vector<int>#define vvi vector<vi>#define itr :: iterator it#define WL(t) while(t --)#define gcd(a,b) __gcd((a),(b))#define lcm(a,b) ((a)*(b))/gcd((a),(b))#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);using namespace std;long long a = 0;void ModExp(int base,int exp,int m){if(m == 1){a = 0;}long long c = 1;for(int i = 1;i <= exp;i++){c = (c*base) % m;}a = c;}bool sortby(const pair<int,int> &a,const pair<int,int> &b){return a.second < b.second;}void solve(){int n;cin >> n;int pref[n];vector<pair<int,int> > arr;for(int i = 0;i < n;i++){if(i == 0){int tmp;cin >> tmp;pref[i] = tmp;arr.push_back(make_pair(i,pref[i]));}else{int tmp;cin >> tmp;pref[i] = pref[i-1] + tmp;arr.push_back(make_pair(i,pref[i]));}}sort(arr.begin(),arr.end(),sortby);int ans = INT_MAX;int rans = INT_MAX;int ai,aj;for(int i = 1;i < n;i++){if(abs((arr[i+1].second) - (arr[i].second)) < ans){aj = max(arr[i].first,arr[i+1].first);ai = min(arr[i].first,arr[i+1].first);ans = abs(arr[i+1].second - arr[i].second);rans = pref[aj] - pref[ai];}}cout << rans << endl;cout << ai+2 << " " << aj+1 << endl;}signed main(){// FastIO;// int t = 1;// cin >> t;// WL(t)solve();}
Looking at the IARCS Study material, I think you should cover uptill Minimum Spanning Tree (Prim's algorithm and Kruskal's algorithm) (excluding it)
Hope I could help....
I guess it should pass because:
n <= 700
So O(n^3) = O(700^3)
which is 343,000,000 calculations.
A computer can process about 108 to 109 calculations per second.
If you do the math and take the log10(343,000,000)
You will get approximately 8.53 which states that the program does approximately 108.53 calculations per second and hence finishes under 1 second.
As this is my first reply, I can't understand why the include statement is empty, It is #include<bits/stdc++.h>
I solved it in 0.00 sec.
You just have to check for a disjoint set,If it is a disjoint set then increment the counter and set the appropriate end.
Here is my Code:
#includeusing namespace std;bool compare(const pair&a,const pair &b){ return (a.second < b.second);}int main(){int n;int ans = 1;cin >> n;int tmp,tmp1;vector> arr; for(int i = 0;i < n;i++){cin >> tmp >> tmp1;arr.push_back(make_pair(tmp,tmp1));}sort(arr.begin(),arr.end(),compare);int e = arr[0].second;for(int i = 1;i < n;i++){if(arr[i].first > e){//disjoint setans += 1;e = arr[i].second;}}cout << ans;return 0;}