Ideal Point solution Improvement
Context:
Once I submitted my solution to 1795B - Идеальная точка 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 - Идеальная точка
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!
.