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 }
Sunday, December 28, 2014
591: box of bricks
This problem is pretty straightforward except for one very bad trick. The problem requires outputting a blank line for every set processed. I got caught here and got a wrong answer in my first try.
The algorithm first calculates the total number of bricks and divides the sum by the number of stacks. the resulting number is the number of bricks for each stack so that all stacks have the same height. i call this height the fair height which is the height whereby all stacks should be equal to.
the algorithm then goes through each stack. if the height of a stack is greater than the fair height, then get the difference. sum all the differences for all stacks taller than the fair height. this sum of differences would then be equal to the minimum number of brick moves.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[1000];
char *pch;
int n, i, fair, x, moves, k;
int h[1000];
for (k = 1; 1; k += 1) {
gets(line);
sscanf(line, "%d", &n);
if(!n)
break;
gets(line);
pch = strtok(line, " \t\n");
i = 0;
while (pch) {
h[i] = atoi(pch);
pch = strtok(NULL, " \t\n");
i += 1;
}
fair = 0;
for (i = 0; i < n; i += 1) {
fair += h[i];
}
fair /= n;
moves = 0;
for (i = 0; i < n; i += 1) {
x = h[i];
if (x > fair) {
moves += (x - fair);
}
}
printf("Set #%d\n", k);
printf("The minimum number of moves is %d.\n\n", moves);
}
return 0;
}
The algorithm first calculates the total number of bricks and divides the sum by the number of stacks. the resulting number is the number of bricks for each stack so that all stacks have the same height. i call this height the fair height which is the height whereby all stacks should be equal to.
the algorithm then goes through each stack. if the height of a stack is greater than the fair height, then get the difference. sum all the differences for all stacks taller than the fair height. this sum of differences would then be equal to the minimum number of brick moves.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[1000];
char *pch;
int n, i, fair, x, moves, k;
int h[1000];
for (k = 1; 1; k += 1) {
gets(line);
sscanf(line, "%d", &n);
if(!n)
break;
gets(line);
pch = strtok(line, " \t\n");
i = 0;
while (pch) {
h[i] = atoi(pch);
pch = strtok(NULL, " \t\n");
i += 1;
}
fair = 0;
for (i = 0; i < n; i += 1) {
fair += h[i];
}
fair /= n;
moves = 0;
for (i = 0; i < n; i += 1) {
x = h[i];
if (x > fair) {
moves += (x - fair);
}
}
printf("Set #%d\n", k);
printf("The minimum number of moves is %d.\n\n", moves);
}
return 0;
}
Wednesday, December 10, 2014
136: ugly numbers
This is a brute force approach. If the current number is divisible by 2, 3 or 5, then divide it by the number it is divisible by. Keep dividing until you reach 1 as long as it is divisible by 2, 3 or 5. If the current dividend is not yet 1, and it is not divisible by 2, 3 or 5, then it means that your current number is not an ugly number. This approach took 26 seconds on an i5 machine. uVA problem specs requires at most 3 seconds. Other blogs discuss using dynamic programming.
#include "stdio.h"
int main() {
int i, x, r, is_ugly, count;
count = 0;
for(i = 1; 1; i += 1) {
x = i;
is_ugly = 1;
while (x > 1) {
r = x % 2;
if (r) {
r = x % 3;
if (r) {
r = x % 5;
if (r) {
is_ugly = 0;
break;
}
else {
x /= 5;
}
}
else {
x /= 3;
}
}
else {
x /= 2;
}
}
if (is_ugly) {
count += 1;
//printf("%d ", i);
if (count >= 1500) {
break;
}
}
}
printf("The 1500'th ugly number is %d.\n", i);
return 0;
}
#include "stdio.h"
int main() {
int i, x, r, is_ugly, count;
count = 0;
for(i = 1; 1; i += 1) {
x = i;
is_ugly = 1;
while (x > 1) {
r = x % 2;
if (r) {
r = x % 3;
if (r) {
r = x % 5;
if (r) {
is_ugly = 0;
break;
}
else {
x /= 5;
}
}
else {
x /= 3;
}
}
else {
x /= 2;
}
}
if (is_ugly) {
count += 1;
//printf("%d ", i);
if (count >= 1500) {
break;
}
}
}
printf("The 1500'th ugly number is %d.\n", i);
return 0;
}
10082: WERTYU
For this problem, I created a character array, containing the keyboard characters in their original sequence. To translate a letter, i searched for the letter in the array and printed the letter that is one index before the index where the letter is located in. I had to detect spaces in the input as well. If the current letter is a space, print a space in the output as well.
#include "stdio.h"
int main() {
char line[1000];
int i, j;
char orig[] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
while(gets(line)) {
for(i = 0; line[i]; i += 1) {
if(line[i] == ' ') {
printf(" ");
continue;
}
for(j = 0; orig[j]; j += 1) {
if(line[i] == orig[j]) {
printf("%c", orig[j-1]);
break;
}
}
}
printf("\n");
}
return 0;
}
#include "stdio.h"
int main() {
char line[1000];
int i, j;
char orig[] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
while(gets(line)) {
for(i = 0; line[i]; i += 1) {
if(line[i] == ' ') {
printf(" ");
continue;
}
for(j = 0; orig[j]; j += 1) {
if(line[i] == orig[j]) {
printf("%c", orig[j-1]);
break;
}
}
}
printf("\n");
}
return 0;
}
Friday, October 17, 2014
10018 - Reverse and Add
This problem is pretty straight forward except for one thing. The unsigned int restriction. The problem says that the palindrome cannot be greater than 2^32 = 4,294,967,295, but somehow, just using unsigned int does not work. Unsigned int is 32-bit, and when I use this, I get wrong answer. When I tried using unsigned long long int which is equivalent to 64-bit, the code got accepted.
To read or write an unsigned long long int, I used %llu instead of the usual %d in printf() or scanf().
To get the digits of an integer, I get the remainder when the number is divided by 10. Get the remainder when the quotient is divided by 10 again. Repeat and repeat until the quotient equals 0. The series of remainders obtained correspond to the digits of the integer.
Here's an implementation that got accepted:
#include "stdio.h"
int main() {
char line[100];
unsigned long long int num, q, r, l, mid, ispal, rnum, pow, sum;
int i, j, k, num_input, count;
unsigned int array[100];
scanf("%d", &num_input);
for (k = 0; k < num_input; k += 1) {
scanf("%llu", &num);
q = num;
l = 0;
while (q > 0) {
r = q % 10;
q /= 10;
array[l] = r;
l += 1;
}
sum = num;
count = 0;
do {
count += 1;
rnum = 0;
pow = 1;
for (i = l - 1; i >= 0; i -= 1) {
rnum = rnum + (array[i] * pow);
pow = pow * 10;
}
sum = sum + rnum;
// printf("sum=%d\n", sum);
q = sum;
l = 0;
while (q > 0) {
r = q % 10;
q /= 10;
array[l] = r;
l += 1;
}
mid = l / 2;
ispal = 1;
for (i = 0, j = l - 1; i < mid; i += 1, j -= 1) {
if (array[i] != array[j]) {
ispal = 0;
break;
}
}
} while (ispal == 0);
printf("%d %llu\n", count, sum);
}
return 0;
}
To read or write an unsigned long long int, I used %llu instead of the usual %d in printf() or scanf().
To get the digits of an integer, I get the remainder when the number is divided by 10. Get the remainder when the quotient is divided by 10 again. Repeat and repeat until the quotient equals 0. The series of remainders obtained correspond to the digits of the integer.
Here's an implementation that got accepted:
#include "stdio.h"
int main() {
char line[100];
unsigned long long int num, q, r, l, mid, ispal, rnum, pow, sum;
int i, j, k, num_input, count;
unsigned int array[100];
scanf("%d", &num_input);
for (k = 0; k < num_input; k += 1) {
scanf("%llu", &num);
q = num;
l = 0;
while (q > 0) {
r = q % 10;
q /= 10;
array[l] = r;
l += 1;
}
sum = num;
count = 0;
do {
count += 1;
rnum = 0;
pow = 1;
for (i = l - 1; i >= 0; i -= 1) {
rnum = rnum + (array[i] * pow);
pow = pow * 10;
}
sum = sum + rnum;
// printf("sum=%d\n", sum);
q = sum;
l = 0;
while (q > 0) {
r = q % 10;
q /= 10;
array[l] = r;
l += 1;
}
mid = l / 2;
ispal = 1;
for (i = 0, j = l - 1; i < mid; i += 1, j -= 1) {
if (array[i] != array[j]) {
ispal = 0;
break;
}
}
} while (ispal == 0);
printf("%d %llu\n", count, sum);
}
return 0;
}
Tuesday, October 14, 2014
299 - Train Swapping
I think this problem is an implementation of the insertion sort algorithm (http://en.wikipedia.org/wiki/Insertion_sort). Given a sequence 4 3 2 1, you can perform swaps on the numbers as follows:
4 3 2 1
3 4 2 1
3 2 4 1
2 3 4 1
2 3 1 4
2 1 3 4
1 2 3 4
4 3 2 1
3 4 2 1
3 2 4 1
2 3 4 1
2 3 1 4
2 1 3 4
1 2 3 4
This gives a total of 6 swaps. Here's another sequence and the sequence of swaps performed to sort the numbers:
4 3 5 1 2
3 4 5 1 2
3 4 1 5 2
3 1 4 5 2
1 3 4 5 2
1 3 4 2 5
1 3 2 4 5
1 2 3 4 5
This gives a total of 7 swaps.
So, one can simply implement the sequence of swaps and count the swaps.
Here's the code. By the way, I used scanf("%d\n", &n) in this code. I noticed that if I don't put \n in the scanf() function, the code does not accept input properly. The scanf() has to be used with the \n character.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[1000];
int n, i, l, j, k, p, swaps, temp;
int c[100];
char *pch;
scanf("%d\n", &n);
for (i = 0; i < n; i += 1) {
scanf("%d\n", &l);
gets(line);
pch = strtok(line, " \t\n");
for (j = 0; j < l; j += 1) {
c[j] = atoi(pch);
pch = strtok(NULL, " \t\n");
}
for (k = 1, swaps = 0; k < l; k += 1) {
for (p = k - 1; p >= 0; p--) {
if (c[p] < c[p+1]) {
break;
}
temp = c[p];
c[p] = c[p+1];
c[p+1] = temp;
swaps += 1;
}
}
// printf("B");
// for (j = 0; j < l; j += 1) {
// printf("%d ", c[j]);
// }
// printf("E\n");
printf("Optimal train swapping takes %d swaps.\n", swaps);
}
return 0;
}
Monday, October 13, 2014
10035 - Primary Arithmetic
I get a wrong answer here. and then when i reviewed my code, i realized the error.
what i did was to extract each digit one by one from each number. to extract the first digit, get the remainder by dividing the number by 10. the remainder is the first digit. to extract the second digit, divide the quotient from the first division by 10. the remainder is the second digit. to obtain the third digit, divide quotient from the second division by 10. the remainder is the third digit, etc., etc. until you reach the 9th digit.
sum the first digit from the first number with the first digit from the second number. if the sum is greater than 9, then there is a carry of 1 in the next operation. sum the second digit from the first number and the second digit from the second number and the carry from the first operation. if the sum of the second digits with the carry is greater than 9, then there is a carry in the next operation. sum the third digit from the first number and the third digit from the second number and the carry from the previous operation. if the sum is greater than 9, then there is a carry in the next operation. Repeat the cycle until you reach the 9th digits. During the process, count the number of carries.
The error i had was I forgot to reset the carry when the sum was less than or equal to 9. This led to a wrong answer which was made me upset and depressed. After a few minutes, i reviewed my code and realized the resetting error. Overconfidence kills.
#include "stdio.h"
int main() {
unsigned int x, y, i, rx, ry, num_carry, sum;
bool carry;
while (1) {
scanf("%d %d", &x, &y);
if (x == 0 && y == 0) {
break;
}
carry = 0;
num_carry = 0;
for (i = 0; i < 9; i += 1) {
rx = x % 10;
x = x / 10;
ry = y % 10;
y = y / 10;
sum = rx + ry + carry;
if (sum > 9) {
carry = 1;
num_carry += 1;
}
else {
carry = 0;
}
}
if (num_carry > 1) {
printf("%d carry operations.\n", num_carry);
}
else if (num_carry == 1) {
printf("1 carry operation.\n");
}
else {
printf("No carry operation.\n");
}
}
return 0;
}
what i did was to extract each digit one by one from each number. to extract the first digit, get the remainder by dividing the number by 10. the remainder is the first digit. to extract the second digit, divide the quotient from the first division by 10. the remainder is the second digit. to obtain the third digit, divide quotient from the second division by 10. the remainder is the third digit, etc., etc. until you reach the 9th digit.
sum the first digit from the first number with the first digit from the second number. if the sum is greater than 9, then there is a carry of 1 in the next operation. sum the second digit from the first number and the second digit from the second number and the carry from the first operation. if the sum of the second digits with the carry is greater than 9, then there is a carry in the next operation. sum the third digit from the first number and the third digit from the second number and the carry from the previous operation. if the sum is greater than 9, then there is a carry in the next operation. Repeat the cycle until you reach the 9th digits. During the process, count the number of carries.
The error i had was I forgot to reset the carry when the sum was less than or equal to 9. This led to a wrong answer which was made me upset and depressed. After a few minutes, i reviewed my code and realized the resetting error. Overconfidence kills.
#include "stdio.h"
int main() {
unsigned int x, y, i, rx, ry, num_carry, sum;
bool carry;
while (1) {
scanf("%d %d", &x, &y);
if (x == 0 && y == 0) {
break;
}
carry = 0;
num_carry = 0;
for (i = 0; i < 9; i += 1) {
rx = x % 10;
x = x / 10;
ry = y % 10;
y = y / 10;
sum = rx + ry + carry;
if (sum > 9) {
carry = 1;
num_carry += 1;
}
else {
carry = 0;
}
}
if (num_carry > 1) {
printf("%d carry operations.\n", num_carry);
}
else if (num_carry == 1) {
printf("1 carry operation.\n");
}
else {
printf("No carry operation.\n");
}
}
return 0;
}
11172 - Relational Operator
This is probably the easiest problem I ever solved in UVA.
I thought that there must be some kind of trick here. Some technicality that would make the problem extra tricky and deceiving. But it looks like there's no trick or deception here. It looks like just a really easy problem.
I also discovered that gets() can be used for these types of problems, instead of my usual fgets() style.
Here's the code:
#include "stdio.h"
int main() {
char line[100];
int n, i, a, b;
gets(line);
sscanf(line, "%d", &n);
for (i = 0; i < n; i += 1) {
gets(line);
sscanf(line, "%d %d", &a, &b);
// printf("A=%d, B=%d\n", a, b);
if (a < b) {
printf("<\n");
}
else if (a > b) {
printf(">\n");
}
else {
printf("=\n");
}
}
}
I thought that there must be some kind of trick here. Some technicality that would make the problem extra tricky and deceiving. But it looks like there's no trick or deception here. It looks like just a really easy problem.
I also discovered that gets() can be used for these types of problems, instead of my usual fgets() style.
Here's the code:
#include "stdio.h"
int main() {
char line[100];
int n, i, a, b;
gets(line);
sscanf(line, "%d", &n);
for (i = 0; i < n; i += 1) {
gets(line);
sscanf(line, "%d %d", &a, &b);
// printf("A=%d, B=%d\n", a, b);
if (a < b) {
printf("<\n");
}
else if (a > b) {
printf(">\n");
}
else {
printf("=\n");
}
}
}
Sunday, October 12, 2014
10038 - Jolly Jumpers
This is another crazy problem.
It's supposed to be straight forward, but I kept getting run time errors.
My algorithm was to create a list of checks. Whenever a difference was calculated, the checks array element with index equal to the difference was set to 1. Then once all the differences were calculated, and all the checks were marked, I verified if all check elements with indices from 1 up to n-1 were marked with 1. If all were marked with 1, then the sequence is jolly.
I thought the run time error was because I was marking a checks element that is out of bounds. So I tried increasing my checks array from 3000 to 4000. But still the run time error existed. Then I realized that if the private key was n = 3000, then the input line would be more than 3000 characters long. This meant that my usual way of getting the line from the input would not longer work.
Usually, I use this code to get input from the user:
fgets(line, 100, stdin)
But since the input line can be more than 3000 characters long, I changed the code to:
fgets(line, 1000000, stdin)
When I did this, the run time error disappeared.
Here's the code:
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[1000000];
int n, i, x, j, diff, is_jolly;
int arr[4000];
int checks[4000];
char *pch;
while (fgets(line, 1000000, stdin)) {
pch = strtok(line, " \t\n");
n = atoi(pch);
if (n == 1) {
printf("Jolly\n");
continue;
}
for (i = 0; i < n; i += 1) {
pch = strtok(NULL, " \t\n");
x = atoi(pch);
arr[i] = x;
}
// printf("arr: ");
// for (i = 0; i < n; i += 1) {
// printf("%d ", arr[i]);
// }
// printf("\n");
j = n - 1;
for (i = 1; i <= j; i += 1) {
checks[i] = 0;
}
// printf("checks: ");
// for (i = 1; i <= j; i += 1) {
// printf("%d ", checks[i]);
// }
// printf("\n");
for (i = 1; i <= j; i += 1) {
diff = arr[i] - arr[i - 1];
if (diff < 0) {
diff = -1 * diff;
}
// printf("diff = %d\n", diff);
if (diff <= 3000) {
checks[diff] = 1;
}
}
// printf("diff: ");
// for (i = 1; i <= j; i += 1) {
// printf("%d ", checks[i]);
// }
// printf("\n");
is_jolly = 1;
for (i = 1; i <= j; i += 1) {
if (checks[i] != 1) {
is_jolly = 0;
break;
}
}
if (is_jolly) {
printf("Jolly\n");
}
else {
printf("Not jolly\n");
}
}
}
It's supposed to be straight forward, but I kept getting run time errors.
My algorithm was to create a list of checks. Whenever a difference was calculated, the checks array element with index equal to the difference was set to 1. Then once all the differences were calculated, and all the checks were marked, I verified if all check elements with indices from 1 up to n-1 were marked with 1. If all were marked with 1, then the sequence is jolly.
I thought the run time error was because I was marking a checks element that is out of bounds. So I tried increasing my checks array from 3000 to 4000. But still the run time error existed. Then I realized that if the private key was n = 3000, then the input line would be more than 3000 characters long. This meant that my usual way of getting the line from the input would not longer work.
Usually, I use this code to get input from the user:
fgets(line, 100, stdin)
But since the input line can be more than 3000 characters long, I changed the code to:
fgets(line, 1000000, stdin)
When I did this, the run time error disappeared.
Here's the code:
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int main() {
char line[1000000];
int n, i, x, j, diff, is_jolly;
int arr[4000];
int checks[4000];
char *pch;
while (fgets(line, 1000000, stdin)) {
pch = strtok(line, " \t\n");
n = atoi(pch);
if (n == 1) {
printf("Jolly\n");
continue;
}
for (i = 0; i < n; i += 1) {
pch = strtok(NULL, " \t\n");
x = atoi(pch);
arr[i] = x;
}
// printf("arr: ");
// for (i = 0; i < n; i += 1) {
// printf("%d ", arr[i]);
// }
// printf("\n");
j = n - 1;
for (i = 1; i <= j; i += 1) {
checks[i] = 0;
}
// printf("checks: ");
// for (i = 1; i <= j; i += 1) {
// printf("%d ", checks[i]);
// }
// printf("\n");
for (i = 1; i <= j; i += 1) {
diff = arr[i] - arr[i - 1];
if (diff < 0) {
diff = -1 * diff;
}
// printf("diff = %d\n", diff);
if (diff <= 3000) {
checks[diff] = 1;
}
}
// printf("diff: ");
// for (i = 1; i <= j; i += 1) {
// printf("%d ", checks[i]);
// }
// printf("\n");
is_jolly = 1;
for (i = 1; i <= j; i += 1) {
if (checks[i] != 1) {
is_jolly = 0;
break;
}
}
if (is_jolly) {
printf("Jolly\n");
}
else {
printf("Not jolly\n");
}
}
}
Subscribe to:
Posts (Atom)