Finding the easy problems

For starters, it would be best to try to solve the easier problems first. If one tried solving the hard problems first, then he might get frustrated immediately from getting rejected submissions one after the other. It could also happen that he would get stuck in a single problem for several days and end up extremely disappointed in programming and swearing never to do programming again.

For competitors in a contest, it is also best to find, solve and submit the easier problems first given a set of problems. Otherwise, one might spend so much time in a single hard problem that he losses time that could have been more productively used to submit much easier problems. So instead of submitting 3 easy problems at the end of the contest, he only submits 1 hard problem. But the weight of the easy problem is just the same weight as a hard problem in a programming competition.

So, when one starts a contest, before solving any problem, he should scan and sort out which problems are easier to solve first. Then he should solve the easier problems first. If he wishes to win, then he should resist the temptation of solving the hard problem first for whatever reason. The easy problem and the hard problem would earn one the same amount of money if the contest awarded cash prizes. So why should one consume all his time in solving a hard problem, unless he is not after winning the contest and just simply after programming insight enlightenment?

In this post, I discuss about finding easy problems in the UVa problem archive. Easy problems are only relative in the sense that they are easy compared to the other problems also existing within the archive. So how do we define relativity? Through statistics.

Figure 1 shows a screenshot of the problem archive where statistics are shown for each problem.


Figure 1. Screenshot of the problem archive.

Two ratio statistics are shown for each problem. The first one is the ratio of accepted submissions to total submissions. Let’s call this the BR ratio. For example, for problem 10800, the BR ratio is 19.73%. The second ratio is the ratio of number of users who actually solved the problem to the total number of users who attempted to solve the problem regardless of whether they solved it or not. Let’s call this the UR ratio. For problem 10800, the UR ratio is 67.51%.

Two other statistics exist which are the total submissions for a problem (B value) and the total number of users who attempted to solve a problem (U value). For problem 10800, B is 5039 meaning there were 5039 submissions for this problem whether the submissions were accepted or rejected. For the same problem, U is 1265, meaning there were 1265 users who submitted solutions whether their solutions were accepted or not.

So given this statistics, how do we interpret them? Generally, to find an easy problem, we would want to look for one which has a relatively high BR ratio. This means that an easy problem would be a problem for which most submissions were accepted because it was easy to solve so most people solved it in their first attempt or submission.

Figure 2 shows an example were an easy problem is visually spotted out.


Figure 2. Problem 10865 is likely to be an easy problem.

In Figure 2, one can easily point out that problem 10865 can likely be an easy problem because of the high BR ratio relative to its surrounding neighbor problems. The BR ratio stands out at 71%. Its closest rival has a BR ratio of 55.81%. The 71% BR ratio means that for about every 10 submissions, 7 of those were accepted. With a higher statistical historical ratio, one’s likelihood of solving the problem becomes higher. So it would be better if one start with such easy problems when starting his career in programming in order not to get frustrated at the start of his career immediately.

There is a watch out though. Figure 3 shows an example.

Figure 3. Problem 717 appears to be an easy one but could be actually a real hard one.

In Figure 3, problem 717 stands out easily with a BR ratio of 83.33%. This ratio is very high compared to other problems’ ratios. But looking at its B value of only 18, something looks fishy. The B value is very low which means that out of the tens of thousands of coders, only 18 solutions were submitted. Looking at the U value reveals something even more dismal: only 12 users attempted to solve this problem.

So why did most users avoid this problem as only 12 out of the tens of thousands of coders attempted to try this problem? Most probably this problem is a difficult one which most coders have no idea on how to solve. And those who attempted to solve it were most likely the genius type of users. Remember in high school or college when there would always be someone in class who stands out because of his extreme intelligence. Well, this is perhaps the type of person who solves the problem like problem 717.

So one feel that he is confident to take on really challenging problems, and that most problems have become too easy already, and that he has had enough programming experience already so that he is no longer vulnerable to becoming frustrated whenever he is unable to solve difficult problems, then one must at all cost avoid this type of problems with high BR ratios but extremely low B values.

Notice also that for problem 717, out of the 12 users who attempted it (U = 12), all of them were able to solve it (UR = 100%), confirming that these few people must indeed be geniuses.

UVa problem 11364: sample algorithm

To solve UVa problem 11364 (Parking), it would be beneficial to know that the minimal distance Michael has to walk is simply twice the distance from the farthest store to the nearest store. For example, consider the following setup:
A________B______________C_____D
X______________________________

A, B, C and D are the stores while X is Michael’s car. To get to all the stores and return to his car, Michael would have to walk:

A to B
B to C
C to D
D to C
C to B
B to A

In essense, the total distance he would have traveled would be just twice the distance from A to D.

Consider now the following setup:

A________B______________C_____D
__________________X____________

For Michael to get to all stores and return to his car, he would need to walk:

X to B
B to A
A to B
B to X
X to C
C to D
D to C
C to X

Again, analyzing this series of walks, it is simply twice the distance from A to D.

Hence to compute the minimal distance given a series of stores to walk to, simply find the nearest store and the farthest store, get their difference and then multiply the difference by 2.

UVa problem 11364: sample code

001 #include "stdio.h"
002 #include "stdlib.h"
003 
004 int main() {
005   char  line[100]
006       , ctmp[100]
007   ;
008   int   num_tests
009       , num_stores
010       , stores[100]
011       , itmp
012       , max
013       , min
014       , diff
015       , i
016       , j
017       , k
018       , m
019   ;
020 
021   fgets(line, 100, stdin);
022   sscanf(line, "%d\n", &num_tests);
023 
024   for (i = 0; i < num_tests; i += 1) {
025     fgets(line, 100, stdin);
026     sscanf(line, "%d\n", &num_stores);
027 
028     fgets(line, 100, stdin);
029     for (j = 0, m = 0; 1; j += 1) {
030       if (line[j] == '\n' || line[j] == 0) {
031         break;
032       }
033 
034       if (line[j] == ' ' || line[j] == '\t') {
035         continue;
036       }
037 
038       for (k = 0; 1 ; j += 1, k += 1) {
039         if (line[j] == ' ' || line[j] == '\t' || line[j] == '\n' || line[j] == 0) {
040           break;
041         }
042         ctmp[k] = line[j];
043       }
044       ctmp[k] = 0;
045 
046       stores[m] = atoi(ctmp);
047       m += 1;
048     }
049     
050     max = 0;
051     min = 99;
052     for (j = 0; j < num_stores; j += 1) {
053       if (stores[j] > max) {
054         max = stores[j];
055       }
056 
057       if (stores[j] < min) {
058         min = stores[j];
059       }
060     }
061     diff = max - min;
062     diff *= 2;
063 
064     printf("%d\n", diff);
065   }
066 
067   return 0;
068 }

UVa problem 10851: sample algorithm

In UVa problem 10851 (2D Hieroglyphs decoder), one could explore the advantage of using right bit-shifts instead of long-cut division for division by powers of 2. For example, to divide a number by 128 (which is 2 raised to the power of 7), one could simply shift the number 7 bits to the right.Definitely, this fact could give one an advantage as a bit-shift operation is so much simpler and faster than traditional division.

Moreover, the mod operation may be quite computationally expensive as well. Since a mod by 2 operation is only needed, one could simply check whether the last binary bit of a number is 0 or 1 in order to tell if the number is divisible by 2 or not.

For example, the number 15 when represented in binary is 1111. Since its last bit (the right-most) is 1, then it is not divisible by 2. The number 12 when represented in binary is 1100. Since the last bit is 0, then it is divisible by 2. Bitwise-ANDing the number with 1 will enable one to get the last bit of the number.

For this problem, one could build a lookup table for each of the 256 ASCII characters. One could explore the use of a C++ standard map, where the key is the encrypted character and the value is the actual ASCII character. For example, we could build a map like the following:

Key, Value
//\\//\/, L
\/////\/, A
…

And so when our program sees an encryption of //\\//\/, it can simply lookup the map and find that the encryption stands for the ASCII character L.

UVa problem 10851: sample code

001 #include "stdio.h"
002 #include "string"
003 #include "map"
004 #include "iostream"
005 
006 using namespace std;
007 
008 int main() {
009   char   line[100]
010        , ctmp[100]
011        , dtmp[100]
012        , input[10][100]
013        ;
014   int   num_msg
015       , i
016       , ii
017       , j
018       , k
019       , b
020       , c
021       , m
022       , n
023       , p
024       , msg_len;
025       ;
026 
027   map imap;
028   map::iterator iter;
029 
030   for (c = 0; c < 256; c += 1) {
031     ctmp[0] = '/';
032     ctmp[9] = '/';
033 
034     for (i = 1; i < 9; i += 1) {
035       ii = i - 1;
036 
037       b = c >> ii;
038       b &= 1;
039 
040       ctmp[i] = b == 0 ? '/' : '\\';
041     }
042 
043     ctmp[10] = 0;
044 
045     imap.insert(pair(ctmp, c));
046   }
047 
048   fgets(line, 100, stdin);
049   sscanf(line, "%d\n", &num_msg);
050 
051   for (i = 0; i < num_msg; ++i) {
052     for (j = 0; j < 10; ++j) {
053       fgets(line, 100, stdin);
054       sscanf(line, "%s\n", &input[j]);
055     }
056 
057     fgets(line, 100, stdin);
058 
059     msg_len = strlen(input[0]) - 2;
060 
061     for (m = 1, p = 0; m <= msg_len; m += 1, p += 1) {
062       for (n = 0; n < 10; n += 1) {
063         ctmp[n] = input[n][m];
064       }
065       ctmp[n] = 0;
066 
067       iter = imap.find(ctmp);
068       dtmp[p] = iter->second;
069     }
070     dtmp[p] = 0;
071 
072     printf("%s\n", dtmp);
073   }
074 
075   return 0;
076 }

Getting input

For programming competitions, input will usually come from standard input; that is, input is taken from the user manually typing the input, or input is directed into the program from a file.

When input is manually typed by the user, it will be like Figure 1.

Figure 1. Input manually typed by the user.

In Figure 1, the user manually types the input “User is typing this line now.”

When input is directed into the program from a file, it would appear like Figure 2.

Figure 2. Input directed from a file.

In Figure 2, the contents of the file i.txt are inputted into the program.

Reading a line from standard input can be done using Code 1.

Code 1. Reading a line from standard input.

#include "stdio.h"

int main() {
__char line[100];


__fgets(line, 100, stdin);


__return 0;
}

In Code 1, the fgets statement is configured to read from standard input using the stdin parameter. The line read is then placed into the character array line. The parameter 100 is used to indicate the maximum number of characters to be read. We use 100 since we declared the line variable to be a character array of 100 slots.

In Code 1, once the fgets statement is executed, the user can pretty much do anything with the line variable which contains the line read from standard input. For example, the user can print the contents into standard output such as the code in Code 2.

Code 2. Printing what was read from standard input.

#include "stdio.h"

int main() {

__char line[100];

__fgets(line, 100, stdin);

__printf("User typed the following: %s\n" , line);

__return 0;

}

When Code 2 is executed, it behaves like Figure 3.

Figure 3. Sample execution of Code 2.

Dev-C++

Most of the algorithms I will be discussing will be based on how I will implement them in the C/C++ language. Although algorithms should be purely independent of the programming language used, I often think of the algorithms in terms of the underlying language I would be using to implement them.

In this post, I will be discussing the tool used for compiling the C/C++ codes I create to test my algorithms. Although everyone has his own way of compiling – like others may use g++ or Visual C++ – others may have no idea on how to compile. This post is dedicated to those others who have no idea or are confused on how to compile their codes. I present my way of compiling.

To compile my C/C++ codes, I use the tool Dev-C++. You can use Google to search for it. It’s a tool my teacher from school taught me. I thought I would only use it in school, but when I started working as an employee, I was also using it in the company’s regular programming competitions.

Interestingly, several years since I last used the tool in school, the tool had not changed much. Somehow, someway or another, people just stopped developing the tool, and so no new updates or versions of the tool were released since I last used it in school. And that was several years ago.

Somehow also, it is the only Windows C++ compiler I know how to use until this date. In school, I used to use Borland C++ or Microsoft Visual C++. But somehow, these other tools lost popularity. Borland C++ definitely lost popularity as I don’t hear anybody using it anymore, at least in my neighborhood. Microsoft Visual C++ definitely is ultra popular, but how in the world do you get the software for free. Microsoft keeps collecting money from us, until we third world developers have nothing left to use to develop our ideas and algorithms.

So, I was left with Dev-C++, until now, and who knows, maybe until I’m real old and shriveled like a rotten tomato, still aspiring to be a decent programmer.

Now, going back to the real topic. The Dev-C++ website is kind of confusing. I always got lost in it back in college when I had to download the binary and install it into a workstation. In my days, we had no personal laptops and so we had to hop from one computer to another, and install the bloody tool every time we saw that the workstation we hopped into did not have the tool installed into it.

To download the tool, go to the following website:
http://www.bloodshed.net/devcpp.html

Figure 1 shows a screenshot of the site.

Figure 1. Screenshot of the Dev-C++ website.

Click onto the download page, download the binary and install it. By the way, Dev-C++ is for Windows.

Once installed, you can immediately use it. Figure 2 shows a screenshot of the Dev-C++ tool.

Figure 2. Screenshot of the Dev-C++ tool.

Through the tool, you type in your code, save it and then compile (CTRL-F9). Should there be no compile errors, you can close the dialog box shown in Figure 2. Open a command prompt and run the executable as shown in Figure 3.

Figure 3. Executing the executable.

In Figure 3, go to the directory where you saved your code. More often than not, the executable will be the same name as the file name of your code except for the suffix extension. For example, if you named your code a.cpp, then most likely, an executable named a.exe will be created if your compilation yielded no errors. Simply type the name of the executable to execute.

UVa Online Judge

The UVa Online Judge (http://icpcres.ecs.baylor.edu/onlinejudge/) is a website that archives thousands of problems used for computer programming competitions. It also provides a facility for validating code submissions to the problems published. Hence, it offers an excellent venue for testing algorithms.

Each problem in the archive is tagged with an ID number for easy identification. Refer to Figure 1.


Figure 1. Problems listing in the archive.

In Figure 1, the problem “Moscow time” has an ID number of 505.

Codes can be submitted for online validation can be written in C, Java, C++ or Pascal. Figure 2 shows the form for online submission.

Figure 2. Form for online code submission.

To search for a problem, one can opt to use the Google search bar as shown in Figure 3.

Figure 3. Google bar for searching problems.

Simply type in the problem ID in the Google bar. Be sure to tick the icpcres.ecs.baylor.edu button.

Welcome!

Welcome to Algorithm Share!

This blog is about sharing algorithms with others.

As for now, most of the problems to which algorithms will be discussed will come from the UVa Online Judge: http://icpcres.ecs.baylor.edu/onlinejudge/

I encourage you to post comments if you have algorithms to share as well. Most of the algorithms I will share will be my own ideas, but I believe that there are a thousand more algorithms out there that are more optimized than my own for a given problem. So, please do share your algorithms for me to learn as well.