LightOJ - 1198 - Karate Competition 

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1198

Code:

//
// Created by Dabashis Kundu Shento on 7/12/20.
//

#include <bits/stdc++.h>

using namespace std;

int a[55],b[55],dp[55][55],n;

int lower(int i, int j, int val)
{
    int ans=n,mid;

    while(i<=j) {
        mid=(i+j)/2;
        if (a[mid] > val) {
            ans = mid;
            j = mid - 1;
        } else
            i = mid + 1;
    }
    return ans;
}

int cal(int i,int j)
{

   if(i>=n||j>=n) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    int r=0;
    if(a[i]>b[j])
        r=2+cal(i+1,j+1);
    else if(a[i]==b[j])
    {
        int ll=lower(i,n-1,b[j]);
        r=1+cal(i+1,j+1);
        if(ll<n)
            r=max(r,2+cal(ll+1,j+1));
    }
    else
        r= cal(i+1,j);

    return dp[i][j]=r;
}

int main() {
    int t,f=0;
    cin>>t;
    while(t--){
        cin>>n;
        f++;
        //int a[n+4],b[n+5];
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int i=0;i<n;i++)
            cin>>b[i];
        sort(a,a+n);
        sort(b,b+n);
        memset(dp,-1,sizeof(dp));
        int res=cal(0,0);
        cout<<"Case "<<f<<": "<<res<<endl;
    }
}

 

 LightOJ-1016 - Brush (II) 

 IDEA: 

We can clean each dust by placing the brush on the y-axis of that point. From that point +w will cover all the points between them inclusively. For this first sort y-axis value then find points covered by each point.

Code:

//
// Created by Dabashis Kundu Shento on 5/12/20.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t,l=0;
    cin>>t;
    while(t--)
    {
        l++;
        int n,w;
        cin>>n>>w;
        int a,b;
        int c,d;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            cin>>a>>b;
            v.push_back(b);
        }
        sort(v.begin(),v.end());
        int ans=1;
        c=v[0];
        for(int i=1;i<n;i++)
        {
            if(v[i]-c>w)
            {
                ans++;
                c=v[i];
            }
        }
        cout<<"Case "<<l<<": "<<ans<<endl;
    }
    return 0;
}