Tidying Posters

shdn't the outpout be 1 and then 2, I hope I understood the problem correctly.

No, the sample output is correct.

I am sorry Stephen but I am still not able to understand.

In my understanding, in case#1, I just need to remove poster(0 5 1 2) as remaining 2 are not intersecting.

No, it's the number of posters left over, not the number you take away. I got that mixed up too

:-) thanks, really appreciated it.

completely frustated now. I am using python2.6.5 , runtime error . can anyone plz tell me what can be the cause? sample input is working fine.

Is there a new line in the input,after each test case??

@admin

T = int(raw_input())

for t in range(T):

n = int(raw_input())

for i in range(n):

x = raw_input().split()

print x[0],x[1],x[2],x[3]

I am getting a runtime error in this. Is their a problem with the python compiler?

with proper indentation i mean. Everything running fine on my system

@Anoop Narang - please do not spam the comment section. You should only post a comment if you do not understand the problem statement.

i have tested my code against the given test cases as well as some other test cases and it is giving correct answer in proper output format then why am i getting wrong answer

do i need to check the condition x₀ < x₁ and y₀ < y_{1 for every poster}

and if the condition is not satisfied then what  should my program do?

You are getting wrong answer because your program is outputting the wrong answer for at least one of the judge's test cases. You will not be told anything else to help you.

As for your second message, the problem statement clearly tells you that will always be the case.

@Pankaj, you must have missed the worst case scenario to test.

why do i get runtime(other) when i use 20M and the array is declared

outside all functions?

can i know...what was the solution for this problem?

Can the input file be made publicly available?

I would really like to know the test cases for which my code fails.

Thanks.

Hmm ... now i know there's definitely a better algorithm somewhere for this than what i've implemented , but since my program runs in time for most cases AND i've tried in vain to come up with a corner case (or a class of test cases). I'd really appreciate if someone can point me in right direction ...

http://pastebin.org/324551 [JAVA]

Your problem is that you can produce exponentially many "solution sets" as you call them in your comments. You'll run out of time or out of memory to store them, whatever comes first.

For example, if you have 10 separate sets of 10 posters and all 10 posters within a set intersect with each other, you'll end up with 10^10 solution sets.

I think it's better to wait for the editorial, but I can throw in a few keywords in the meanwhile. Posters form a partial order. Consider A in relation to B, iff they intersect and A is wider than B. Independent set of posters becomes an antichain in terms of order theory. By Dilworth's theorem, it's the same as the minimum number of chains, which can be found with bipartite matching.

@Muthukumaran:  if you define rectangle intersection in the usual sense and construct a graph consisting of rectangles as vertices and edge between Ra and Rb iff Ra intersects Rb, then, the problem reduces to finding the maximum independent vertex set on this graph.  For a general graph, this is known to be NP Hard.

Since this rectangle intersection was defined in a very constrained way, the solution must be able to exploit it.  If you define "A crosses B" iff "the edges caused by A on B while intersecting B are vertical and the edges caused by B intersecting A are horizontal", then the graph will have a special structure.  From the second example, rectangle 1 crosses 2 and 2 crosses 3.  Try to figure out what the special structure is.  (Hint: by definition of "cross", 2 does not cross 1, so, it is a directed graph.)

This is Bipartite maximal matching problem,right?

Oops. Spoiler.

Ahh .. why didn't i think of that !!. Now that you've said it , the bottleneck seems so obvious ... I guess figuring this out would've been an important step towards the actual solution.

thanks a lot :)

Can somebody tell me why am I getting a runtime error,despite it being running quite well in my system:

Here is the link to my code:http://www.codechef.com/viewsolution/253474

Somebody help! ,i cant find any error in my code

Something wrong? Help!

I used the following data (attach later) to test.

I draw these rectanges on a image,

It is easyly to find 21 rectanges
in which there is no two posteres
are intersect with each other.

but when I use  Mark Greve's program to test,
the output is 11.

who can tell me why?

The test data is :
------------------------------------

1

42
0 20 20 80
407 427 20 80
7 34 0 40
27 54 10 30
10 34 60 100
30 54 70 90
47 74 0 40
67 94 10 30
50 74 60 100
70 94 70 90
87 114 0 40
107 134 10 30
90 114 60 100
110 134 70 90
127 154 0 40
147 174 10 30
130 154 60 100
150 174 70 90
167 194 0 40
187 214 10 30
170 194 60 100
190 214 70 90
207 234 0 40
227 254 10 30
210 234 60 100
230 254 70 90
247 274 0 40
267 294 10 30
250 274 60 100
270 294 70 90
287 314 0 40
307 334 10 30
290 314 60 100
310 334 70 90
327 354 0 40
347 374 10 30
330 354 60 100
350 374 70 90
367 394 0 40
387 414 10 30
370 394 60 100
390 414 70 90

--------------------------------------------

^ ... my bruteforce solution does give the answer as 21 (http://pastebin.org/326129) .. so i can confirm with some confidence that the answer is indeed 21.

I tested other solutions too ... for java , only one got right output for your test case but even that one fails for most others i tested including the one i post :/

Test Case :

2
10
104566952 147916623 678630251 940183343
9003277 33083278 13259631 32571745
-143404406 417984435 530812595 916779222
-821275036 825049197 -116313380 522616699
88447868 -948119839 -186205146 -597354365
386215609 -687235206 77231082 -488094271
465724273 -468631398 -809402914 820688263
-58704934 -135115798 342261899 -485357300
422144505 941971265 -60972220 589169242
358482926 -443545977 267310067 -285530109
10
-125945674 305685747 402777714 -640846402
-87795403 -329164920 539284253 -948513636
-141302020 219271881 -31813421 150387932
668263521 -886705769 129186320 275896848
165480317 -314940381 5915929 58945502
100844855 -279211671 13629740 -142774358
-425254002 452284922 130074332 532925093
-296582353 682158130 81657940 -208470299
-347892052 -476857497 -4562865 -51663998
-485187866 981481563 -307793035 -506168448

PS : coincidently , although stephen and keshav's solution give wrong answers to some test cases i tested them on. They seem to always agree with one another on the answers :D

I suppose there's something wrong with the approach itself used by most programmers.

oopsie .. ignore my last two posts. I've been using wrong test cases. x₀ < x₁ and y₀ < y_1.

Can anyone explain me where my algo goes wrong.

I am finding the number of posters that a poster intersects. After finding it for all posters i remove the poster with maximum number of intersections, removing that poster from other poster's list and then doing the same till no poster intersects.

Please tell me where it is wrong or paste a test case ( small one so that i can manually check it ).

Please help :)

liubiaoyong : in case you're still wondering . Like my test cases , your test cases too violate the input restrictions. Like corner of 1st poster (20,20) lies in the middle of the third poster.

harsh :What do you do when more than one poster has the same amount of intersections ? If you choose arbitrarily , you're bound to get wrong answers ... if you test for each of them , you'll end up exceeding the time limit.

And even then, what makes you think removing the one with the maximum number of intersections always ends up giving an optimal answer? Can you prove it? (The answer is no, since it is not true.)

Antarpreet Singh : I'm sorry. you are right.
I haven't noticed that " no corner of any poster will intersect any other poster anywhere. ".

@Stephen ... yes its not, i just wasn't sure enough before. Anyway, the following arrangement of posters definitely proves the approach wrong.

@Antarpreet Singh and Stephen Merriman

Thanks, for clearing that out. And thanks for that poster diagram.

I guess now before proceeding with any algorithm i will now try to prove its correctness first :)

Thanks a lot :).

for c#, Can we use advance data structure like Collection of some Class objects (like to use List?)

When will I be able to submit my solution for this problem?

@Admin : just like to manoj when we can submit solution for problems

This was a June contest problem. The practice version is at http://www.codechef.com/problems/POSTERS/

@ stephen   Can partail problem also opend for practics ??

this month's pricing toll where it is plz give me link  ....

I want share with my solution.

I didn't figure out approach with ordered set, maximal chain and antichans.

So I hardly worked on optimizing Bron-Kerbosch algo for finding largest independent set in the graph.

And finally done it with number of essential optimizations.

It is interesting can someone make my solution fail?

Not by time because I use limited search on number of iterations but with real tricky test

on which my solution will not find answer after 40000 deepings in recursion.

(In my program you see 10000 but obviusly I can increase it to 40000 still running in time)

I hope that if someone find such test I still will be third this month :)

@Anton: You want your "mini" to often be a vertex that does not belong to any maximum independent set. Start with a small graph with a vertex of minimum degree that does not belong to any maximum independent set, and a vertex of maximum degree that does not belong to any maximum independent set either, such as this:

O-O-O
|| |
O-O-O

Of course, this is the overlap graph of a valid test case - no corner overlapping a poster.

Now take 16 copies and add a long thin poster that connects them all. Make sure that in each copy the poster corresponding to the top-right vertex is listed before the others of degree two, and there you go. The correct answer is 48. Your code gives 32, even with way more than 40000 steps allowed.

1
97
0 9 2 5
3 9 8 9
1 6 1 6
2 3 0 7
4 5 0 10
7 8 0 10
10 19 2 5
13 19 8 9
11 16 1 6
12 13 0 7
14 15 0 10
17 18 0 10
20 29 2 5
23 29 8 9
21 26 1 6
22 23 0 7
24 25 0 10
27 28 0 10
30 39 2 5
33 39 8 9
31 36 1 6
32 33 0 7
34 35 0 10
37 38 0 10
40 49 2 5
43 49 8 9
41 46 1 6
42 43 0 7
44 45 0 10
47 48 0 10
50 59 2 5
53 59 8 9
51 56 1 6
52 53 0 7
54 55 0 10
57 58 0 10
60 69 2 5
63 69 8 9
61 66 1 6
62 63 0 7
64 65 0 10
67 68 0 10
70 79 2 5
73 79 8 9
71 76 1 6
72 73 0 7
74 75 0 10
77 78 0 10
80 89 2 5
83 89 8 9
81 86 1 6
82 83 0 7
84 85 0 10
87 88 0 10
90 99 2 5
93 99 8 9
91 96 1 6
92 93 0 7
94 95 0 10
97 98 0 10
100 109 2 5
103 109 8 9
101 106 1 6
102 103 0 7
104 105 0 10
107 108 0 10
110 119 2 5
113 119 8 9
111 116 1 6
112 113 0 7
114 115 0 10
117 118 0 10
120 129 2 5
123 129 8 9
121 126 1 6
122 123 0 7
124 125 0 10
127 128 0 10
130 139 2 5
133 139 8 9
131 136 1 6
132 133 0 7
134 135 0 10
137 138 0 10
140 149 2 5
143 149 8 9
141 146 1 6
142 143 0 7
144 145 0 10
147 148 0 10
150 159 2 5
153 159 8 9
151 156 1 6
152 153 0 7
154 155 0 10
157 158 0 10
-1 160 3 4

Whoops, the formatting didn't work. I'll try again.

O-O-O
|| |
O-O-O

Groan. I give up.

V(G) = {1,2,3,4,5,6}

E(G) = {{1,2},{2,3},{3,4},{4,5},{5,6},{6,1},{2,5},{1,5}}