ICPC 2019 -Online Round-Question 3(Moving Line Segments)

help
1

Question 3- ICPC 2019 online round (Moving Line Segments)

Is there anyway of solving the question in O(n^2) ?

2

Yes, This question is solvable in O(n^2) time complexity.

3

Can you share the solution?

4

it should not run in O(n^3)??

5

Yes , i need a solution in O(n^2) if possible…

6

@sanket_j_shah1 Here is my solution. Form an undirected graph where nodes are the line segments and two nodes are connected by an edge iff they intersect (or touch) and have the same speed. Now if it is possible to give directions to nodes in such a way that for every edge, its adjacent nodes have opposite direction (as they’ll be intersecting and having the same speed), then answer is YES else NO. We can do DFS starting from a node and assign it a direction (say left). Then all its adjacent nodes should be assigned right. If any of the adjacent node is already assigned a direction and it is same as that of the parent then answer is NO. PS: the graph formed may have disconnected components.

5 Likes
7

same approach here too … bipartite graph

3 Likes
8

I just checked if undirected graph had cycle of size >=3 then answer is “No” else “Yes”

4 Likes
9

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define nl ‘\n’
#define X first
#define Y second
#define nimble ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v) (v).begin(),(v).end()
#define see(x) cout<<(#x)<<" -> “<<(x)<<”\n"
#define mod(x,m) ((((x)%(m))+(m))%(m))
#define _sz(x) (int)x.size()
#define fr(i,a,b) for(int i=a;i<b;i++)
#define fr1(i,b,a) for(int i=b;i>=a;i–)
#define nearestPowerOf2(S) ((int)pow(2.0,(int)((log((double)S)/log(2.0))+0.5)))

int inf=0x3f3f3f3f;
ll infl=0x3f3f3f3f3f3f3f3fLL;
long double infd=1.0/0.0;
const double pi=2*acos(0.0);
const int MOD=1e9+7;

int main(){
nimble;
int tt=1;cin>>tt;
while(tt–){
int n;
cin>>n;
// vector v[n];
map<int,vector<pair<int,int>>> mp;
for(int i=0;i<n;i++){
int l,r,v;
cin>>l>>r>>v;
mp[v].pb({l,r});
}
int gg=1;
for(auto x:mp){
if(_sz(x.Y)>=3){
vector<pair<int,int>> xx;
xx=x.Y;
int f=0;
for(int i=0;i<_sz(xx);i++){
f=0;
vector<pair<int,int>> ss;
for(int j=0;j<_sz(xx);j++){
if(i==j)
continue;
int pp=xx[i].X;
int qq=xx[i].Y;
int px=xx[j].X;
int qx=xx[j].Y;
if(pp>qx)
continue;
if(qq<px)
continue;
ss.pb({px,qx});
f++;
}
if(f>=2){
int ff=0;
map<int,int> xmp;
map<int,int> coll;
vector<pair<int,int>> xdd;
for(int k=0;k<_sz(ss);k++){
xmp[ss[k].X]=1;
xmp[ss[k].Y]=-1;
coll[ss[k].X]++;
coll[ss[k].Y]++;
}
for(auto xx:coll){
if(xx.Y>1){
gg=0;
break;
}
}
if(gg==0){
cout<<“NO”<<nl;
break;
}
for(auto xx:xmp){
xdd.pb({xx.X,xx.Y});
}
sort(all(xdd));
int cx=0;
for(int k=0;k<_sz(xdd);k++){
cx+=xdd[k].Y;
if(cx>=2){
gg=0;
break;
}
}
if(gg==0){
cout<<“NO”<<nl;
break;
}
}
}
if(gg==0)
break;
}
}
if(gg)
cout<<“YES”<<nl;
}
return 0;
}

10

I made an observation in this question that if any three Line Segments intersect initially and also if their speed is same then there is NO way we can assign direction to all three of them as any two of them will still be intersecting. So, O(n^2) worked here.

11

I had an O(nlogn) solution. First notice that no is only possible if three segments which share a common point have same speed. Then use a differences array to find this intersection. But instead of differences array use a map since we don’t need intermediate points and 1e9 is too big for array.

12

My solution

Time Complexity : {O(n \ logn)}

13

should O(n^3) work in this case. I think it shouldn’t, but some of my friends submitted that and got AC

14

It will work. The sum of n over all the TCs was about 2000.

15

Explain your approach please.

16

if u haven’t used graph , can you please share the code ?

17

even then n^3 is 10^9

18

I created a struct with x coordinate, velocity and type. Type - either left/right of each range. Use a hashmap (velocity, count). Sort the coordinates wrt to x-coordinates. If they have same x-coordinates, then type ‘left’ will come before the other.

Iterate through the sorted array of coordinates. If the coordinate is of type ‘left’, increment corresponding count of velocity in hashmap and check if the count is 3. If so, print ‘No’ and break.
If the coordinate is of type ‘right’, decrement corresponding count of velocity in hashmap.

1 Like
19

Here’s my code which doesn’t use graphs:

/* Created on October 18th 2019 */

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

#define ll long long

bool check_overlap(std::vector<ll> left, std::vector<ll> right, std::vector<ll> velocity, ll i, ll j) {
    if (velocity[i] == velocity[j] &&
            ((left[j] >= left[i] && left[j] <= right[i]) ||
             (right[j] <= right[i] && right[j] >= left[i]))) return true;
    return false;
}

void foo() {
    ll n; scanf("%lld", &n);
    std::vector<ll> left(n); std::vector<ll> right(n); std::vector<ll> velocity(n);
    for (ll i = 0; i < n; ++i) 
        scanf("%lld %lld %lld", &left[i], &right[i], &velocity[i]);

    std::vector<std::set<ll>> overlap(n);
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            if (i == j) continue;
            if (check_overlap(left, right, velocity, i, j) || 
                    check_overlap(left, right, velocity, j, i)) {
                overlap[i].insert(j);
            }
        }
    }

    for (ll i = 0; i < n; ++i) {
        for (auto &x: overlap[i]) {
            if (overlap[x].size() < 2) continue;
            for (auto &y: overlap[x]) {
                if (i != y && overlap[i].count(y)) {
                    puts("NO");
                    return;
                }
            }
        }
    }
    puts("YES");
}

int main(void) {
    ll t; scanf("%lld", &t);
    while (t --) foo();
    return 0;
}
20

Hi, I have done the exact same thing but I am getting a wrong answer.
Here is the link to my submission : https://www.codechef.com/submit/SEGDIR