11297 - Census

[rushel]

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]

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.

Thanks in advance.

Got AC, problem was in update process.

[pranon]

Code ``Accepted". Problem in updating the segment when the one being updated is the current max/min node.

[brianfry713]

Your code assumes n==m.

[pranon]

Code: Select all

Code ``Accepted". Problem in updating the segment when the one being updated is the current max/min node.

[brianfry713]

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.

[danieldonadon]

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]

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]

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

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!

[metaphysis]

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.