The problem with an O(n^6) algorithm is that you get a time limit error in UVA. Forums claim that you need an O(n^4) algorithm or better to have your code accepted. According to the algorithmist, if you use kadane's algorithm, you can reach an astonishing O(n^3): only 3 for loop implementation which has very fast execution time. Forums recommend using dynamic programming too.
But the problem is, what in the world is dynamic programming?
I've heard about dynamic programming a lot of times in the past, but I really don't know what it is. My computer science professor tried to explain it to me in the past. The way I understand it is that you use previous results in order to build the results of the current cases which are bigger than the previous cases.
Which makes sense in our case, right? In this problem, we're counting the sums of rectangles. But if you think about it, a big rectangle is composed of several smaller rectangles. If you know the sums of the smaller rectangles, then you can use those sums to solve for the sum of the cells for the big rectangle. In essense, that is what dynamic programming is. We solve for the sum of a big rectangle by using the sums of the smaller rectangles which comprise the big rectangle. And these sums of the smaller rectangles were previously obtained.
People say that dynamic programming is like recursion but with the use of memory. In our problem, we are using memory to store the results of the sums of smaller rectangles so that we can recall these smaller sums to solve for the sums of larger rectangles later on.
Consider the implementation below. In particular, let us take a look at the 3 for loops beginning at line 49. Here we are considering the rectangles with sizes 1x2, 1x3, 1x4, 1x5, ... 1xn. For each size, we consider the rectangles of such sizes at coordinates (1,1), (1,2), (1,3), ..., (2,1), (2,2), ...
Initially, the sumsA array is simply a replica of the original input matrix. To solve for the 1x2 rectangles, we note that a 1x2 rectangle is composed of two 1x1 rectangles that are adjacent to each other horizontally. So, to solve for the sum of a 1x2 rectangle, we simply add the sums of the smaller 1x1 rectangles that comprise it. After solving for the sums of the 1x2 rectangles, we update sumsA array so that it contains the 1x2 rectangular sums.
To solve for 1x3 rectangles, we note that 1x3 rectangles are composed of a 1x2 rectangle and a 1x1 rectangle connected adjacently horizontally. So, in essense, to get the sum of a 1x3 rectangle, we can simply add the sum of its 1x2 rectangle and its 1x1 rectangle. Take note, however, that the 1x2 rectangular sums have been previously saved in the array sumsA. Also the 1x1 rectangular sums are simply stored already in the original array, arr. So, we can simply add the corresponding cells in sumsA and arr to arrive at the 1x3 rectangular sums.
Once we obtain the 1x3 sums, we store these in sumsA array overwriting the previously stored 1x2 sums. We overwrite the 1x2 sums because we don't need these data anymore. To build the 1x4 sums, we simply add the 1x3 sums with the 1x1 sums. So, we don't need to store the 1x2 sums anymore. As a note, notice that we store the sums for each successive rectangle considered. This is what dynamic programming is about. Storing previous results so that we can use them later on to build results for larger cases -- larger rectangles. We use the 1x3 result to solve for the 1x4 results.
Once the 1x4 sums are obtained, these are stored in sumsA, and these in turn are used to build the 1x5 sums by adding the 1x4 sums with the 1x1 sums. We continue the process until we reach the 1xn size. Remember that for each size, we have to consider all rectangles of such size at all possible beginning coordinates: (1,1), (1,2), (1,3), ..., (2,1), (2,2)...
After considering 1x1, 1x2, ..., 1xn rectangles, we consider the rectangles of sizes 2x1, 3x1, 4x1, 5x1, ..., nx1. This is what you see starting at line 63.
Let's start first with the 2x1 rectangle. We use a sumsB array which is initially set to have the same contents as the original input matrix, arr. We note that a 2x1 rectangle is composed of two 1x1 rectangles adjoined vertically. Therefore, to get the sum of a 2x1 rectangle, we add the sum of a 1x1 rectangle (from sumsB) and another sum of a 1x1 rectangle (from arr). (line 67)
Again we store the 2x1 sums in sumsB overwriting the previous 1x1 sums. We do this because if we are going to solve for the 3x1 sums, we need to have the 2x1 sums ready since a 3x1 rectangle is formed from a 2x1 rectangle and a 1x1 rectangle. Similarly, to solve for the 4x1 rectangle, we can simply add the sum for a 3x1 rectangle and 1x1 rectangle.
Note, however, that after solving for the 2x1 sums, instead of proceeding to solve for the 3x1 sums, we do something else (line 76). We solve for the 2x2 rectangular sums, the 2x3 sums, the 2x4 sums, etc. Why is that?
Observe that a 2x2 rectangle can be thought of as formed from a 2x1 rectangle and another 2x1 rectangle joined together horizontally beside each other. The 2x1 sums were previously stored in sumsB, but they were also stored in sumsA array (lines 68-69). Therefore, to solve for a 2x2 rectangle, we sum the corresponding sums from sumsA (2x1 sums) with the sums in sumsB (2x1 sums).
The resulting 2x2 sums are stored in sumsA overwriting the previous 2x1 sum contents. We overwrite because we need the updated 2x2 sums to solve for the 2x3 rectangles. A 2x3 rectangle can be thought of as formed by adjoining a 2x2 rectangle with a 2x1 rectangle horizontally. Notice that we did not overwrite the contents of sumsB which contains 2x1 sums. So, to solve for the 2x3 sums, we add the sums from sumsA (2x2 sums) with the sums in sumsB (2x1 sums). We repeat the process for 2x4, 2x5, ..., 2xn rectangles.
We then solve for the 3x1 rectangles using the sumsB array which contains the 2x1 sums (line 63). After solving for the 3x1 rectangles which are now stored in sumsB (2x1 contents overwritten (line 68), we solve for the 3x2 rectangles by noting that we can solve 3x2 rectangles by adding two 3x1 rectangles (sumsA and sumsB which both contain 3x1 sums (lines 68-69). I'm tired, I think you get how the algorithm goes.
Bottom line is you end up with an O(n^4) algorithm (only max of 4 embedded for-loops). This results to an accepted solution in UVA. This implementation ran in 0.062 seconds in UVA. I still have to learn about Kadane's algorithm which results in O(n^3).
1 #include "stdio.h"
2 #include "string.h"
3 #include "stdlib.h"
4 int main() {
5 const int lsize = 100000;
6 char line[lsize];
7 int n, x, y, r, c, i, j, k;
8 int p, q, s, t, u, v;
9 int max, sum;
10 char *pch;
11 int arr[150][150];
12 int sumsA[150][150];
13 int sumsB[150][150];
14 fgets(line, lsize, stdin);
15 sscanf(line, "%d", &n);
16 r = c = 1;
17 while (fgets(line, lsize, stdin)) {
18 pch = strtok(line, " \t\n");
19 while (pch) {
20 x = atoi(pch);
21 arr[r][c] = x;
22 c += 1;
23 if (c > n) {
24 r += 1;
25 c = 1;
26 }
27 pch = strtok(NULL, " \t\n");
28 }
29 }
30 // for (r = 1; r <= n; r += 1) {
31 // for (c = 1; c <= n; c += 1) {
32 // printf("%d ", arr[r][c]);
33 // }
34 // printf("\n");
35 // }
36 max = arr[1][1];
37 // printf("1x1\n");
38 for (i = 1; i <= n; i += 1) {
39 for (j = 1; j <= n; j += 1) {
40 sum = arr[i][j];
41 sumsA[i][j] = sum;
42 sumsB[i][j] = sum;
43 if (sum > max) {
44 max = sum;
45 }
46 }
47 }
48 // printf("1x2, 1x3, 1x4, ...\n");
49 for (i = 2; i <= n; i += 1) {
50 x = n - i + 1;
51 for (j = 1; j <= n; j += 1) {
52 for (k = 1; k <= x; k += 1) {
53 sum = sumsA[j][k] + arr[j][k+i-1];
54 sumsA[j][k] = sum;
55 if (sum > max) {
56 max = sum;
57 }
58 // printf("%d %d %d = %d\n", i, j, k, sum);
59 }
60 }
61 }
62 // printf("2x1, 3x1, 4x1, ...\n");
63 for (i = 2; i <= n; i += 1) {
64 x = n - i + 1;
65 for (j = 1; j <= x; j += 1) {
66 for (k = 1; k <= n; k += 1) {
67 sum = sumsB[j][k] + arr[j+i-1][k];
68 sumsB[j][k] = sum;
69 sumsA[j][k] = sum;
70 if (sum > max) {
71 max = sum;
72 }
73 // printf("%d %d %d = %d\n", i, j, k, sum);
74 }
75 }
76 // printf("\t%dx2,3,4,...\n", i);
77 for (s = 2; s <= n; s += 1) {
78 y = n - s + 1;
79 for (j = 1; j <= x; j += 1) {
80 for (k = 1; k <= y; k += 1) {
81 sum = sumsA[j][k] + sumsB[j][k+s-1];
82 sumsA[j][k] = sum;
83 if (sum > max) {
84 max = sum;
85 }
86 // printf("\t%d %d %d %d = %d\n", i, s, j, k, sum);
87 }
88 }
89 }
90 }
91 printf("%d\n", max);
92 return 0;
93 }
Saturday, January 31, 2015
108: Maximum sum
The first time I saw this problem was about in year 2006. The problem was in a programming contest orientation. Back then, I remember I think I was able to solve the problem. So this time, when I saw the same problem in uVA after more than 9 years, I was pretty confident I could resolve the problem.
I did resolve the problem and I was confident that my solution would get accepted. Then, came the bad news. My solution was rejected with a time limit error. I was appalled. Didn't know what to do beyond a brute force algorithm.
I read through the discussions in the internet and they said that you need at least an O(n^4) algorithm in order for your solution to get accepted. This means that the time by which your algorithm executes should be a polynomial function of the number of inputs, but the polynomial function should only be a variant of n raised to 4, where n is the number of inputs. In other words, time of execution = f(n^4). Another way to put it is that your algorithm should only have a maximum of 4 embedded for loops:
for (...) { for (...) { for (...) { for (...) {...} } } }
My original algorithm was O(n^6) consisting of 6 embedded for loops. I tried running my solution using an i5 machine for a 100x100 input. It took about 2.5 minutes to execute. The machine uVA uses for judging uses a weaker machine than an i5 probably, that's why I got a time limit.
My original algorithm uses a brute force approach and considers all possible rectangles beginning with 1x1 rectangles. A 1x1 rectangle is simply a rectangle consisting of 1 cell. Then the algorithm considers all 1x2 rectangles. A 1x2 rectangle is a rectangle consisting of 2 cells aligned horizontally. Then, the algorithm considers all 1x3 rectangles, 1x4 rectangles, up to 1xn rectangles where n is the total number of columns of the input.
Then the algorithm considers 2x1 rectangles (2 cells aligned vertically). Then, 2x2 rectangles (4 cells arranged as a square). Then 2x3 rectangles, 2x4 rectangles, etc up to 2xn rectangles.
The algorithm keeps continuing until the nxn rectangle is considered. The algorithm then stops. For each rectangle considered, the sum of the cells in the rectangle is compared against a maximum. If the sum is greater than the maximum sum previously obtained, then the maximum is updated.
For each dimension, the algorithm considers all possible rectangles at all possible positions in the matrix. For instance, for 1x1 rectangles, the algorithm considers the rectangle at coordinates (1,1), the rectangle at coordinates (1,2), at (1,3)...at (1,n), the rectangle at coordinates (2,1), (2,2), (2,3), ...(2,n), up to (n,n). The same goes with 1x2 rectangles. All 1x2 rectangles at all possible beginning coordinates are considered: (1,1), (1,2), (1,3), ... (1,n-1).
This is why 6 loops are needed: The first two outmost loops are for generating all dimensions: 1x1 rectangles, 1x2 rectangles, 1x3, 1x4, ..., 1xn, 2x1, 2x2, 2x3, ... 2xn, ... nxn. The next two for loops are for considering the rectangles at all possible beginning coordinates. For instance, for 1x2 rectangles, we consider such rectangles at coordinates (1,1), (1,2), (1,3), ... (1, n-1), (2,1), (2,2), (2, n-1), ... (n, n-1). The last two inmost for loops are for computing the sum of the cells in each rectangle considered. For instance, for computing the sum of the cells for the 1x2 rectangle which has beginning coordinates at say (2,3).
Here is the brute force implementation. Remember that this is O(n^6). Six embedded for loops, and it isn't accepted by UVA because of time limit problem. UVA requires solutions that take less than 3 seconds. Can you see the six embedded for loops in the code?
1 #include "stdio.h"
2 #include "string.h"
3 #include "stdlib.h"
4 int main() {
5 const int lsize = 100000;
6 char line[lsize];
7 int n, x, y, r, c, i, j;
8 int p, q, s, t, u, v;
9 int max, sum;
10 char *pch;
11 int arr[150][150];
12 fgets(line, lsize, stdin);
13 sscanf(line, "%d", &n);
14 r = c = 1;
15 while (fgets(line, lsize, stdin)) {
16 pch = strtok(line, " \t\n");
17 while (pch) {
18 x = atoi(pch);
19 arr[r][c] = x;
20 c += 1;
21 if (c > n) {
22 r += 1;
23 c = 1;
24 }
25 pch = strtok(NULL, " \t\n");
26 }
27 }
28 // for (r = 1; r <= n; r += 1) {
29 // for (c = 1; c <= n; c += 1) {
30 // printf("%d ", arr[r][c]);
31 // }
32 // printf("\n");
33 // }
34 max = arr[1][1];
35 for (i = 1; i <= n; i += 1) {
36 x = n - i + 1;
37 for (j = 1; j <= n; j += 1) {
38 // printf("%d %d\n", i, j);
39 y = n - j + 1;
40 for (p = 1; p <= x; p += 1) {
41 u = p + i - 1;
42 for (q = 1; q <= y; q += 1) {
43 sum = 0;
44 v = q + j - 1;
45 for (r = p; r <= u; r += 1) {
46 for (c = q; c <= v; c += 1) {
47 sum += arr[r][c];
48 }
49 }
50 // printf("%d %d %d %d = %d\n", i, j, p, q, sum);
51 if (sum > max) {
52 max = sum;
53 }
54 }
55 }
56 }
57 }
58 printf("%d\n", max);
59 return 0;
60 }
I did resolve the problem and I was confident that my solution would get accepted. Then, came the bad news. My solution was rejected with a time limit error. I was appalled. Didn't know what to do beyond a brute force algorithm.
I read through the discussions in the internet and they said that you need at least an O(n^4) algorithm in order for your solution to get accepted. This means that the time by which your algorithm executes should be a polynomial function of the number of inputs, but the polynomial function should only be a variant of n raised to 4, where n is the number of inputs. In other words, time of execution = f(n^4). Another way to put it is that your algorithm should only have a maximum of 4 embedded for loops:
for (...) { for (...) { for (...) { for (...) {...} } } }
My original algorithm was O(n^6) consisting of 6 embedded for loops. I tried running my solution using an i5 machine for a 100x100 input. It took about 2.5 minutes to execute. The machine uVA uses for judging uses a weaker machine than an i5 probably, that's why I got a time limit.
My original algorithm uses a brute force approach and considers all possible rectangles beginning with 1x1 rectangles. A 1x1 rectangle is simply a rectangle consisting of 1 cell. Then the algorithm considers all 1x2 rectangles. A 1x2 rectangle is a rectangle consisting of 2 cells aligned horizontally. Then, the algorithm considers all 1x3 rectangles, 1x4 rectangles, up to 1xn rectangles where n is the total number of columns of the input.
Then the algorithm considers 2x1 rectangles (2 cells aligned vertically). Then, 2x2 rectangles (4 cells arranged as a square). Then 2x3 rectangles, 2x4 rectangles, etc up to 2xn rectangles.
The algorithm keeps continuing until the nxn rectangle is considered. The algorithm then stops. For each rectangle considered, the sum of the cells in the rectangle is compared against a maximum. If the sum is greater than the maximum sum previously obtained, then the maximum is updated.
For each dimension, the algorithm considers all possible rectangles at all possible positions in the matrix. For instance, for 1x1 rectangles, the algorithm considers the rectangle at coordinates (1,1), the rectangle at coordinates (1,2), at (1,3)...at (1,n), the rectangle at coordinates (2,1), (2,2), (2,3), ...(2,n), up to (n,n). The same goes with 1x2 rectangles. All 1x2 rectangles at all possible beginning coordinates are considered: (1,1), (1,2), (1,3), ... (1,n-1).
This is why 6 loops are needed: The first two outmost loops are for generating all dimensions: 1x1 rectangles, 1x2 rectangles, 1x3, 1x4, ..., 1xn, 2x1, 2x2, 2x3, ... 2xn, ... nxn. The next two for loops are for considering the rectangles at all possible beginning coordinates. For instance, for 1x2 rectangles, we consider such rectangles at coordinates (1,1), (1,2), (1,3), ... (1, n-1), (2,1), (2,2), (2, n-1), ... (n, n-1). The last two inmost for loops are for computing the sum of the cells in each rectangle considered. For instance, for computing the sum of the cells for the 1x2 rectangle which has beginning coordinates at say (2,3).
Here is the brute force implementation. Remember that this is O(n^6). Six embedded for loops, and it isn't accepted by UVA because of time limit problem. UVA requires solutions that take less than 3 seconds. Can you see the six embedded for loops in the code?
1 #include "stdio.h"
2 #include "string.h"
3 #include "stdlib.h"
4 int main() {
5 const int lsize = 100000;
6 char line[lsize];
7 int n, x, y, r, c, i, j;
8 int p, q, s, t, u, v;
9 int max, sum;
10 char *pch;
11 int arr[150][150];
12 fgets(line, lsize, stdin);
13 sscanf(line, "%d", &n);
14 r = c = 1;
15 while (fgets(line, lsize, stdin)) {
16 pch = strtok(line, " \t\n");
17 while (pch) {
18 x = atoi(pch);
19 arr[r][c] = x;
20 c += 1;
21 if (c > n) {
22 r += 1;
23 c = 1;
24 }
25 pch = strtok(NULL, " \t\n");
26 }
27 }
28 // for (r = 1; r <= n; r += 1) {
29 // for (c = 1; c <= n; c += 1) {
30 // printf("%d ", arr[r][c]);
31 // }
32 // printf("\n");
33 // }
34 max = arr[1][1];
35 for (i = 1; i <= n; i += 1) {
36 x = n - i + 1;
37 for (j = 1; j <= n; j += 1) {
38 // printf("%d %d\n", i, j);
39 y = n - j + 1;
40 for (p = 1; p <= x; p += 1) {
41 u = p + i - 1;
42 for (q = 1; q <= y; q += 1) {
43 sum = 0;
44 v = q + j - 1;
45 for (r = p; r <= u; r += 1) {
46 for (c = q; c <= v; c += 1) {
47 sum += arr[r][c];
48 }
49 }
50 // printf("%d %d %d %d = %d\n", i, j, p, q, sum);
51 if (sum > max) {
52 max = sum;
53 }
54 }
55 }
56 }
57 }
58 printf("%d\n", max);
59 return 0;
60 }
Saturday, January 24, 2015
113: power of cryptography
I don't like this problem because it dwells more on technicality than logic. The first time I saw this problem, I did not know how to solve it because I thought that you're suppose to only use integers. The problem said that the program should be able to handle numbers as large as p = 10^101, but integers can only handle up to 2^64 for unsigned long long int. 2^64 is smaller than 10^101. And so I was stuck. I was thinking do I have to use a class for very big integers.
I looked at the discussions in the Internet and discovered that you could actually just use double type, which is kind of smart. double type can handle numbers as large as 10^300. float type however cannot do because float I think can only handle up to 10^38.
Using double gives us a whole range of mathematical powers. We can use the cmath library to raise the number p to the fraction (1/n) to get the nth root of p.
I read the forums and they said that the correct way to read a double using scanf is to use %lf. In printing the double, I initially used %d and casting the double to an integer. Unfortunately, this did not work and I got wrong answers. probably because the specs mentions that k should be able to handle up to 10^9, while %d which corresponds to an integer can only handle up to 2^31.
Again I consulted the forums and they told me to use %.0lf in printf. The .0 corresponds to having no decimals after the decimal point.
After doing these things I still got a wrong answer. As you can see, this can be very frustrating, getting wrong answers every now and then because of technicality in the C language.
The way I got input was something like this:
fgets(line, 100, stdin);
sscanf(line, "%lf", &n);
fgets(line, 100, stdin);
sscanf(line, "%lf, &p);
I also checked if fgets returned true whenever I used it. Unfortunately again, I got wrong answers. Very frustrating problem.
So, again after consulting the forums, they recommended I use while (scanf("%lf %lf", &n, &p)==2). So, I used this syntax and it worked and I finally got the accepted AC response.
I think, however, that this is unfair because the problem specs mentions that each integer input will be on a line of its own. This means that for every line input, there will only be one integer. Using scanf("%lf %lf, &n, &p), however, means that a line input can have two integers already which is a contradiction from the specs. This is why I feel the problem is ugly and very frustrating because it deals with technicality instead of logic.
#include "stdio.h"
#include "cmath"
int main() {
char line[100];
double n, p, k;
while (scanf("%lf %lf", &n, &p) == 2) {
k = pow(p, 1.0/n);
printf("%.0lf\n", k);
}
return 0;
}
I looked at the discussions in the Internet and discovered that you could actually just use double type, which is kind of smart. double type can handle numbers as large as 10^300. float type however cannot do because float I think can only handle up to 10^38.
Using double gives us a whole range of mathematical powers. We can use the cmath library to raise the number p to the fraction (1/n) to get the nth root of p.
I read the forums and they said that the correct way to read a double using scanf is to use %lf. In printing the double, I initially used %d and casting the double to an integer. Unfortunately, this did not work and I got wrong answers. probably because the specs mentions that k should be able to handle up to 10^9, while %d which corresponds to an integer can only handle up to 2^31.
Again I consulted the forums and they told me to use %.0lf in printf. The .0 corresponds to having no decimals after the decimal point.
After doing these things I still got a wrong answer. As you can see, this can be very frustrating, getting wrong answers every now and then because of technicality in the C language.
The way I got input was something like this:
fgets(line, 100, stdin);
sscanf(line, "%lf", &n);
fgets(line, 100, stdin);
sscanf(line, "%lf, &p);
I also checked if fgets returned true whenever I used it. Unfortunately again, I got wrong answers. Very frustrating problem.
So, again after consulting the forums, they recommended I use while (scanf("%lf %lf", &n, &p)==2). So, I used this syntax and it worked and I finally got the accepted AC response.
I think, however, that this is unfair because the problem specs mentions that each integer input will be on a line of its own. This means that for every line input, there will only be one integer. Using scanf("%lf %lf, &n, &p), however, means that a line input can have two integers already which is a contradiction from the specs. This is why I feel the problem is ugly and very frustrating because it deals with technicality instead of logic.
#include "stdio.h"
#include "cmath"
int main() {
char line[100];
double n, p, k;
while (scanf("%lf %lf", &n, &p) == 2) {
k = pow(p, 1.0/n);
printf("%.0lf\n", k);
}
return 0;
}
Friday, January 23, 2015
10370: Above average
For this problem, the problem seems to be parsing, because the inputs can have newlines inserted randomly between them. so what i did was to just keep parsing out numbers from the input regardless if the number comes after a space or a newline. just keep parsing numbers.
for every number parsed, check the status of the program. a status of 0 means that it is the program start, and so the number just parsed corresponds to the number of cases to be processed. if the status is 1, it means that we already know the number of cases. therefore the number just parsed corresponds to the number of students in a particular test case. a status of 2 means that we are currently extracting the grades of the students in a particular case. a status of 3 means that all cases have been processed and that the program should exit.
if in status 2, the number of student grades extracted becomes equal to the number of students in a particular test case, then we get the average grade of all students in the test case. then we count the number of students whose grade is above the average. then we divide the number of students with above average grade by the total number of students in the particular test case.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[10000];
char *pch;
int num_cases, num_students;
int students_processed, cases_processed;
int grades[10000];
int x, i, num_above;
float ave;
float above_percentage;
// 0 start
// 1 obtained num_cases
// 2 obtained num_students
// 3 all cases processed
int status = 0;
cases_processed = 0;
while (1) {
gets(line);
pch = strtok(line, " \t\n");
while (pch) {
x = atoi(pch);
if (status == 0) {
num_cases = x;
status += 1;
}
else if (status == 1) {
num_students = x;
students_processed = 0;
status += 1;
}
else if (status == 2) {
grades[students_processed] = x;
students_processed += 1;
if(students_processed == num_students) {
cases_processed += 1;
ave = 0;
for (i = 0; i < num_students; i += 1) {
ave += grades[i];
}
ave /= num_students;
for (i = 0, num_above = 0; i < num_students; i += 1) {
if (float(grades[i]) > ave) {
num_above += 1;
}
}
above_percentage = float(num_above) / float(num_students) * 100;
printf("%.3f%\n", above_percentage);
if (cases_processed == num_cases) {
status = 3;
break;
}
status = 1;
}
}
pch = strtok(NULL, " \t\n");
}
if (status == 3) {
break;
}
}
return 0;
}
for every number parsed, check the status of the program. a status of 0 means that it is the program start, and so the number just parsed corresponds to the number of cases to be processed. if the status is 1, it means that we already know the number of cases. therefore the number just parsed corresponds to the number of students in a particular test case. a status of 2 means that we are currently extracting the grades of the students in a particular case. a status of 3 means that all cases have been processed and that the program should exit.
if in status 2, the number of student grades extracted becomes equal to the number of students in a particular test case, then we get the average grade of all students in the test case. then we count the number of students whose grade is above the average. then we divide the number of students with above average grade by the total number of students in the particular test case.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[10000];
char *pch;
int num_cases, num_students;
int students_processed, cases_processed;
int grades[10000];
int x, i, num_above;
float ave;
float above_percentage;
// 0 start
// 1 obtained num_cases
// 2 obtained num_students
// 3 all cases processed
int status = 0;
cases_processed = 0;
while (1) {
gets(line);
pch = strtok(line, " \t\n");
while (pch) {
x = atoi(pch);
if (status == 0) {
num_cases = x;
status += 1;
}
else if (status == 1) {
num_students = x;
students_processed = 0;
status += 1;
}
else if (status == 2) {
grades[students_processed] = x;
students_processed += 1;
if(students_processed == num_students) {
cases_processed += 1;
ave = 0;
for (i = 0; i < num_students; i += 1) {
ave += grades[i];
}
ave /= num_students;
for (i = 0, num_above = 0; i < num_students; i += 1) {
if (float(grades[i]) > ave) {
num_above += 1;
}
}
above_percentage = float(num_above) / float(num_students) * 100;
printf("%.3f%\n", above_percentage);
if (cases_processed == num_cases) {
status = 3;
break;
}
status = 1;
}
}
pch = strtok(NULL, " \t\n");
}
if (status == 3) {
break;
}
}
return 0;
}
10189: Minesweeper
It has been more than 5 years I guess since I last tried this problem. Last time I tried it, i always got a wrong answer. This time I tried it again after several years. as a first try, i got a wrong answer again. I then read the forums and learned that there should be no extra blank line after the last line of output. the extra blank line should only be placed between cases.
The algorithm I used was first to create an initialized array. For a 3x5 array, it would look something like this:
-------
-uuuuu-
-uuuuu-
-uuuuu-
-------
the u's above represent uninitialized data table. they can be random initially. but notice that after initialization, you have dash characters surrounding the data table.
we then read the input into the array:
-------
-**...-
-.....-
-.*...-
-------
we then process each element in the data table one element at a time.
First we process the first element. for each element, we consider the 3x3 matrix surrounding the element under consideration:
-------
-**...-
-.....-
-.*...-
-------
for this 3x3 matrix, we count the number of asterisk characters which represent bombs.
Then we consider the next element and its corresponding 3x3 matrix:
-------
-**...-
-.....-
-.*...-
-------
again we count the number of bombs for this 3x3 matrix.
we do this process again and again until we process the last element in the data table:
-------
-**...-
-.....-
-.*...-
-------
In processing the cases, just be careful that you do not print an extra line after the last case. One way to do this is to get dimensions from the user first. Then enter the while-loop. In the while loop, process the data, then get the dimensions from the user. if the dimensions are not both zero, then print an extra line before looping back to the start of the while-loop.
One thing I did was not to use the gets() function anymore to get lines from the user input. I installed ubuntu 14.01 onto my netpad and when I compiled the code using g++, I get a warning message saying that the use of gets() is unsafe. Therefore, I have returned to my usual way of getting input from the user: using the fgets() function.
1 #include "stdio.h"
2 int main() {
3 int n, m;
4 int i, j;
5 int p, q;
6 int count, field;
7 char arr[150][150];
8 char line[150];
9 for (i = 0; i < 150; i += 1) {
10 arr[i][0] = '-';
11 arr[0][i] = '-';
12 }
13 fgets(line, 150, stdin);
14 sscanf(line, "%d %d\n", &n, &m);
15 if (n == 0 && m == 0) {
16 return 0;
17 }
18 for(field = 1; 1; field += 1) {
19 for (i = n + 1, j = 1; j <= m + 1; j += 1) {
20 arr[i][j] = '-';
21 }
22 for (i = 1, j = m + 1; i <= n + 1; i += 1) {
23 arr[i][j] = '-';
24 }
25 for (i = 1; i <= n; i += 1) {
26 fgets(line, 150, stdin);
27 for (j = 0; j < m; j += 1) {
28 arr[i][j+1] = line[j];
29 }
30 }
31 // for (i = 0; i <= n + 1; i += 1) {
32 // for (j = 0; j <= m + 1; j += 1) {
33 // printf("%c", arr[i][j]);
34 // }
35 // printf("\n");
36 // }
37 // printf("\n");
38 printf("Field #%d:\n", field);
39 for (i = 1; i <= n; i += 1) {
40 for (j = 1; j <= m; j += 1) {
41 if (arr[i][j] == '*') {
42 printf("%c", '*');
43 }
44 else {
45 count = 0;
46 for (p = i - 1; p <= i + 1; p += 1) {
47 for (q = j - 1; q <= j + 1; q += 1) {
48 if (arr[p][q] == '*') {
49 count += 1;
50 }
51 }
52 }
53 printf("%d", count);
54 }
55 }
56 printf("\n");
57 }
58 fgets(line, 150, stdin);
59 sscanf(line, "%d %d\n", &n, &m);
60 if (n == 0 && m == 0) {
61 break;
62 }
63 printf("\n");
64 }
65 return 0;
66 }
The algorithm I used was first to create an initialized array. For a 3x5 array, it would look something like this:
-------
-uuuuu-
-uuuuu-
-uuuuu-
-------
the u's above represent uninitialized data table. they can be random initially. but notice that after initialization, you have dash characters surrounding the data table.
we then read the input into the array:
-------
-**...-
-.....-
-.*...-
-------
we then process each element in the data table one element at a time.
First we process the first element. for each element, we consider the 3x3 matrix surrounding the element under consideration:
-------
-**...-
-.....-
-.*...-
-------
for this 3x3 matrix, we count the number of asterisk characters which represent bombs.
Then we consider the next element and its corresponding 3x3 matrix:
-------
-**...-
-.....-
-.*...-
-------
again we count the number of bombs for this 3x3 matrix.
we do this process again and again until we process the last element in the data table:
-------
-**...-
-.....-
-.*...-
-------
In processing the cases, just be careful that you do not print an extra line after the last case. One way to do this is to get dimensions from the user first. Then enter the while-loop. In the while loop, process the data, then get the dimensions from the user. if the dimensions are not both zero, then print an extra line before looping back to the start of the while-loop.
One thing I did was not to use the gets() function anymore to get lines from the user input. I installed ubuntu 14.01 onto my netpad and when I compiled the code using g++, I get a warning message saying that the use of gets() is unsafe. Therefore, I have returned to my usual way of getting input from the user: using the fgets() function.
1 #include "stdio.h"
2 int main() {
3 int n, m;
4 int i, j;
5 int p, q;
6 int count, field;
7 char arr[150][150];
8 char line[150];
9 for (i = 0; i < 150; i += 1) {
10 arr[i][0] = '-';
11 arr[0][i] = '-';
12 }
13 fgets(line, 150, stdin);
14 sscanf(line, "%d %d\n", &n, &m);
15 if (n == 0 && m == 0) {
16 return 0;
17 }
18 for(field = 1; 1; field += 1) {
19 for (i = n + 1, j = 1; j <= m + 1; j += 1) {
20 arr[i][j] = '-';
21 }
22 for (i = 1, j = m + 1; i <= n + 1; i += 1) {
23 arr[i][j] = '-';
24 }
25 for (i = 1; i <= n; i += 1) {
26 fgets(line, 150, stdin);
27 for (j = 0; j < m; j += 1) {
28 arr[i][j+1] = line[j];
29 }
30 }
31 // for (i = 0; i <= n + 1; i += 1) {
32 // for (j = 0; j <= m + 1; j += 1) {
33 // printf("%c", arr[i][j]);
34 // }
35 // printf("\n");
36 // }
37 // printf("\n");
38 printf("Field #%d:\n", field);
39 for (i = 1; i <= n; i += 1) {
40 for (j = 1; j <= m; j += 1) {
41 if (arr[i][j] == '*') {
42 printf("%c", '*');
43 }
44 else {
45 count = 0;
46 for (p = i - 1; p <= i + 1; p += 1) {
47 for (q = j - 1; q <= j + 1; q += 1) {
48 if (arr[p][q] == '*') {
49 count += 1;
50 }
51 }
52 }
53 printf("%d", count);
54 }
55 }
56 printf("\n");
57 }
58 fgets(line, 150, stdin);
59 sscanf(line, "%d %d\n", &n, &m);
60 if (n == 0 && m == 0) {
61 break;
62 }
63 printf("\n");
64 }
65 return 0;
66 }
Subscribe to:
Posts (Atom)