Touching segments
-
MihirDas 10 years ago can you give me a few test cases and their answers apart from the hidden testcases. the program is running correct according to me but the compiler is showing wrong answer for many test cases.
-
SalvadorDali 10 years ago Have absolutely the same problem. Only 3 cases passes, all else have wrong answer. I created huge amount of manual test cases (all of which are passing). And to tell the truth I believe that my solution is correct.
-
sanubajoria 10 years ago same for me
-
mayurdabhi 10 years ago Same here.. Tried various sample test case, all are passing..
-
-
-
-
signal11 10 years ago now that the contest is over, is it possible to share some more test cases ? thanks !
-
abhiranjan 10 years ago Done.
-
sanubajoria 10 years ago can you telll me . How can i get the testcases?
-
abhiranjan 10 years ago You can get the test cases from submission page (you need to make a submission for that).
-
-
-
-
sanubajoria 10 years ago can u give some sample test case.i tested its working for me.but still its passing 3 testcases
-
Eternal_Dragon 10 years ago Hey guys Consider a testcase as 1
3
1 2
1 2
3 4
Now point 2 crosses 1 2 and point 3 crosses 3 4. But as 1 2 is repeated twice in the given input, should the output be 3 or will it be 2 for the above scenario?
In short, can i ignore duplicate segments given as input?
-
AhmedAKZM 10 years ago The output should be three. See this (https://www.hackerrank.com/contests/software-challenge/challenges/picking/forum/comments/48379) comment
-
-
tom_b 10 years ago I think I am missing a subtle case.
Assume you first find the point p1 with the maximum number of intersections. Now remove all the segments this point intersects. Now find the point p2 with the maximum number of intersections in the remaining segments.
I thought that the sum of the count of intersections at p1 and p2 would be the answer, but this seems to fail a number of test cases.
I can't visualize a case where a point (pt1) with the maximum number of interesctions is not part of the answer, but maybe I am wrong about that?
-
abhiranjan 10 years ago Hi, sorry I haven't solved this challenge. But I see many people using segment tree to solve this. Please refer to their solutions, if stil stuck.
-
tom_b 10 years ago Thanks abhiranjan.
I had been looking at interval trees and segment trees for this challenge, but convinced myself it could be solved without them. However, I have also brute-forced some of the failing testcases and verified that my original idea, expressed above, is not correct!
So, when I get some time, I'll delve into segement trees and how to solve this properly.
Thanks for the suggestion and following up.tom_b
-
abhiranjan 10 years ago Welcome :)
-
-
-
ritesh_bajaj6 10 years ago hi @tom_b did you got any test case which is failing your logic. I have also used the same logic & its failing for some test cases.
-
tom_b 10 years ago I don't have a test case that I generated, but the third testcase part 3 from the challenge testcases has 76 segments and fails. That one was small enough to brute force (testing each point p1 for intersections and then checking the remaining points after removing any segments intersected by p1).
-
KamaleshNair 10 years ago Hi @tom_b, I had also done it the same way you did, failed for the exact same test case. Would you let me when you figure out how this is done using the "segment tree" approach.
I have gone through the "line-sweep algorithm" + "segment-tree" data structure (used in the algorithm) and found that it yields the correct answer, but I would like to know how it gives the correct answer and what is different/the error in your initial approach
-
-
-
Sort 15 Discussions, By:
Please Log In in order to post a comment