Page 1 of 2
11297 - Census
Posted: Mon Oct 01, 2007 2:09 am
by Robert Gerbicz
From the problem statement:
Code: Select all
In the first line you will find N (0 <= N <= 500)
But in the first line of sample input I see
Assuming that the problem desription is good I've got RTE for my program. It indicates that the description is wrong. It's really confusing, what is the second number in the first line? Is it the duplication of the N value, or what?!
Re: 11297 - Census
Posted: Mon Oct 01, 2007 2:23 am
by lord_burgos
Robert Gerbicz wrote:From the problem statement:
Code: Select all
In the first line you will find N (0 <= N <= 500)
But in the first line of sample input I see
Assuming that the problem desription is good I've got RTE for my program. It indicates that the description is wrong. It's really confusing, what is the second number in the first line? Is it the duplication of the N value, or what?!
yes this is a mistake, is n and m, but because is just a test case, n is equal to m, mmm, I need to change this part , thanks
Posted: Mon Oct 01, 2007 7:40 am
by mmonish
I got too many WA in this prob. here i post my code. Anyone please help me..
Code: Select all
#include<stdio.h>
#include<string.h>
#include<math.h>
#define SZ 505
#define INF (1 << 30)
int mat[SZ][SZ] , n , ma[SZ][30] , mi[SZ][30] , m;
int main()
{
//freopen("c.in" , "rt" , stdin);
int i , j , k , l , q , a , b , c ,d;
char ch;
scanf("%d%d" , &n , &m);
for(i = 1;i<=n;i++)
for(j = 1;j<=25;j++)
{
ma[i][j] = 0;
mi[i][j] = INF;
}
k = (int) sqrt(m);
for(i = 1;i<=n;i++)
{
for(j = 1;j<=m;j++)
{
scanf("%d" , &mat[i][j]);
j % k == 0 ? l = j/k : l = (j/k)+1;
if(mat[i][j] > ma[i][l]) ma[i][l] = mat[i][j];
if(mat[i][j] < mi[i][l]) mi[i][l] = mat[i][j];
}
}
scanf("%d" , &q);
while(q--)
{
scanf(" %c" , &ch);
if(ch == 'c')
{
scanf("%d%d%d" , &a , &b , &c);
b % k == 0 ? l = b/k : l = (b/k)+1;
mat[a][b] = c;
if(ma[a][l] < c) ma[a][l] = c;
if(mi[a][l] > c) mi[a][l] = c;
}
else
{
scanf("%d%d%d%d" , &a , &b , &c , &d);
c > n ? c = n : c = c;
d > m ? d = m : d = d;
int mir , mar;
mar = 0;mir = INF;
for(i = a;i<=c;i++)
{
l = b;
while(l <= d)
{
if((l-1) % k == 0) break;
if(mar < mat[i][l])
mar = mat[i][l];
if(mir > mat[i][l])
mir = mat[i][l];
l++;
}
l = (l/k)+1;
for( ;l<= d/k;l++)
{
if(mar < ma[i][l])
mar = ma[i][l];
if(mir > mi[i][l])
mir = mi[i][l];
}
l = (d/k)*k+1;
for(;l<=d;l++)
{
if(mar < mat[i][l])
mar = mat[i][l];
if(mir > mat[i][l])
mir = mat[i][l];
}
}
printf("%d %d\n" , mar , mir);
}
}
return 0;
}
Posted: Mon Oct 01, 2007 8:05 am
by sclo
I don't see why your algorithm should work.
Posted: Mon Oct 01, 2007 12:44 pm
by mmonish
>> sclo
Will u tell me why my algorithm shouldn't work. I think if i understand the problem then my algo gives correct ans.
Posted: Mon Oct 01, 2007 1:47 pm
by Lomir
"x1 y1 x2 y2" which represent the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population.
"x y v" indicating a change of the population of city C [x, y] by value v.
q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2
Which input format is right? There are or not characters 'c' and 'q'?
And why the answer to the second query in sample test is 10?
We increace value in row 2 column 3 by 10 and initial value was 2.
So the answer must be 12?
P.S. Could somebody correct all problem defenitions from yesterday contest?
Posted: Mon Oct 01, 2007 6:42 pm
by lord_burgos
mmonish wrote:I got too many WA in this prob. here i post my code. Anyone please help me..
// CODE
Input:
Code: Select all
10 10
3 9 380 28471 29141 12245 0 5957 57 8535
5 9582 224 8649 2763 7 63 42 4462 0
11616 0 4647 4099 5 11 30991 0 32585 1
7 0 16 0 363 0 0 10947 1 31210
0 13 48 5997 8734 325 424 0 5949 18088
146 0 7 664 9175 22785 2055 4433 5783 586
214 31 363 8852 89 0 1748 9217 14348 21473
177 19922 0 2 973 73 27593 15329 71 7
0 2311 16 481 476 646 5081 80 66 36
234 22716 161 1 467 2594 8256 0 18567 0
10
c 7 4 2671
q 8 1 10 3
q 1 3 3 4
c 9 10 6454
c 10 6 1118
c 2 3 5946
c 8 9 3405
q 2 2 10 8
q 1 1 495 493
q 3 5 10 10
Correct Ouput:
Code: Select all
22716 0
28471 224
30991 0
32585 0
32585 0
Posted: Mon Oct 01, 2007 7:07 pm
by anikov
This is a very nice problem, but the problem description is one of the worst I have seen.
And this example is VERY stupid, not showing anything useful.
Posted: Mon Oct 01, 2007 7:27 pm
by sclo
anikov wrote:This is a very nice problem, but the problem description is one of the worst I have seen.
And this example is VERY stupid, not showing anything useful.
I agree. Actually for many problems for this contest, the example is too trivial and it doesn't really help much. And I find some of the problem statement simply doesn't make sense.
Posted: Mon Oct 01, 2007 9:15 pm
by mmonish
>>lord_burgos
Thanks. I do some simple mistake in my implementation.Now i post my modified code which gives the correct ans. But i am getting WA in 1.4 sec.
I tried to figure out my mistake but couldn't. help plz..
Posted: Mon Oct 01, 2007 10:02 pm
by rushel
in tht above test case the dimension of square is 10 * 10
but in the following query x2 = 495 and y2=493
q 1 1 495 493
so there can be test casese like this?
Posted: Mon Oct 01, 2007 10:10 pm
by Lomir
I used N Interval Trees (a tree for each row) to get rather slow AC.
This is really nice problem, expcept for its statement.
Posted: Mon Oct 01, 2007 10:28 pm
by sclo
2d interval tree works here.
Each query and update is O((log n)^2)
Posted: Tue Oct 02, 2007 12:01 am
by Robert Gerbicz
sclo wrote:2d interval tree works here.
Each query and update is O((log n)^2)
There is a method using:
O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query
This is better if there are much more 'c' queries than 'q' queries.
Posted: Tue Oct 02, 2007 6:12 am
by Lomir
O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query
My n intervals work like this.
I think c is less then q, cause got AC only in more then 6sec.
2d interval tree works here.
Each query and update is O((log n)^2)
I know, however i would code it whole night
It's enoght for me to have n interval trees, if they pass TL.