PROBLEM LINK:
Author: Ilya Malinovsky
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Ad-Hoc
PROBLEM:
Numbers 1 to N are written in clockwise order. Given k disjoint intervals(each interval given in clockwise direction) (l1,r1),(l2,r2)…(lk,rk) denoting boy’s division. These intervals cover the whole set.
Similarily, given is the Chef’s division(what he wants to achieve) (a1,b1),(a2,b2)…(ap,bp). He can divide an interval from boy’s intervals into disjoint intervals but he cannot join two of the boy’s intervals. Check if it’s possible to acheive his intervals from boy’s intervals.
QUICK EXPLANATION:
Answer is “Yes” iff for each interval in boy’s division, the left border coincides with left border of some interval in chef’s division.
EXPLANATION:
For any i, if there doesn’t exist a j such that li = aj, that means segments numberered (li-1) and (li) will be occuring together in chef’s division but they are in different parts in boys division. Hence, it will equivalent to chef joining to different parts of boys division which is not allowed.
If the condition that “for each interval in boy’s division, the left border coincides with left border of some interval in chef’s division” this kind of scenario will occur.
Here, red lines denote chef’s divisions. Only those divisions of chef are shown where left border coincide with boys’ divisions.
Since, chef’s divisions also cover all the parts, the remaining parts will be covered by the remaining divisions.
Therefore, we have to check only one condition. Pseudo code:
n,k,p=input()
flag=0
set myset
for i=0 to k:
x,y=input()
myset.insert(x)
for i=0 to p:
x,y=input()
if x not in myset: flag=1
if flag, print "No"
else, print "Yes"
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon.
