## 11297 - Census

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

Moderator: Board moderators

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
can anybody give me some tricky test cases for this problem. I tried the problem with static binary tree.

At last I got AC in 0.950
using O(lgn^2)
this problem is nice one.

THANKS TO THE PROBLEM SETTER

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 11297 - Census

This very weird that, brute force approaches get AC. I was trying to do it using a segment tree, but getting wrong answers. Can anyone help? It passes forum cases and some cases of my own as well. Can't find why it failed.

Code: Select all

``````Accepted
``````
Sorry for such a huge code, actually, after getting 3 wrong answers, I separated each call in a if block for debugging purpose. Also, the statement is quite confusing.

Got AC, problem was in update process.
You should not always say what you know, but you should always know what you say.

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

### Re: 11297 - Census

Code ``Accepted". Problem in updating the segment when the one being updated is the current max/min node.
Last edited by pranon on Wed Oct 10, 2012 9:39 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11297 - Census

Your code assumes n==m.
Check input and AC output for thousands of problems on uDebug!

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

### Re: 11297 - Census

Code: Select all

``Code ``Accepted". Problem in updating the segment when the one being updated is the current max/min node.``
Last edited by pranon on Wed Oct 10, 2012 9:40 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11297 - Census

Input:

Code: Select all

``````10 11
83 86 77 15 93 35 86 92 49 21 62
27 90 59 63 26 40 26 72 36 11 68
67 29 82 30 62 23 67 35 29 2 22
58 69 67 93 56 11 42 29 73 21 19
84 37 98 24 15 70 13 26 91 80 56
73 62 70 96 81 5 25 84 27 36 5
46 29 13 57 24 95 82 45 14 67 34
64 43 50 87 8 76 78 88 84 3 51
54 99 32 60 76 68 39 12 26 86 94
39 95 70 34 78 67 1 97 2 17 92
50
c 7 6 41
c 10 7 29
q 8 5 10 8
c 10 3 97
q 7 6 9 11
c 5 1 29
c 10 11 15
c 10 3 45
q 2 6 4 7
c 5 7 93
c 5 10 87
q 4 1 7 5
q 7 10 10 10
q 6 4 10 11
q 6 10 8 11
q 9 9 10 11
q 10 5 10 11
c 4 3 4
q 9 2 10 10
c 7 5 83
c 10 2 90
q 10 3 10 5
q 3 9 8 11
c 5 7 28
c 4 11 22
q 1 1 2 4
c 9 5 44
c 3 10 82
c 5 3 0
c 3 6 68
c 4 5 33
q 1 2 10 5
q 7 3 8 6
c 1 8 84
c 1 1 36
c 6 9 87
q 9 2 10 4
c 1 1 1
q 3 3 10 7
q 2 10 3 10
q 8 3 8 5
c 5 10 22
c 7 11 92
q 3 1 4 6
c 10 11 13
q 1 11 1 11
q 10 8 10 8
q 5 7 10 11
c 1 6 79
q 4 7 7 7``````
AC output:

Code: Select all

``````97 8
94 3
67 11
98 13
86 3
97 2
67 3
94 2
97 2
99 2
78 34
91 2
90 15
99 0
87 8
99 32
96 0
82 11
87 8
93 4
62 62
97 97
97 2
82 25``````
You can also use uvatoolkit.com for this problem.
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 4
Joined: Thu Nov 24, 2011 3:29 am

### Re: 11297 - Census

For anyone who still have doubts about the problem description:

1. The country is divided in N x M regions, where (1 <= N, M <= 500). [It is not N x N as stated.]

2. All coordinates are given as (ROW, COLUMN), where (1 <= ROW <= N) and (1 <= COLUMN <= M). For instance, region (1, 2) is the region of row 1 and column 2. [It does not follow the conventional use of X and Y for column and row, respectively.] A rectangle grid is defined by its upper-left coordinate and then its bottom-right coordinate.

3. The queries are either "q R1 C1 R2 C2", where (R1, C1)-(R2, C2) defines a grid containing one or many regions; or "c R C V", where V is the new value for region (R, C). [The description is faulty, but the example is correct.]

Therefore, the input for the problem is better described along these lines:

In the first line you will find N and M, respectively the number of rows and columns of the country map, where (1 <= N, M <= 500). The next N lines contain M integers each and describe the population of each region, that is, the j-th column of the i-th row denotes the population of region (i, j), where (1 <= i <= N, 1 <= j <= M). The next line contains the number of queries Q, where (Q <= 40000), followed by Q lines representing the queries. Each query has one of the following formats: (1) the character 'q' followed by four integers R1 C1 R2 C2, which describe a rectangular grid of upper-left coordinate (R1, C1) and bottom-right coordinate (R2, C2), where (1 <= R1, R2 <= N and 1 <= C1, C2 <= M); or (2) the character 'c' followed by three integers R C V, which describe the new population value of the region of coordinate (R, C), where (1 <= R <= N, 1 <= C <= M).

For each 'q'-query, you must output the greatest population among all regions inside the specified grid, as well as the least population, is this order. For each 'c'-query, you must change the population value of region (R, C) to the new value that was given.

Sample input:

Code: Select all

``````5 5
1 2 3 4 5
0 9 2 1 3
0 2 3 4 1
0 1 2 4 5
8 5 3 1 4
4
q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2
``````
Explanation:

The country is defined by 5x5 regions, where the matrix that represents the population distribution is given is the following five lines. Next, there are four queries. The first inquires about the regions on the grid (1,1)-(2,3), that is,
1 2 3
0 9 2
The second updates the value of region (2, 3), which was previously 2, to the new value of 10. The third query inquires about all regions, and the last query inquires about the regions on the grid (1,2)-(2,2):
2
9

Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

### Re: 11297 - Census

After struggling with this problem for several hours....

The problem input has been changed/corrected. The board is now actually N x N and N is listed only once in the input. Sample inputs found here and on UDebug are now no longer correct!

It's great that these problems are getting fixed. But it would also be great if it were mentioned somewhere...

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 11297 - Census

Zwergesel wrote:The problem input has been changed/corrected. The board is now actually N x N and N is listed only once in the input. Sample inputs found here and on UDebug are now no longer correct!
This has now been fixed on uDebug. Please see

http://www.udebug.com/UVa/11297
Zwergesel wrote:It's great that these problems are getting fixed. But it would also be great if it were mentioned somewhere...
uDebug is proud to be community-powered. So, we rely on users like you to fix issues such as the one you highlighted. In the future, if you see something you think is off or needs fixing on uDebug, please reach out to us directly using one of the methods mentioned in the link below and we'll surely get back to you and do our best to set things right.

http://www.udebug.com/faq#team-udebug-section

Thank you for your help!
Check input and AC output for over 7,500 problems on uDebug!

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 11297 - Census

After using assert, the test data may contains some bug. In query, there may be some coordinate value which is bigger than given N, for example:

Code: Select all

``````2
1 2
1 3
1
q 1 1 20 20
``````
In my AC code, I output 0 in this situation.