CP Coaching Week 1 (20 -> 26 November 2019) - Solutions

Problem 1:
You may have solved this with a naive approach, where you loop from i to j and calculate the sum in each query.
But that has a Big-O complexity of O(N*Q) which "should" cause a TimeLimitExceeded; the test data are weak.

Let's discuss a much faster solution, using prefix sum arrays.
Learn this technique here: hackerrank.com/topics/prefix-sum

A prefix of something is a part of it that begins at the beginning.
For example "ab", "a", "abc" are prefixes of the string "abc".
The trick is to construct a prefix sum array P, where P[i] = A[0] + A[1] + ... + A[i]        -- A is the input array
Using this array, any sum  A[i] + A[i+1] + ... + A[j] can be represented using P as P[j] - P[i-1]. Be careful from the case where i = 0.

Re-submit the problem using this method!
And then try to solve this: codeforces.com/contest/816/problem/B



Problem 2:
The key observation to make is that the valleys will be disjoint, so you can keep a counter and count each time
you go back to level 0 while coming up from -1.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    string s; cin >> s;
    int nb = 0;
    int currentLevel = 0;
    for(int i=0;i<n;++i){
        if(s[i] == 'D') --currentLevel;
        else{
            ++currentLevel;
            if(currentLevel == 0) ++nb;
        }
    }
    cout << nb << endl;
}



Problem 3:
We are looking for the maximum sized set S of numbers from the array, such that the absolute difference between any two of the chosen integers is less than or equal to 1. Meaning S = {x,x,x,x.....,x+1,x+1,x+1,x+1....} for some x in the array. ==> There will only be two consecutive numbers in it.
We can keep the occurence of each number, test all the possibilities and take the maximum.

#include <bits/stdc++.h>
using namespace std;
int occurence[100]; // things declared globally(outside the main()) are automatically set to 0
int main(){
    int n; cin>>n;
    for(int i=0; i<n; i++){
        int x; cin>>x;
        ++occurence[x];
    }
    int answer = 0;
    for(int i=1; i+1<=99; i++) answer = max(answer, occurence[i] + occurence[i+1]);
    cout << answer << "\n";
    return 0;
}



Problem 4:
Let p and q the two numbers that give us the minimal abs(p-q).
If we sort the array, p and q will be adjacent. Try to demonstrate why, by yourself. (par l'absurde)
So we just sort the array and check every two adjacent numbers and take the minimum.

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
int main() {
    int n; cin >> n;
    int a[n]; for(int i=0; i<n; ++i) cin >> a[i];
    sort(a, a + n);
    int answer = inf;
    for(int i=0; i + 1 < n; ++i) answer = min(answer, abs(a[i] - a[i + 1]));
    cout << answer << "\n";
    return 0;
}




Problem 5:
(Can be solved by std::set but we haven't studied it yet; although you can read about it in the handbook)
Straight forward using a boolean array.

#include <bits/stdc++.h>
using namespace std;
bool canWin[101]; // initialized automatically to false because it's declared globally
int main() {
	int n; cin>>n;

	int p; cin>>p;
	for(i=1; i<=p; i++){
		int x; cin>>x; canWin[x] = true;
	}

	int q; cin>>q;
	for(i=1; i<=q; i++){
		int x; cin>>x; canWin[x] = true;
	}

	for(i=1; i<=n; i++) if(!canWin[i]){
	    cout<<"Oh, my keyboard!\n";
	    return 0;
	}
	cout<<"I become the guy.\n";

	return 0;
}



Problem 6:
It's not hard to see that the optimal way is to bring the leftmost maximum number to the front,
and the rightmost minimum number to the end.
How much time will those swap operations take?
Let a be the index of the leftmost maximum, and b be the index of the rightmost minimum. (1 indexed indices)
We will need a-1 "seconds" and n-b "seconds". Is that all?

No. Imagine the case where a>b. In that case, we will need one less operation to move the second after fixing the first.
Try to figure out why with an example.


#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin>>n;
	int t[n + 1];
    for(int i=1; i<=n; i++) cin>>t[i];

	int mx = *max_element(t+1, t+1+n);  // if you're doing it 0-indexed, the array's range will be (t,t+n) as usual
	int a; for(int i=n; i>=1; --i) if(t[i] == mx) a = i;

	int mn = *min_element(t+1, t+1+n);
	int b; for(int i=1; i<=n; ++i) if(t[i] == mn) b = i;

	cout << a-1 + n-b - (a > b) << "\n";

	return 0;
}


Remember to solve the dummy contest's problems!!   ==>   codeforces.com/group/MAbng8L9pC/contest/257241