CHFRAN no exhaustive tests

help
1

code
this is my code (wrong logic) and it got AC for 10 pts.

https://www.codechef.com/viewsolution/28319668
could someone please add more tests for this problem

1
16
44 88
53 72
12 22
5 75
12 26
50 52
18 63
46 51
10 22
57 90
52 82
51 100
1 30
9 18
24 35
41 82

this is one of the testcase for which my code fails.

here’s a visualization to see that the answer is 2
Figure_1

@rishup_nitdgp please add more tests

2

I can give a quick thought about this -
what you try to do is actually draw this ranges but sorted according to the first coordinate,and then start drawing vertical lines on the second coordinate of each range and see how may ranges it intersects and then delete such ranges where minimum intersections happen.

1 Like
3

Yeah, it works. Nice idea. I solved it differently though my AC code

4

Isn’t that solution O(n^2) ?

5

Nope , sorting takes nlogn time and then rest of the work is done by just looking over the second coordinates which also are sorted , (used lower bound for getting the appropriate position) for a better reference you can have a look at my solution,
https://www.codechef.com/viewsolution/28339731

2 Likes
6

My approach was:

  • Put start and end points into an array A (and remember their type).
  • Sort array A, take care that start points with same coordinate as end point will be processed first. Otherwise you get wrong solution. (O(nlogn))
  • Iterate through the array A and fill a prefix sum array B (each start adds one, each end removes one) (O(n))
  • Find a start point in array B (first decreasing sequence from start of the array) (O(n))
  • Find an end point in array B (first decreasing sequence from end of the array) (O(n))
  • Iterate through B from start to end and take smallest value (this is the solution) (O(n))

Code: CodeChef: Practical coding for everyone

1 Like
7

one help tell me which range will you delete and then what will be the two subsets for this test case
1
6
3 5
4 7
5 7
6 10
8 9
10 12

8

it seems they had given poor test cases

9

delete 6 10 range
Figure_3

the y = {18,17,16} is one range and y = {15,13} is another

1 Like
10

but 15,13 have no common points how it will be in one subset?

11

They just said they have to be in the same subset if they share a point not they have to be in different subsets if they don’t share one.

12

yes right. thanks

13

Yup my incomplete logic also passed for 10pts.

1 Like
14

i used recursion to achieve this, but couldnt optimise it so i got tle in higher subtasks…
can anyone help mw in optimising this code(also i dont think it has overlapping here, correct me if im wrong)
https://www.codechef.com/viewsolution/28343558

15

Hey I was looking at your solution but didn’t get the proper intuition behind it.
I am stuck at the part where you found no of finish times less than first time of current one (Line 207).
Also,

Could you please tell me how to do this efficiently?

16

Hey @bennyjoseph, thanks for noticing. I tried my best to make the test cases uniform in all the subtasks but every time something is skipped.

I’ll add this test case for the practice section.

17

Okay thanks. I loved the problem by the way.