Need help.!

I was trying to solve some past contest problems. I got stuck on these 2 problems. I read the editorials but didn’t quite understood it. It would be really nice if someone can explain approach to solve these problems.

https://codeforces.com/contest/1249/problem/D1
https://codeforces.com/contest/1249/problem/C2

D1: Greedy algorithm.
First input segments as
segment[l].push_back(make_pair(r,i)) where i is the index.
Then use a set.
iterate from 1 to 200000.
at every iteration add the elements at segment[i] to the set. those elements are the ranges at this number. remove all the elements whose r<i since we’ve already crossed them. if the number of elements in the set is larger than k, remove the elements that go the furthest ahead to maximize the number of segment reductions and store the removed segments in an answer vector.

C2: Find the largest 2 in base 3 notation. add that power to it and subtract the remainder. eg
1120201001 we get
1200000000 now do it again
2000000000 again
10000000000
Code for D1

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
	cin>>n>>k;
	vector<int> ans;
	vector<pair<int,int>> segment[200005];
	set<pair<int,int>> insidesegment;
	for(int i=0;i<n;i++){
	  int l,r;
	  cin>>l>>r;
	  segment[l].pb(mp(r,i)); 
	}
	
    for(int i=0;i<200003;i++){
        for(int j=0;j<segment[i].size();j++){
            insidesegment.insert(segment[i][j]);
        }        insidesegment.erase(insidesegment.begin(),insidesegment.lower_bound(mp(i,-1)));
        while(insidesegment.size()>k){
            ans.pb((*prev(insidesegment.end())).second);
            insidesegment.erase(prev(insidesegment.end()));
        }
        
    }
    cout<<ans.size();
    cout<<"\n";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]+1<<" ";
    }
    cout<<'\n';
}

Code for C2

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin >>t;
	while(t--){
	    ll n,ans;
	    ll removable=0;
	    cin>>n;
	    ans=n;
	    ll placevalue=1;
	    while(n){
	        if(n%3==2){
	            ans+=placevalue;
	            n+=1;
	            ans-=removable;
	            removable=0;
	        }
	        removable+=placevalue*(n%3);
	        n/=3;
	        placevalue*=3;
	    }
	    cout<<ans<<"\n";
	}
	
}

1 Like

Thank you so much for explanation and code.:grinning: