Lighting the shop

""Each line in the next m lines contains n characters '0' or '1'""

Can this program take input as:

1 0 0 1

1 1 0 1

1 0 1 1

1 0 0 1

or it is need to be without spaces..

reply soon admin

Please specify the output clearly or the input format .

@Sumit No.

@Lalit, Sumit Check Sample I/O.

Is this Output Format correct (given m=5, n=4):

4

1 2 3 4

3 0 0 2

2 4 1 0

0 3 2 1

4 1 0 3

---------> Blank line here before the next test case starts

@Aniruddha It is working correct for Sample I/O ...but i m not able to submit.

@mohan ..same here

Greetings admin,

My code runs for large input such as 50x50 on my laptop(intel processor) but while submitting i'm getting SIGKILL error, may I know what is this error and what is about to create such a error in my code.

Thanks in advance

It's hard to say what SIGKILL is exactly, it is a error signal produced by C++. Your program must contain bugs somewhere.

@Stephen,

How on earth did you solve these problems so quickly?

It's a holiday weekend :P

Can anyone confirm that for a matrix of 10x10 with 1's in all locations, there are a total of 22 min colors needed.

Similarly for 100x100 with 1's in all locations, there are a min of 128 colors.

I am getting Wrong Answer, trying to verify if the data is correct.

Thanks.

The data is correct. Extra test cases can't be provided.

Just to clarify: Stephen means the judge data is correct, and I agree. So if you get wrong answer, your program must be wrong.

@Sohail

I think the minimum number of color counted by you are wrong.

Any say in that......

@Md Tareque Khan

Discussing test cases will get you disqualified.

@stephen

Hey, do u know anything about SIGKILL error. what shoud I do. The program rns fine on my laptop for big inputs too.

@stephen

Hey, do u know anything about SIGKILL error. what shoud I do. The program rns fine on my laptop for big inputs too.

@stephen

Hey, do u know anything about SIGKILL error. what shoud I do. The program rns fine on my laptop for big inputs too.

@stephen

Hey, do u know anything about SIGKILL error. what shoud I do. The program rns fine on my laptop for big inputs too.

@stephen

Hey, do u know anything about SIGKILL error. what shoud I do. The program rns fine on my laptop for big inputs too.

@stephen

Did you mean my data is correct or the judge data is correct?  Just need clarification.

Sorry I am new here.  I just read the FAQ.  My question might fall under prohibited rules.  You don't need to answer it.

@Md Khan: please don't post repeated messages :) Try to google about SIGKILL, there's may be some information

@Sohaild: The judge data should be correct as some users have successfully solve the problem.

sry for the repeating comments.........

actually I had a network problem, so that might have caused such a nuissance.......

@Writer

I don't know why people think I am doubting the judge data.  I am not.  I was just trying to verify some data points so that I can isolate if the problem is in my algorithm or simply in input/output.  And I have already found some bugs and have fixed them all and now it is not saying Wrong Answer any more.  However I am now getting TLE, even though I have optimized it a lot.

As mentioned discussing test cases is not allowed. It is your job to debug your program, not other people's.

Input -> The first line contains two numbers m, n (1 <= m, n <= 700).

Are these numbers space separated while giving input?

Of course they are.. if there was no space between them you couldn't tell what m and n were at all. Look at the sample input.

Stephen Merriman

Hi,have u use any standard algorithm for this Problem

I'll tell you in 5 days.

hey i m getting error

/sources/tested.cpp: In function 'int main()': /sources/tested.cpp:4: error: 'cout' was not declared in this scope

can anyone suggest what to do with this error......

Stephen Merriman

Can u telll me how much line of code your program is?plz

@nishant:

I think you should use std::cout instead.

@Mark Greve

You made my 90 something submissions to a problem last contest look like nothing ;)

@Stephen Merriman

I will tell the story later :)

Guys, it's good to see you talking here. I want to ask you a few questions, which are not connected with the contest or problems. How can i become great programmer like you ? What is the formula to success in algorithmic problem solving ? Where did you learned all those stuff, and how can i learn them ? Thank you :)

solve more and more problems ...thats all...

Let G be the graph such that each cell in the matrix is a node and the corresponding cells in the same column and row are its neighbours. Notice that vertex coloring G is equivalent to edge-coloring L(G) where L(G) is the line-graph of G.

If every entry in the mXn matrix were a 1, then the line graph of G is a K(m,n), i.e. a fully connected bipartite graph.It is easy to edge-color a fully connected bipartite graph. If some of the elements were zeros, we again get a bipartite graph. However, this time it is not as easy to edge color this graph as was the case of K(m,n).  To get started with edge-coloring of general bipartite multi-graphs, one might want to look at some of the links available here.

I would recommend looking into algorithms that are based on some sort of augmentation instead of going for divide-and-conquer approaches using Euler tour and perfect bipartite matching as subroutines. Even though the asymptotic performance is much worse for the augmentation approaches (I even doubt it would run in time on a just a few worst case test cases), it works a lot better on the test cases for this problem. I spent like 130 submissions on getting the divide-and-conquer approach to run in time... But I do see that others have managed to squeeze it inside the time limit.

My augmenting algorithm timed out, so I switched to divide and conquer, only to eventually discover that my problem was actually that I was doing output too slow.  So I ended up with a hybrid, doing augmentation until the maximum degree is a power of 2, then switching to divide and conquer.  I also added a special case for when the maximum degree was equal to the larger dimension of the grid, which appeared to catch at least one big test case.

The bottleneck of augmentation approach was checking if endpoints of an edge have a common free color. The lengths of paths which need to be augmented was surprisingly small (around 10 on my 200x200 cases). AND-ing bitmasks of free colors gave me a 16x speed-up which was good enough.

Usually in order to decrease the execution time (increase the speed) you have to pay penalty in terms of memory used.  Hats off to Adrian, he achieved it with the least time and least memory.

I used the augmenting path approach. Namely, greedily fill in cells using the smallest colour that hasn't been used in the row/column. If no colour is available, find the smallest unused in the row (x), and smallest unused in the column (y). Fill this cell with an x; replace the x in the column with a y; replace the y in that row with an x, etc.

To find the smallest in each row/column/combined I used bitmasks; an array of 24 ints (each storing 30 bits) was enough to pass in time, allowing you to skip 30 colours at a time.

I also used the augmenting path approach, however I didn't use the greedy part because as Stephen already said, it is expensive to find which color is unused in row x and column y. Instead I determined an unused color c in row x. If this color does not occur in column y, we are done. Otherwise find a color c2 which does not occur in column y. If this color does not occur in row x, again we are done. Otherwise use augmenting path method and switch colors c and c2. I found out by doing a random_shuffle on the available colors for each column in the beginning, the augmenting path method takes about 4.8 steps on average for each cell on a 700 x 700 grid with all 1s.

Btw, this problem was already posed with smaller limits in an UVA contest: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&cat...