11110 - Equidivisions

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

Re: 11110 - Equidivision

Post by SyFyKid » Fri May 11, 2012 6:57 pm

To those, who didnt solve this problem: DONT READ THIS THREAD :lol:
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 :evil:

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 :lol:

Good luck!

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

Re: 11110 - Equidivision

Post by Muftee_Ruet » Thu Nov 22, 2012 1:49 pm

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. :lol:

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11110 - Equidivisions

Post by lighted » Wed Dec 24, 2014 11:42 am

mrahman wrote: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.
TimeString wrote:- 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.
Robert Gerbicz wrote: 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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 11110 - Equidivisions

Post by Zyaad Jaunnoo » Mon Mar 02, 2015 5:31 pm

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 :roll: ).
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!

Post Reply

Return to “Volume 111 (11100-11199)”