Please read the new rule regarding the restriction on the use of AI tools. ×

Ideal Point solution improvement

Revision en2, by casadella_guim, 2023-02-22 11:02:18

Ideal Point solution Improvement

Context:

Once I submitted my solution to 1795B - Ideal Point I was curious of checking how the author actually solved the problem. After reading its interesting answer, I thought I could share my thoughts on the problem, which seemed more optimal and faster. Note: I'm doing these problems because I'm starting in C and want to gain some hands on practice and experience in contest-like scenarios

Problem: 1795B - Ideal Point

Please check the original problem to gain some deeper understanding. Basically, in a 1 dimensional space, you are given n segments that span from l to r. You are also given an integer k , candidate of being the Ideal Point. An Ideal Point is one and the only one that intersects with each segment. You are asked to answer whereas it's possible to convert k to an ideal point by eliminating any number of segments.

Authors solution:

I won't go into detail, but the author suggested a (de)constructive solution where you started erasing all the segments that didn't contain the point k. Then, It proceeded to iterate over the 50 possible values of k (defined in the explanation) to find if indeed point k had the maximum number of intersections.

Proposed solution: 194504885

Intuition:

The straightforward idea is that a point k can be Ideal if and only if it's the leftmost point of any segment (l) and the rightmost point of any segment (r). If this is true, you can basically erase every other segment, thus being able to convert k to an Ideal Point and solving the problem

Implementation:

It's as simple as doing a linear scan of the segments and keeping track of some flags regarding l and r. This could be optimized with a while loop, but I wasn't sure of how to "skip" the remaining input.

Code:

#include <stdio.h>
#include <stdbool.h>

int main(){
    int t;
    scanf("%d", &t);

    for (int _ = 0; _ < t; _++){
        int n, k;
        scanf("%d %d", &n, &k);
        
        bool fl = false, fr = false;
        int l, r;
        
        for (int i = 0; i < n; i++){
            scanf("%d %d", &l, &r);
            if ((int)l == k) fl = true;
            if ((int)r == k) fr = true;
        }
        if (fl && fr) printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

Final comment:

This is my first ever post, any suggestions on how to properly reference the problem and where would be the ideal place to post thoughts on problems would be appreciated. As well as any comments on how to improve. Finally, as I said, I'm just starting to learn C, so any tip or recommendation would also be great. Thanks!

Tags bruteforce, problem, solution, gnu c

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English casadella_guim 2023-02-22 11:02:18 68
en1 English casadella_guim 2023-02-21 23:10:09 2828 Initial revision (published)