TANGDIV - Editorial

PROBLEM LINK:

Practice
Contest

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.

8 Likes

what should be the ans to this test case???

1
2 1 1
1 2
2 1

both “yes” and “no” are getting accepted!!!

The answer should be no.
Though it’s logical that in this case, 12 and 21 are exactly the same. Still to get 12 from 21 we’ll have to rotate our configuration i.e. take the “1” from 21 and put it in the front. And that is not allowed.
For justification see the second sample test case in the problem.
10 3 1
2 5
10 1
6 9
1 10

1 Like

ans should be no,well i wrote around 22 different test cases,
put different conditions for them…and got AC…
here is the link to my soln.
http://www.codechef.com/viewsolution/3741801

l, r - denote chef’s, a, b - boy’s, i think

@garakchy No. l,r -denotes boy’s division and viceversa as can been seen through the problem statements here.

by solving this problem a learned only one thing READ problem statement carefully….

i got 10 WAs beacuse of this we had to print “Yes” and “No” and i was printing “YES” n “NO” …:smiley:

4 Likes

In order to do it he planned to separate the neighbouring segments in k places, so that he could get k parts: the 1st - from segment l1 to segment r1 (inclusive), the 2nd - from l2 to r2, …, the kth - from lk to rk (in all cases in the clockwise order). Suddenly, when Chef was absent, one naughty boy came and divided the tangerine into p parts (also by separating the neighbouring segments one from another): the 1st - from segment a1 to segment b1, the 2nd - from a2 to b2, …, the pth - from ap to bp

1 Like

yeah,there is a mismatch b/w the problem and the editorial. But, the editorial has been designed keeping l,r - as boy’s division and viceversa in view.
So,in order to understand the editorial you need to follow the editorial’s assumption :slight_smile:

since it is wiki, can sb, who knows the topic well, edit it pls

This one was easy and trick! :stuck_out_tongue:
Here’s how i solved it-
As the editorialist said problem occurs if a segment x is to be linked with segment x+1 originally and the boy breaks it there, since this effect cant be undone.
so suppose one i/p is 1 5 this means 5 is not linked to 6 and hence use a marker break[5]=1 meaning 5 is not linked to 6. Mark all the breakage for chef and boy and compare the two values on the basis-
if chef did not mark breakage and the boy did- hence an error!!
Heres my code- http://www.codechef.com/viewsolution/3792091

Simple map can be used for the purpose of storing breakage of boy and chef ( max size would be 500 )
Note since N = O(5*10e7), i dont think we’ll be able to use boolean array for the same purpose, since heap memory limit mite be violated!
Cheers!

what if test case is
9 2 1
2 4
7 9
1 5
according to your algorithm it will print no but it should print yes. algorithm should be search for subset.

@shipu and malinovsky239 … please tell the bug in this code… i still can not figure out the bug … kindly respond quick … it is troubling me a lot …

here is basic idea to the code i wrote

.make boundaries for child’s division (a,b) — i write it as a-0.2 and b+0.2

.query chefs interval as it is.

. count how many intervals in between l and r via binary search if 0 then fine else “No”.

. some modifications for l>r cases (cyclicity) …clear in code.

please respond with test cases … if u cant figure out any then also respond …

here is the link

http://www.codechef.com/viewsolution/3756360

are u sure it is the correct link…i can see that the soln is AC…also it is of some other user!!!

thanx to point out its edited with new link …

help will appreciated…