# SAMESNAK - Editorial

Author: Praveen Dhinwa
Editorialist: Aulene De

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.

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.

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?

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:

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);

Hopefully you get it!

1 Like

Your code gives WA in this case:

0 2 0 8

0 2 0 2

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 @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…

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

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