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

Post by rushel » Tue Oct 02, 2007 9:06 pm

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
Location: CSE-DU, Bangladesh
Contact:

Re: 11297 - Census

Post by zobayer » Tue Dec 28, 2010 1:29 pm

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

Post by pranon » Tue Sep 25, 2012 4:20 pm

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

Post by brianfry713 » Tue Sep 25, 2012 11:05 pm

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

Post by pranon » Tue Sep 25, 2012 11:08 pm

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

Post by brianfry713 » Fri Sep 28, 2012 9:26 pm

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!

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

Re: 11297 - Census

Post by danieldonadon » Fri Feb 14, 2014 9:38 pm

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

Post by Zwergesel » Wed Oct 21, 2015 6:03 pm

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! :x :-? :roll:

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

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

Re: 11297 - Census

Post by uDebug » Thu Nov 05, 2015 7:39 am

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! :x :-? :roll:
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!

Find us on Facebook. Follow us on Twitter.

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

Re: 11297 - Census

Post by metaphysis » Fri Jan 11, 2019 11:38 am

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.

Post Reply

Return to “Volume 112 (11200-11299)”