I am currently thinking about the following problem. https://archive.topcoder.com/ProblemStatement/pm/15306 Using DP, we can easily count the number of distinct subsequences, and by extension the number of distinct strictly increasing subsequences. For example, see this blog post: https://mirror.codeforces.com/blog/entry/80464?#comment-667033.

However, I'm unsure on how to extend this idea to count the number of distinct subsequences CONTAINING a strictly increasing sub-subsequence. The difficulty arises in cases like [1,2,3,1,2,3,1,2,3], where to count subsequences like [1,3,2,3] (for L=3 for instance) one needs to somehow skip over the leftmost next occurance of the value 2.

Thanks in advance.

I have some questions regarding two similar problems.

1. We are given ONE set of points in 2D (the plane), and we want to find the closest pair of points within this set. I know the divide and conquer algorithm, but I have seen various sources make different arguments for the number of points one needs to check (3, 5, or 7). Which is actually correct and most optimal? A brief proof of correction for the most optimal solution will be appreciated.

2. We are given TWO sets of points A and B in 2D (the plane), and we want to find the closest pair (a,b) such that $$$a \in A$$$ and $$$b \in B$$$. How can we solve this? Is this a variant of the above problem with only ONE set of points, or does it require something else?

Consider this problem: https://www.acwing.com/problem/content/description/129/ Translation: A company has M tasks to be completed. Each task has a corresponding difficulty level and the time required to complete the task. The difficulty level of tasks is $$$y_i$$$. The time required to complete the task is $$$x_i$$$. If the company completes this task, they will receive $$$500 x_i+2 y_i$$$ income. The company has N machines, each with a maximum working time and maximum difficulty level. If the task requires more time than the maximum working time of the machine, the machine cannot complete the task. If the difficulty level of the task exceeds the maximum difficulty level of the machine, the machine cannot complete the next task. Each machine can only complete one task in a day. Each task can only be completed by one machine. Find the maximum number of tasks that can be completed, and the corresponding profit. If there are multiple solutions, choose the one that earns the highest profit.

Input format: For each test case, the first line contains two integers N and M, representing the number of machines and the number of tasks, respectively. Next N rows each contains two integers $$$x_i$$$ and $$$y_i$$$, respectively representing the maximum working time and maximum difficulty level of each machine. Next M rows each contains two integers $$$x_i$$$ and $$$y_i$$$, respectively representing the time required to complete the task and the difficulty level of the task.

Solution: The intended solution is greedy. However, my greedy approach does not work:

int n, m; 
while (cin >> n >> m) {
    // time and level
    multiset<pii> machines; 
    F0R(i,n) {
        int a, b; cin >> a >> b;
        machines.insert(mp(a,b)); 
    }

    vector<pii> tasks(m); 
    F0R(i,m) {
        int a, b; cin >> a >> b; tasks[i] = mp(a,b);
    }
    sort(all(tasks)); reverse(all(tasks));

    int cnt = 0, ans = 0;
    F0R(i,m) {
        auto it = lower_bound(all(machines), tasks[i]);
        while (it != machines.end()) {
            if (it->second >= tasks[i].ss) { 
                cnt++;
                ans += 500*tasks[i].ff + 2*tasks[i].ss;
                machines.erase(it);
                break;
            }
            it++;
        }
    }
    cout << cnt << ' ' << ans << '\n'; 
}

This fails at the following case: 20 30 42 67 583 0 476 24 1413 58 1079 64 1392 45 274 27 1334 91 120 42 514 36 756 4 1027 53 293 82 166 16 1025 95 1134 26 392 38 432 12 1222 99 1218 94 1363 11 1104 33 406 64 752 11 913 68 1085 44 1005 57 1331 59 90 41 189 78 805 35 606 42 289 6 407 42 558 48 106 5 62 29 1347 50 617 1 1370 48 923 23 1061 54 50 40 650 76 981 8 1116 39 164 23 1221 38 290 82 1345 41 The first number of the answer (i.e. the maximum number of tasks that can be completed) for this case is 16, but my code outputs 15.

The following solution passes:

while(cin >> n >> m){
    for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    for(int i = 1; i <= m; i++) cin >> b[i].first >> b[i].second;

    sort(a + 1,a + 1 + n); sort(b + 1,b + 1 + m);

    multiset<int> s; s.clear();
    long long cnt = 0, ans = 0;
    for(int i = m, j = n; i >= 1; i--){
        while(j >= 1 && b[i].first <= a[j].first)s.insert(a[j--].second);

        multiset<int>::iterator it = s.lower_bound(b[i].second);
        if(it != s.end()){
            cnt ++;
            ans += 500 * b[i].first + 2 * b[i].second;
            s.erase(it);
        }
    }
    cout << cnt << " " << ans << endl;
}

//Credits：墨染空

So why does my solution fail but the above solution pass?