11110 - Equidivisions

[SyFyKid]

To those, who didnt solve this problem: DONT READ THIS THREAD
after getting 5-7 WAs I found bug in my dfs , but before that I have read this thread and rewrote my program for about 4-6 times

This test should help:

Code: Select all

3
1 1 1 2 1 3 2 1 3 1
2 2

output:

Code: Select all

wrong

thats all... no extra spaces... no extra lines... just extra values

Good luck!

[Muftee_Ruet]

Interesting problem.

The tricky part is input parsing. Input should be taken as string.
And another important thing is

An equidivision of an n x n square array of cells is a partition of the n^2 cells in the array in exactly n sets, each one with n contiguous cells.

Try the problem.

[lighted]

input #

Code: Select all

2
1 2 0 0
5
0 0 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1 3
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4
0

Problem description says

It is understood that a cell in an n x n square array is denoted by a pair (i, j), with 1 <= i, j <= n

Judge's input don't contain cell coordinates having value equal to 0 or greater n.

- A line may not contain exactly 2*N numbers, maybe less than it, maybe more than it. Moreover, it is possible that there are no numbers in this line!! So if you use C or C++, you'd better use gets().

I checked that each line contains at least 2 * N numbers, so it can't be less or no numbers or empty line.

3. If there are odd number of numbers in a line then the answer is wrong.

As TimeString pointed there will be even number of input numbers in a line.

[Zyaad Jaunnoo]

Thanks for the information shared on this thread! Otherwise, it would have been difficult to guess where my program went wrong.

To contribute my 2 cents, I considered the following and got accepted:
1) A region may not necessarily contain n pairs of coordinates (it can be 0 as well ).
2) If a region size is less than n, consider the output as wrong.
3) If a region is discovered more than once, consider the output as wrong.
4) The total number of *distinct* regions should be equal to n.
5) I assumed that all values are in the range [1..n].

Hope the above points will help you in solving this problem.

Cheers!