11297  Census
Moderator: Board moderators

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11297  Census
Got AC, problem was in update process.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.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.Code: Select all
Accepted
Thanks in advance.
You should not always say what you know, but you should always know what you say.
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.

 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!
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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11297  Census
Input:AC output:You can also use uvatoolkit.com for this problem.
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
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
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 upperleft coordinate and then its bottomright 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 jth column of the ith 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 upperleft coordinate (R1, C1) and bottomright 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:
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
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 upperleft coordinate and then its bottomright 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 jth column of the ith 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 upperleft coordinate (R1, C1) and bottomright 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
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
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...
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...
Re: 11297  Census
This has now been fixed on uDebug. Please seeZwergesel 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!
http://www.udebug.com/UVa/11297
uDebug is proud to be communitypowered. 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.Zwergesel wrote:It's great that these problems are getting fixed. But it would also be great if it were mentioned somewhere...
http://www.udebug.com/faq#teamudebugsection
Thank you for your help!

 Experienced poster
 Posts: 138
 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:
In my AC code, I output 0 in this situation.
Code: Select all
2
1 2
1 3
1
q 1 1 20 20
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.