Tuesday, August 14, 2012

284: Logic

I was hesitant to take on this problem because of its rather low success rate. Out of about 240 submissions, only 23% were accepted. Moreover, only about 80 users have tried it; the more popular problems have over a thousand users. I read the problem and indeed it was quite intimidating. Nonetheless, I tried to think about a solution for the problem. I went to the barber, and while having my hair cut, I was thinking about a plausible algorithm. I was able to come up with a rough sketch of an algorithm, but I spent a little more time to think more about it. About 24 hours later, I tried writing the algorithm into code. When I finished writing and testing the code, I submitted the code into the UVA online judge, and luckily, the code got accepted with a run time of 8 ms, which is well within the time limit of 3 seconds.

Below is the sample code. The code uses several global variables for the reason that I created a debug function, print_array(), to aid me in checking the code prior to submission, to see whether the code actually does what it is intended to do. Instead of passing the arrays as arguments to the print_arrays() function, I thought it would be easier to use global variables. Using global variables is not good programming practice. However, since we are after performance and not beauty or maintainability, I thought it would be all write to deviate from good programming habits.

First, I explain the data structures used. Several array variables are utilized. In the real world, one would not do this to implement the algorithm to this problem. In the real world, one would probably use object-oriented programming and classes to implement the algorithm. However, once again, as the emphasis of UVA problems is speed rather than beauty, I resorted to this rather ugly but probably faster code implementation.

The problem specifies a 10x10 grid array where each element or node in the grid corresponds to an input node, output node, NOT gate, AND gate, or OR gate. We could have used a two-dimensional array to implement the code; however, it would probably easier to reduce and think of the problem in terms of only one dimension to simplify things. After all, every node in the 10x10 grid two-dimensional array would correspond to a unique element in a 100-element one-dimensional array. For instance the node [9][8] in the 2D array would correspond to node [98] in the 1D array, and node [0][0] in the 2D array would correspond to node [0] in the 1D array.

In object-oriented programming, a node would correspond to a class with several variables in it. The class would have a variable corresponding to the symbol of the node, which can be i, o, &, | or !, depending whether the node is an input, output, AND, OR or NOT gate. In addition, the class would have a variable corresponding to the x-coordinate of the node, and another variable corresponding to the y-coordinate of the node. Moreover, the class would have one or two inputs depending on what type of gate it is. If the node is an input, output or NOT gate, then the node would only have one input. If the node, however, were an AND gate or an OR gate, then it would require two input variables. Finally, the class would need an output variable to store the output of a gate.

The gates referred to in this problem are digital electronic gates which are very common in electronics. They are often called logic gates and are implemented using transistors. These gates can be very tiny and are almost always present inside most electronic devices such as laptops, televisions and cellphones. You may read more about logic gates in the wikipedia. I guess the most important aspect of a gate is the truth table which is a table which lists down all possible input combinations and the corresponding output values.

In the code below, no classes are used and we did not use a linked-list of class nodes or a similar data structure to store the nodes. Instead, the maximum number of nodes are pre-allocated. The maximum number of nodes is 100 since a 10x10 grid would have 100 nodes. One would think that this is a waste of memory resources since we are pre-allocating 100 nodes immediately when in fact maybe just a few nodes are needed. This argument is true; however, remember that we are after speed and not beauty or maintainability. Since 100 is not that large a number, pre-allocating them immediately may be faster than using some other complex data structure that allocates the exact number of nodes needed. Using a complex data structure may be more efficient in using memory resources; however, the added complexity will inevitably slow things down.

 Though no classes are actually used, the concept of classes is somewhat indirectly embedded within the code. Each node is represented by an index alignment of several array variables. For instance, the node with an x-coordinate of 9 and a y-coordinate of 8 is represented by the elements with index 98 of the arrays arr_v, arr_s, arr_a and arr_c. Array arr_s is for storing the symbol and elements in it can have values of i, o, &, | or !. Array arr_v is for storing the calculated output of the nodes. If for example, node 98 is an AND gate, then arr_v[98] would correspond to the output of an AND gate.

Array arr_a stores the input arguments of the gate in reference form. arr_a is a 2D array and each node can have up to a maximum of two input arguments. If node 98 is an AND gate that takes as its inputs the output of nodes 72 and 25, then arr_a[98][0] and arr_a[98][1] would have the values 72 and 25. It should be noted that the code is written in such a way that arr[98][0] could have a value of 72 and arr[98][1] a value of 25, or vice-versa. The order in which 72 and 25 are stored does not matter. Similarly, a real AND gate will not mind the order in which its inputs are applied. A two-input AND gate can take a 1 in its first input and a 0 in its second input, and output a 0 based on these inputs. If a 0 were input in its first input and a 1 in its second input, the output will still be 0. So, the ordering does not really matter, and we actually use this fact to optimize the code, as will be explained in a while.

The array arr_c is used in relation to arr_a. Each node in arr_a has two elements corresponding to the input arguments of a given gate. For instance, the input arguments to node 98 are placed in the slots, arr_a[98][0] and arr_a[98][1]. arr_c is used to take note of the next slot to store an input argument. Ideally, arr_c should only store 0 or 1 values which would tell us whether to store an input argument into arr_a[98][0] or arr_a[98][1] for the case of gate 98. However, in order to save time, and avoid having to initialize all the elements in arr_c to 0 before testing each test case, we simply use the least significant bit of every element in arr_c.

The least significant bit of any number would be 0 or 1 at any given time. For instance, the number 7 would be presented in binary as 0b0111 and its least significant bit (LSB) would be 1. In this case, if we were to store an input argument for node 98, then we would store it in arr_a[98][1]. We then increment the number 7 by 1 to obtain 8, which in binary is 0b1000. Now, the least significant bit is 0, so storing another input argument to node 98 would be done in arr_a[98][0]. The protocol used in this code is to increment arr_c[98] whenever a new argument is stored in arr_a[98][i], where is either 0 or 1. To obtain the last input argument stored into arr_a[98], we then simply subtract 1 from arr_c[98]. If, for example, arr_c[98] has a value of 8, then to obtain the last input argument stored into arr_a[98], we simply subtract 1 from 8 to obtain 7, and then obtain the least significant bit of 7 which is 1. As 1 is obtained, then the last input argument stored for node 98 is found in arr_a[98][1].

Obtaining the LSB of a number can be done efficiently by bit-wise ANDing the number with 1. For instance to get the LSB of the number 7, we can simply bit-wise AND 7 with 1 to obtain 1. In binary form, this would be represented as:

0d7: 0b0111
0d1: 0b0001
===========
0d1: 0b0001

In bit-wise ANDing, the result will only be 1 if the inputs are both 1. In this case, as the LSB's of both 7 and 1 are both 1, then the result is 1, which is the LSB of 7.

We have explained the arrays, arr_v, arr_a, arr_c. Now, we explain array, arr_r. arr_r lists all the nodes present in a given circuit. In the example given in the problem specification, arr_r would have the values: 0, 2, 11, 21, 13, and 23. These values correspond to the first column of the program inputs:

00i 11 13 ..
02i 11 13 ..
11& 21 ..
21o ..
13| 23 ..
23o ..



arr_i is used to store the nodes that correspond to input gates. In the example of the problem specification, arr_i would contain 0 and 2. Lastly, arr_o is used to store the nodes corresponding to output gates. In the problem example, arr_o would contain gates 21 and 23.

Once all program inputs are encoded into the arrays, the program starts working by first doing some initialization for each test case for a given circuit. Initialization is done by setting all nodes in arr_v that are listed in arr_r to -1 to indicate unknown gate output values (lines 123-125). The following screen output shows the values of the arrays after this initialization of arr_v:

arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v : -1 -1 -1 -1 -1 -1
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00

Notice that arr_i contains the input gates of the circuit, which are 00 and 02. arr_o contains the output gates, 21 and 23. arr_r lists all the gates present in the circuit. For the rest of the arrays, print_arrays() prints the elements with indices sourced from arr_r. For instance, arr_v lists the values of its elements with indices 0, 2, 11, 21, 13, 23. These indices are found in arr_r. arr_s lists the symbols stored in its elements with indices 0, 2, 11, 21, 13, and 23. Using the output of print_arrays(), we can see that node 11 is an AND gate that takes as its inputs the outputs of nodes 00 and 02. Similarly, node 21 is an output gate that takes as its input the output of node 11. For node 21, notice that arr_c[21] has a value of 01. This means that the last input argument for node 21 was stored in arr_a[21][1-1] which is arr_a[21][0]. Remember that arr_c[x] takes note of the next position in arr_a[x][i] to store an input argument for node x in, whether in arr_a[x][0] or in arr_a[x][1].

After initializing arr_v to -1 values to indicate unknown output values, we initialize arr_v with the inputs as specified by the test case (lines 130-132). For the first test case, 00, in the problem specification, the output of print_arrays() will show the following upon input initialization:

arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v :  0  0 -1 -1 -1 -1
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00

Notice that gates 0 and 2 now have output values of 0 and 0.

Next, we iterate through the nodes, attempting to calculate the output values for each of the nodes. If a node in arr_v has a value of -1, then it means that the output value of that node is unknown, and so we try to calculate for it. If can be calculated, then we convert the output value from unknown to the calculated value. If the unknown output value of a given gate cannot be calculated because the output values of another gate to which it is connected to is also unknown, then we simply move on to the next gate. We keep iterating through the nodes until all output values of all gates are no longer unknown; that is arr_v does not contain any -1 values anymore (lines 134-178).

Let us view the output of print_arrays() every time there is an update in one of the values in arr_v:

arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v :  0  0  0 -1 -1 -1
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00
Notice above that the output value of gate 11 changes since now, the output values of gates 0 and 2, which are inputs to gate 11, are now known.
arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v :  0  0  0  0 -1 -1
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00
Since the output of gate 11 is connected to gate 21 which is an output gate, and since gate 11 has value of 0, then gate 21 gains an output value of 0.
arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v :  0  0  0  0  0 -1
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00
Since gate 13 is an OR gate and since its two inputs have values of both 0, then gate 13 obtains an output value of 0. An OR gate will output a 1 if at least one of its inputs is 1. In this case, however, both inputs into the OR gate are 0, so the output is 0.
arr_i : 00 02
arr_o : 21 23
arr_r : 00 02 11 21 13 23
arr_v :  0  0  0  0  0  0
arr_s :  i  i  &  o  |  o
arr_c : 00 00 00 01 00 01
arr_a0: 00 00 00 11 00 13
arr_a1: 00 00 02 00 02 00
Since gate 13 is connected to gate 23, which is an output gate, then gate 23 obtains a value of 0 as well. Once all output values are obtained, we print the output values of the output gates (lines 180-182). Here is the sample code for the algorithm:

001 #include <stdio.h>
002 #include <string.h>
003 #include <stdlib.h>
004 
005 int num_nodes, num_i, num_o;
006 
007 char arr_s[100];
008 
009 int arr_i[100];
010 int arr_o[100];
011 int arr_r[100];
012 int arr_v[100];
013 int arr_a[100][2];
014 int arr_c[100];
015 
016 void print_arrays() {
017   int j, k;
018   
019   printf("arr_i : ");
020   for (j = 0; j < num_i; j += 1) {
021     printf("%02d ", arr_i[j]);      
022   }
023   printf("\n");
024   printf("arr_o : ");
025   for (j = 0; j < num_o; j += 1) {
026     printf("%02d ", arr_o[j]);      
027   }
028   printf("\n");
029   printf("arr_r : ");
030   for (j = 0; j < num_nodes; j += 1) {
031     printf("%02d ", arr_r[j]);      
032   }
033   printf("\n");
034   printf("arr_v : ");
035   for (j = 0; j < num_nodes; j += 1) {
036     k = arr_v[arr_r[j]];
037     printf("%2d ", k);          
038   }
039   printf("\n");
040   printf("arr_s : ");
041   for (j = 0; j < num_nodes; j += 1) {
042     printf(" %c ", arr_s[arr_r[j]]);    
043   }
044   printf("\n");
045   printf("arr_c : ");
046   for (j = 0; j < num_nodes; j += 1) {
047     printf("%02d ", arr_c[arr_r[j]] & 1);    
048   }
049   printf("\n");
050   printf("arr_a0: ");
051   for (j = 0; j < num_nodes; j += 1) {
052     printf("%02d ", arr_a[arr_r[j]][0]);    
053   }
054   printf("\n");
055   printf("arr_a1: ");
056   for (j = 0; j < num_nodes; j += 1) {
057     printf("%02d ", arr_a[arr_r[j]][1]);  
058   }
059   printf("\n\n");
060 }
061 
062 int main() {
063   char line[100], ctmp[100];
064   char *pch;
065   int n, t, node, curr_node, curr_arg, num_unk;
066   int arg_a, arg_b;
067   int i, j, k;
068   char symbol;
069   
070   fgets(line, 100, stdin);
071   sscanf(line, "%d", &n);
072   
073   for (i = 0; i < n; i += 1) {
074     num_nodes = 0;
075     num_i = 0;
076     num_o = 0;
077     
078     while (1) {
079       fgets(line, 100, stdin);
080       pch = strtok(line, " \t");
081       
082       if (pch[0] == 'e') {
083         break;
084       }
085       
086       ctmp[0] = pch[0];
087       ctmp[1] = pch[1];
088       ctmp[2] = 0;
089       curr_node = atoi(ctmp);
090       arr_r[num_nodes] = curr_node;
091       num_nodes += 1;
092       
093       symbol = pch[2];
094       arr_s[curr_node] = symbol;
095       if (symbol == 'i') {
096         arr_i[num_i] = curr_node;
097         num_i += 1;
098       }
099       else if (symbol == 'o') {
100         arr_o[num_o] = curr_node;
101         num_o += 1;
102       }
103                     
104       pch = strtok(NULL, " \t");
105       while (pch != NULL) {
106         if (pch[0] == '.') {
107           break;
108         }
109         
110         node = atoi(pch);
111         curr_arg = arr_c[node] & 1;
112         arr_a[node][curr_arg] = curr_node;
113         arr_c[node] += 1;
114         
115         pch = strtok (NULL, " \t");
116       }
117     }
118     
119     fgets(line, 100, stdin);
120     sscanf(line, "%d", &t);
121     
122     for (j = 0; j < t; j += 1) {
123       for (k = 0; k < num_nodes; k += 1) {
124         arr_v[arr_r[k]] = -1;
125       }
126       
127       fgets(line, 100, stdin);
128       pch = strtok(line, " \t");
129     
130       for (k = 0; k < num_i; k += 1) {
131         arr_v[arr_i[k]] = (pch[k] == 48 ? 0 : 1);
132       }
133       
134       while (1) {
135         num_unk = 0;
136         
137         for (k = 0; k < num_nodes; k += 1) {
138           node = arr_r[k];
139           
140           if (arr_v[node] == -1) {
141             symbol = arr_s[node];
142             
143             arg_a = arr_v[arr_a[node][(arr_c[node] - 1) & 1]];
144             
145             if (arg_a == -1) {
146               num_unk += 1;
147               continue;
148             }
149             
150             if (symbol == '!') {
151               arr_v[node] = (arg_a == 0 ? 1 : 0);
152               continue;
153             }
154             else if (symbol == 'o') {
155               arr_v[node] = arg_a;
156               continue;
157             }
158 
159             arg_b = arr_v[arr_a[node][arr_c[node] & 1]];
160             
161             if (arg_b == -1) {
162               num_unk += 1;
163               continue;
164             }
165             
166             if (symbol == '&') {
167               arr_v[node] = arg_a & arg_b;
168             }
169             else {
170               arr_v[node] = arg_a | arg_b;
171             }            
172           }        
173         }
174         
175         if (num_unk <= 0) {
176           break;
177         }        
178       }
179       
180       for (k = 0; k < num_o; k += 1) {
181         printf("%d", arr_v[arr_o[k]]);
182       }
183       printf("\n");
184     }
185     printf("\n");      
186   }
187       
188   return 0;
189 }

Friday, August 3, 2012

12414: Calculating Yuan Fen

For this UVA problem, I created a Microsoft Excel simulation to find out if there are any patterns I can see. In the file, the two yellow boxes can be changed by the user. The first yellow box can be changed to the desired ST value, while the second yellow box can be edited to the desired test case, which corresponds to the name abbreviations of the couple. For instance, the first yellow box can be changed to 2277, and the second yellow box can be changed to QWERTY. By doing so, one would be able to see that the numbers converge to 100.

I tried looking for a pattern in the Microsoft Excel simulation but could not seem to find one. I checked the web for clues and I read a blog that mentioned that there is no trick needed for this problem. A straightforward brute-force approach would do. So, I tried implementing a brute-force approach, which fortunately got accepted with a run time of 0.220. I thought I would breach the 2.000-second time limit.

In this implementation, for every test case, I first converted each letter to its corresponding number representation by subtracting the ascii number equivalent of 'A' from the ascii number equivalent of the letter in the test case, and adding ST (lines 033-035). For instance, for an ST value of 81, the letter J would be represented as 90, because the ascii number equivalent of J is 74, while that of A is 65. So, 74-65+81 gives 90.

After converting all letters in the test case to their corresponding number representations that are stored in an integer array, nrep[], I split each number into its individual digits, by a modulo-divide loop (lines 040-044). For instance, to obtain the digits of the number 90, first get the remainder of 90 when it is divided by 10. This would give 0, which is the first digit of 90. Then divide 90 by 10, and this leaves us with 9. The remainder of 9 when it is divided by 10 gives us 9, which is the second digit of 90. Now, we divide 9 by 10, and this gives us the integer, 0, which is our signal to stop the loop. Since, we obtain the digits from the least significant digit, we have to store these digits in reverse into the main array, narr[] (lines 046-048).

Once the main integer array, narr[], is built, we reduce the length of this array by 1 by getting the modulo of the sum of each consecutive integer pair in the array, as described in the problem. We continue reducing the length of the array by 1, and we only stop the reducing loop (lines 051-055) when the length of the array has been reduced to 3. At this length, a check (lines 057-060) is performed to see if a 100 is obtained in the first 3 elements of the array. If a 100 is obtained, the ST loop is broken, and the value of ST which yielded the 100 yuan-fen result is printed. Otherwise, if the ST loop is naturally terminated and not broken mid-way, then a sad-face is printed (lines 066-068).

The first part of the code (lines 009-030) is for parsing words, which in this case, are the test cases, which correspond to the abbreviations of the names of the lovers being assessed for yuan-fen compatibility. I believe there are more convenient ways to parse, but as long as the code works, then maybe it would suffice. Perhaps, my parsing algorithm may have slowed down the performance of my code.

Here is my C/C++ code for your comments, hopefully, for improvements:

001 #include <stdio.h>
002 
003 int main() {
004   char line[100], ctmp[100];
005   
006   int i, j, k, q, r, s, t;
007   int nrep[10], st, narr[50], itmp[5];
008 
009   while (fgets(line, 100, stdin)) {
010     for (i = 0; 1; i += 1) {
011       if (line[i] == '\n' || line[i] == 0) {
012         break;
013       }
014     
015       if (line[i] == ' ' || line[i] == '\t') {
016         continue;
017       }
018 
019       for (j = 0; 1 ; i += 1, j += 1) {
020         if (    line[i] == ' '
021              || line[i] == '\t' 
022              || line[i] == '\n'
023              || line[i] == 0
024         ) {
025           break;
026         }
027       
028         ctmp[j] = line[i];
029       }
030       ctmp[j] = 0;
031       
032       for (st = 1, t = 0; st <= 10000; st += 1) {        
033         for (k = 0; k < j; k += 1) {
034           nrep[k] = ctmp[k] - 'A' + st;
035         }
036         
037         for (k = 0, s = 0; k < j; k += 1) {
038           q = nrep[k];
039           
040           for (r = 0; q > 0; r += 1) {
041             itmp[r] = q % 10;
042             
043             q /= 10;          
044           }
045           
046           for (r -= 1; r >= 0; r -= 1, s += 1) {
047             narr[s] = itmp[r];
048           }        
049         }    
050     
051         for (s -= 1; s > 2; s -= 1) {
052           for (k = 0; k < s; k += 1) {
053             narr[k] = (narr[k] + narr[k+1]) % 10;
054           }
055         }
056         
057         if (narr[0] == 1 && narr[1] == 0 && narr[2] == 0) {
058           t = 1;
059           break;
060         }
061       }
062       
063       if (t) {
064         printf("%d\n", st);
065       }
066       else {
067         printf(":(\n");
068       }
069     }
070   }
071   
072   return 0;
073 }

Thursday, August 2, 2012

11498: Division of Nlogonia

Thought about reviving this blog. I visited UVa Online Judge today and they have a lot of new problems since I last visited it. I tried looking for an easy problem and this is what I found. Here is a sample C++ code solution that got accepted:


#include <stdio.h>

int main() {
  char line[100];
  int num_tests, n, m, x, y;
  char h, v;

  while (1) {
    fgets(line, 100, stdin);
    sscanf(line, "%d", &num_tests);

    if (num_tests == 0) {
      return 0;
    }

    fgets(line, 100, stdin);
    sscanf(line, "%d %d", &n, &m);

    for (int i = 0; i < num_tests; ++i) {
      fgets(line, 100, stdin);
      sscanf(line, "%d %d", &x, &y);

      if (x == n || y == m) {
        printf("divisa\n");
        continue;
      }

      if (x > n) {
        h = 'E';
      }
      else {
        h = 'O';
      }

      if (y > m) {
        v = 'N';
      }
      else {
        v = 'S';
      }

      printf("%c%c\n", v, h);
    }
  }

  return 0;
}