SAMESNAK - Editorial

PROBLEM LINKS:

Contest
Practice

Author: Praveen Dhinwa
Primary Tester: Hasan Jaddouh
Editorialist: Aulene De

DIFFICULTY:

Easy

PREREQUISITES:

Plotting points on a 2d-grid

PROBLEM:

Given the starting and ending points of two snakes, determine if the two snakes form a connected component without having a vertex with degree greater than 2 at any point.

Let x11, y11, x12, y12 define the starting and ending points for the first sighting. Similarly, let x21, y21, x22, y22 define the same for the second sighting.

QUICK EXPLANATION:

All solutions lie under the following conditions -

  1. Same X-coordinates across all 4 points, overlapping Y-coordinates
  2. Same Y-coordinates across all 4 points, overlapping X-coordinates
  3. Overlapping end-points

EXPLANATION:

We start by sorting the points of each snake sighting by their X-coordinate and breaking ties with their Y-coordinates.

After that, we try to think of cases where our answer can be true. This part is probably where the problem gets a little easier: remember that little condition we put up there, the one that said “The degree of a vertex should not be greater than 2”? Well, that condition makes this problem simple, as senpai will show you now.

Now, why is this little condition so important? Well, try to think of some cases where this condition is false and plot them on a paper. Come on now, think!

Notice something? Well, if we do plot them on a graph, we can clearly see that the
case where the degree of a vertex is greater than three is when the two snake sightings are perpendicular to each other… something like this.

alt text

Right, so if the two snake sightings are perpendicular to each other and intersect at some vertex… the degree of that vertex will be 3. However, can we think of a case where the degree is 2?

Here’s a hint: What if the sightings are perpendicular to each other at the end-points?

Well, we do get a common vertex, but the degree is 2! Got it right? Awesome. Take this virtual chocolate chip cookie.

alt text

Okay, now what? Well, there is another case where the conditions given in the statement are fulfilled. What if both of the sightings are parallel to each other and have (an) overlapping vertex/vertices? Something like… this?

alt text

Notice something? There’s no vertex with a degree greater than 2, and all conditions for our graph to be valid are fulfilled.

Well, turns out, if there is an overlapping X-coordinate when the Y-coordinates of all points are the same, our solution is valid!

Could we use this to find another case? What if all 4 points have the same X-coordinates?

In this case, we just need to check if there are overlapping Y-coordinates. Outside of these 3, there will be no sightings that fulfil the conditions required for our graph to be valid.

Thus, to summarize, we have established 3 conditions under which all our possible solutions lie -

  1. Same X-coordinates across all 4 points, overlapping Y-coordinates
  2. Same Y-coordinates across all 4 points, overlapping X-coordinates
  3. Overlapping end-points

PS: Notice something? All three of the images I used were directly from the problem statement’s sample test data. A lot of the time, since problem-setters are very mischievous, they leave little tid-bits for you to munch on. Always be on the look-out for these.

PSEUDOCODE:

if y11 == y12 && x21 == x22
	if x12 == x21 && (y11 == y21 || y11 == y22) 
		ans = 1
	if x11 == x21 && (y11 == y21 || y11 == y22)
		ans = 1


if y21 == y22 && x11 == x12 
	if x22 == x11 && (y21 == y11 || y21 == y12)
		ans = 1
	if x21 == x11 && (y21 == y11 || y21 == y12)
		ans = 1

//Case 3: Row is the same (overlaps)

if y11 == y12 == y21== y22
	if |x12 - x11| + |x21 - x22| + 2  > max ( |x22 - x11| , |x21 - x12| ) + 1
		ans = 1

//Case 4: Column is the same (overlaps)

if x11 == x12 == x21 == x22 
	if |y12 - y11| + |y21 - y22| + 2 > max ( |y22 - y11|, |y21 - y12| ) + 1
		ans = 1

SOLUTIONS:

Editorialist’s solution - https://pastebin.com/GkRsLWFz

1 Like

Can someone please look at my code below:

link text

I am not able to get a test-case where it is going wrong…If some-one can give one such, It would be a great help…!
Thank you…!

PS: My logic is:

  1. If both lines are horizontal or vertical, I am just checking that if any one point of a line lies between other two points of other line.

i.e. If both lines are horizontal then:
if((x11>=x21 && x11<=x22) || (x12>=x21 && x12<=x22) || (x21>=x11 && x21<=x12) || (x22>=x11 && x22<=x12))
then true; else false;

  1. If one horizontal and one vertical, I am just checking the four end-points (corners)
    i.e. If first line is vertical and other one horizontal then:

if((x21==x11 && y21==y11) || (x21==x12 && y21==y12) || (x22==x11 && y22==y11) || (x22==x12 && y22==y12))
then true; else false;

Can someone, please tell me where did I go wrong? I am having really a bit of trouble with this simple code!

https://www.codechef.com/viewsolution/13682730

Thankyou

I can’t see what’s wrong with my code either:
//www.codechef.com/viewsolution/13742391
(It gets WA.)

edit: I have found the bug now. My code didn’t work for the case: both snakes vertical and one of length 0 inside the other.

1
2 0 2 3
2 1 2 1
no

Can someone please point out where did i go wrong .I cannot find any test case where it is going wrong

https://www.codechef.com/viewsolution/13776296

ThankYou !!

I guess you’re going wrong when both lines are horizontal.

Check for this input:

8 0 -2 0

9 0 6 0

The code would give wrong answer for above test case.

You need make cases as follows,

  1. x22 <= x11 << x21 and x21 <= x11 <= x22

  2. x22 <= x12 << x21 and x21 <= x12 <= x22

  3. x11 <= x21 << x12 and x12 <= x21 <= x11

  4. x11 <= x22 << x12 and x12 <= x22 <= x11

to avoid above tedious checks, you can do this:
if(x11 > x12) swap(x11, x12);
and if(x21 > x22) swap(x21, x22);
and then apply your checking conditions(written in your code).

Hopefully you get it!

1 Like

Your code gives WA in this case:

0 2 0 8

0 2 0 2

your code gives answer NO, while the answer should be YES.

Whats wrong with my code? Can someone figure out?
https://www.codechef.com/viewsolution/13685172

What’s Wrong With my code , Here it islink text

It is showing WA.
inbetween(x,y,z) means that if y lies between x and z
issingle() gives that snake will be a single point
ishorizontal() gives that snake is horizontal
isvertical() gives that snake is vertical

Can someone point out mistake in my code - WA : https://www.codechef.com/viewsolution/13768389
Thanks in advance

Thanks @sumedhk and Yes, my code was surely going wrong on your given case.

Well I did made changes as per you suggested…but it’s still giving WA…

Please help…!

PS: Code link is as stated above in my answer

Can someone tell me, what’s wrong with my solution ? Or any test case that it fails for?

@sumedhk Can you provide a test case for my code also?
https://www.codechef.com/viewsolution/13729968

I can’t find out what is wrong with my solution. I have tried all the test cases I can think of and it gives the correct output. It would be very helpful if anyone could suggest some test case that fails.Thanks!
Here is my solution - https://www.codechef.com/viewsolution/13743614

Can please anyone help me find the error in this solution https://www.codechef.com/viewsolution/13729224

Here’s a test case where your code fails:

0 2 0 6

0 6 0 7

Answer should be YES.

1 Like

Thanks @sumedhk

can anyone please tell me where did i go wrong here is my solution to the problem … i’d be glad if anyone can help me to find my mistake

Can Somebody please help me with this?? https://www.codechef.com/viewsolution/13773301

This is my Logic:

  • If both snakes are horizontal (or vertical) , at least one of the ends of a snake
    must be between or on the ends of the other.

  • If snake 1 is horizontal and snake 2 is vertical, exactly
    one end point of the snakes must coincide.

Can anyone please provide a test case for this solution ? The solution seems straightforward and easy to understand:
https://www.codechef.com/viewplaintext/13734952

//