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 !!

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

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

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

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

can someone tell me,whats wrong with my solution,or suggest a test case it fails for
https://www.codechef.com/viewsolution/13760654
thanks

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

This is my solution. I guess the cases most users must be missing is complete overlap of two snakes.
eg

0 2 0 8
0 3 0 5

Here the answer should be yes. My solution is pretty simple, as it takes all cases into consideration and uses if-else alone to print the answer.

Can you please provide the test case for which my code fails.Link to my code is-
https://www.codechef.com/viewsolution/13772896

@jayprakash_a
test case failing
-1 2 -4 2 -1 2 8 2
answer should be no

@jeetu86044 for input -1 2 -4 2 -1 2 8 2 answer should be “yes” I guess.How can it be “no” when they have one overlapping point i.e. -1 2. Correct me if I am wrong.

@the_king_i_am

yes it was actually typing mistake

the original test case is:
1 2 4 2 -1 2 -8 2

ans: no