Day 26 | Upsolving Codeforces Div3 Round 820 (D|E) | C++

Yesterday we solved Div3 A, B, and C. Today we are going to upsolve problems D and E.

The first question you should ask is if I couldn't solve D and E yesterday, how I solve them today? It is simple, I learned how to solve them. Yes, we keep learning what we don't know and ultimately we will have a good set of knowledge to perform better in contests. Of course, you need to give contests regularly as well because there are things like experience in contests that also affect your personal performance, but mainly it's practice.

Let's get started then

Friends and the Restaurant | C++ Solution

Let's see this is asking for maximizing the number of days we go to the restaurant, so if we go by how I try to solve it

We need to first decide on the approach we are going to use, and as per my binary search article I would try this way

1. Binary Search - It is the first thing I try to apply to a problem with words given above

2. Dynamic Programming - According to my experience it is the second thing I use

3. Greedy Approach

4. Mathematics

I tried the first 2 and no simple method struck my mind to solve by these 2 so I went with greedy. Another reason, which you might be able to understand better later in your journey, the problem seemed like a greedy problem.

Now, the problem asks us to sort into groups such that the expenditure is strictly less than or equal to the money they have.

So, let's keep an array of differences in expenditure and money they have so we can know how much extra money each person has. I have a plan to keep them sorted in the future, so using a multiset (as there can be repeated values as well)

We can do it like this -

multiset<int> extra;
for(int i = 0; i < n; i++)
    extra.insert(money[i] - expenditure[i]);

Now, we can find solutions like this

• Take maximum and minimum from set

• If their sum is >= 0, then make this a pair

• Otherwise, remove the minimum and reconsider maximum

We can implement it like this

void solve(){
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	for(int& i: x)cin >> i;
	for(int& i: y)cin >> i;
	multiset<int> s;
	for(int i = 0; i < n; i++){
		s.insert(y[i] - x[i]);
	}
	int ans = 0;
	while(s.size() >= 2){
		auto it = s.begin();
		int lowest = *it;
		s.erase(it);
		it = prev(s.end());
		int highest = *it;
		if(lowest + highest < 0)continue;
		s.erase(it);
		ans++;
	}
	cout << ans << '\n';
}
 

But what is the proof that this will work?

Consider that we maximum and minimum do not give a positive result, then maybe the second maximum, maximum, and minimum give a positive result. But if we are making pairs that way, we don't need a minimum. If we remove the minimum, we will still find a valid pair (if nothing else is found) of maximum and second maximum

Interactive Problems

This is an interactive problem. If you have never attempted any interactive problems or have no idea what these are then go ahead and read this blog on the Codeforces on interactive problem

You can also get up to speed by solving this interactive problem

This sample problem is similar to binary search, where instead of calculating if mid is less than the answer we take input to get it.

We can implement it like this

int main(){
    int lo = 1, hi = 1e6, ans;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        cout << mid << endl;
        string x;
        cin >> x;
        if(x == ">="){
            //This mean answer is greater than or equal to mid
            ans = mid;
            lo = mid + 1;
        }else{
            //This means answer is less than mid
            hi = mid - 1;
        }
    }
    cout << "! " << ans << endl;
}

Remember to flush your output. In C++, if you use endl to output a new line, then it flushes out the output buffer.

Guess the cycle size | C++ Implementation

In this problem, we can look at the following observation

1. There is a 50% chance of choosing either path

2. (? a b) and (? b a) can give different results

So if we keep asking like

(? 1 2) (? 2 1)

(? 1 3) (? 3 1)

(? 1 4) (? 4 1)

(? 1 5) (? 5 1)

and so on till 25 (max questions are 50)

Then given that path in both of them is chosen at a 50% chance, there is a very very high probability that we can get a smaller and greater path between two nodes at least once.

So we can try this way and print the sum when we get two different lengths for two queries

You can implement it like this

long long print_ques(long long a, long long b){
	cout << "? " << a << " " << b << endl;
	long long x;
	cin >> x;
	return x;
}
 
void print_ans(long long val){
	cout << "! " << val << endl;
	exit(0);
}
 
 
int main(){
    long long a,b,ans;
    for(int i = 2; i <= 26; i++){
       long long x1 = print_ques(1,i);
       long long x2 = print_ques(i,1);
       if(x1 == -1){
           print_ans(i-1);
       }
       if(x1 != x2){
           print_ans(x1 + x2);
       }
    }
}

Please like and share my posts if they are helpful.