OJ Board

I cant understand one thing, my pc is slow there is no doubt about that, it took approximately 8s, but in judge pc it got AC in only 0.76s. but when i asked official to check my code against judge pc it was more than 3s. But on the same data it is only 0.76s now! how did it happen? anybody any idea?

the problem can be reduced to a matching problem.

do a binary search

Well... convert the lines into angle, it will make the problem very easy

yes, as mf said it is nothing but plain implementation of Kuhn-Munkres. But i thought it will be solved least. Unfortunately and very surprisingly it was the first problem which got accepted in the contest.

Well when i set this problem i was looking for an O(N) algorithm. But i could not find. After that i implemented an NlgN version which used BST which is quite hard to code. I completely overlooked modified closest pair solution. So i though it was going to be one of the hardest. But now i can see ...

can you please describe it a bit more?

i did as adrian said during onsite and got AC

use seive like method and dont sort them explicitly.

YUPPY!!!

GOT AC

My timing is, .890s. I am not sure, but you people may try it with N^2 algorithm.

My algorithm is: Computing the first part in NlgN.
Then doing the second part in also NlgN time.

ya i saw that this morning, (some one gave the link at TC forum).

But how the judge says that the first part is easy to compute? To me the second part is easy to compute. And for the first part i cant think of other way than using NlgN union of rectangle! Now if the judge wants to say that NlgN ...

well there is a problem with the union of rectangle procedure. note that some rectangle may get out of board. and in that case what to do? coz then only making union does not work!

i think checking intersecting fact is going to take way more than N^2 in worst case!

Think about handling the white cells and black cells seperately.

But after that i dont know. AFAIK the NlogN solution (Klee's method) for Union of rectangle is too complex to code. And N^2 seems not to be feasible here! So i am not sure what to do from here!

If NlogN is the one that is to be used ...

well i had lots of trouble witht he input system. so those who will try this problem for them:

(here: W is string, board[][] is char and others are int)


cin>>cases;
for(ks=1;ks<=cases;ks++)
{
cin>>d;

for(i=1;i<=d;i++)
{
cin>>W;
if(W.size()<=100) //<---- this is important. without it u ...