29
Fri, Nov
0 New Articles

Microsoft Computing: Contest Programming

Microsoft
Typography
  • Smaller Small Medium Big Bigger
  • Default Helvetica Segoe Georgia Times

Computer programming is an exercise in problem solving. As a programmer, you are presented with the challenge of creating a computerized solution. Using your logic and experience, you craft the solution, and when you're finished, there's a good degree of satisfaction exchanged for your effort. The programming process may even include a clever flash of insight, which is also rewarded with a feeling of accomplishment.

Within the programmer community, there exists an association of folks who take programming and problem-solving to a global level of organization. This is the world of contest programming.

Contest Programming

Contest programming is designed to sharpen programmers' problem-solving and coding skills in a competitive structure. Programmers can compete with others from all over the world to see how well they stack up to one another.

Contest problems can also be taken out of the competitive setting and used as a set of little coding puzzles, available to one and all. These little problems can be a great source of practice for learning a new coding language or for acquiring additional problem-solving skills.

In either case, contest programming consists of problems that are to be solved with a computer, the solution source code that will produce the solution, and a judge that decides whether the solution is correct. A solution is considered to be correct if it produces the correct output. Beyond some loose performance restrictions (your program must run in less than one minute, for instance,) there is no consideration for coding practices. That is, there are no style points in contest programming.

Problem Solving

To the iSeries professional operating within a business environment, "problem solving" usually takes the form of, for example, a call from Debbie in AP: "Hi. How's the family? (No pause.) I've just printed 300 checks on check stock for an account that was closed four months ago. Can you help me? (Now, a pause.) Roll something back, maybe, like last time? Lemme know by 3:00? Soccer night. Thanks."

Well, problem solving can also mean the act of creating a computer solution to a sort of contrived programming challenge. The value in such an enterprise is an increase in logic and coding abilities, plus an exposure to new data structures and programming techniques.

Take, for example, the famous "traveling salesman" problem. That is, what is the shortest route a traveling salesman can take to visit each city in his territory once and then return home? Well, as you would expect, the answer to this problem has been worked out. The solution is also famous and is known as Dijkstra's Shortest Path Algorithm. But still the challenge remains of turning something like Dijkstra's Algorithm into actual working code.

Note that it is not uncommon for some employers (Microsoft among them) to focus on an employment candidate's problem-solving skills when being considered for hire. Many organizations use the contest problems as a test of these skills. Such a test shows how well and how fast you can code.

University Programming Contests

Contest programming has been used within colleges and universities for a long time to teach and recognize good problem-solving skills. The contests range from small internal events where students within a given school compete with each other to large state, regional, and national trials.

Here's how a typical programming contest works within the computer science departments of many universities. Teams of two to four programmers are given five hours to solve as many short, yet challenging, programming problems as they can. Teams are given a list of programming problems as the clock is started. Each problem may be solved with a short C, C++, or Java program, but the solution requires some degree of coding dexterity. Once a solution has been created, the code is submitted to a judge. The judge runs the program against a robust set of test data to expose any flaw in the solution. If the solution is correct, the team scores a point, and the number of minutes since the beginning of the contest is noted and accumulated. At the end of the five hours, the team that has solved the most problems wins. If more than one team has the same number of solved problems, the total minutes taken determines the winner. The fewer minutes taken to solve the problems, the better.

Contestants may bring printed reference materials to the contest, but electronic media and Internet access are not allowed. (Note that the current trend may change to disallow printed reference material as well.)

What a Contest Problem Looks Like

A typical contest problem resembles this popular example, called the "Crypt Kicker II". (The term "crypt" refers to encryption.) This example by Miguel Revilla is from the Universidad de Valladolid contest Web site.

Crypt Kicker II

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.

A common method of cryptanalysis is the known plaintext attack. In a known plaintext attack, the cryptanalist manages to have a known phrase or sentence encrypted by the enemy, and by observing the encrypted text then deduces the method of encoding.
 

Your task is to decrypt several encrypted lines of text, assuming that each line uses the same set of replacements, and that one of the lines of input is the encrypted form of the plain text

the quick brown fox jumps over the lazy dog

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of several lines of input. Each line is encrypted as described above. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length. There are at most 100 input lines.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Decrypt each line and print it to standard output. If there is more than one possible decryption (several lines can be decoded to the key sentence), use the first line found for decoding.

If decryption is impossible, output a single line:
No solution.

Sample Input

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

Sample Output

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

This example problem is a text-handling puzzle. Other problems focus on other coding challenges like array handling, algorithmic manipulations, or programming concepts such as recursion. In any type of problem, the exact output as described in the problem must be provided by your solution program.

The Solution

The solution to the above problem will take the form of a small Java, C++, or C program (or sometimes Pascal) consisting of a single source file. The program will accept the input from standard in and send the output to standard out. Nothing more and nothing less. Absolutely nothing.

If you're coding in Java, you may use all the tools found in the Java SDK. For example, you may use the Java language function Math.sqrt to get the square root of a number. If you're coding in C/C++, you may use all the functions in the standard libraries.

Universidad de Valladolid

At Spain's Universidad de Valladolid (or UVa) beats the heart of the contest programming scene. As Rochester is to the iSeries, Valladolid is to contest programming (Figure 1).

http://www.mcpressonline.com/articles/images/2002/Microsoft-ContestProblems%20V3--04190400.jpg

Figure 1: The Universidad de Valladolid Web site is the center of the contest programming world. (Click image to enlarge.)

In this well-supported Web site is a collection of established problems and an online judging process. The UVa maintains a database of contest problem participants, the problems attempted, and the results. Anyone can join and participate in this free service sponsored by the Association of Computing Machinery (ACM). If you're a programming puzzle enthusiast or if you're trying to hone your instruction-following and problem-solving skills, this is for you.

Part of the UVa Web site for contest programming is the online judge. The online judge is really a program, not a person. Once you've attempted to solve a problem, you submit your program source code to the online judge. The judge first tries to compile your code. If your code compiles, the judge launches your program and feeds it the test data (note that the judge's test data is much more exhaustive than the example input shown in the problem instructions).

Once the judging is complete, the results are made available to you. If your program was found to be unacceptable (and believe me, this can happen even when you're absolutely sure it's correct), you are given a hint as to the nature of the flaw. For example, the return value from the online judge could be CE for compiler error, WA for wrong answer, or TL for time limit exceeded. You then fix the problem and submit it again. Typically, multiple submissions will be required before you've thought of everything and finally pass. See the UVa Web site for more information.

The Programming Challenges Book and Web Site

If you're interested in participating, you may do well to look into the book Programming Challenges by Steven S. Skiena and Miguel A. Revilla. This book is dedicated to contest programming participants and contains very valuable instructions and tips, together with over 100 of the best programming problems from UVa. Also included are discussions of the various programming techniques typically used to solve these types of problems (graph traversal, backtracking, number theory, recursion, etc.). Please see the Programming Challenges Web site.

TopCoder Web Site

Another resource for contest problems deserves mention: the TopCoder Web site. TopCoder is a contest problem Web site where the best programmers from around the world are tracked and ranked. These sponsored competitions are handled in a variety of ways. Some are directed at collegiate level programmers, some are sponsored by organizations (like Sun Microsystems), and then there are the ones by special invitation only for the coding elite. This site is for true red-meat programmers only.

Some of the sharpest programmers in the world participate in contest programming, and you might be surprised at how they stack up. Take a look at the world rankings sometime. You have to go quite a way down the list before finding the first entry from the United States. As of this writing, a young man from Poland with the handle "Tomek" is the world's best contest programmer. Tomek has earned over $50,000 in coding competitions.

Chris Peters has 26 years of experience in the IBM midrange and PC platforms. Chris is president of Evergreen Interactive Systems, a software development firm and creators of the iSeries Report Downloader. Chris is the author of The OS/400 and Microsoft Office 2000 Integration Handbook, The AS/400 TCP/IP Handbook, AS/400 Client/Server Programming with Visual Basic, and Peer Networking on the AS/400 (MC Press). He is also a nationally recognized seminar instructor. Chris can be reached at This email address is being protected from spambots. You need JavaScript enabled to view it..

Chris Peters has 32 years of experience with IBM midrange and PC platforms. Chris is president of Evergreen Interactive Systems, a software development firm and creators of the iSeries Report Downloader. Chris is the author of i5/OS and Microsoft Office Integration Handbook, AS/400 TCP/IP Handbook, AS/400 Client/Server Programming with Visual Basic, and Peer Networking on the AS/400. He is also a nationally recognized seminar instructor and a lecturer in the Computer Science department at Eastern Washington University. Chris can be reached at This email address is being protected from spambots. You need JavaScript enabled to view it..


MC Press books written by Chris Peters available now on the MC Press Bookstore.

i5/OS and Microsoft Office Integration Handbook i5/OS and Microsoft Office Integration Handbook
Harness the power of Office while exploiting the i5/iSeries database.
List Price $79.95

Now On Sale

BLOG COMMENTS POWERED BY DISQUS

LATEST COMMENTS

Support MC Press Online

$

Book Reviews

Resource Center

  • SB Profound WC 5536 Have you been wondering about Node.js? Our free Node.js Webinar Series takes you from total beginner to creating a fully-functional IBM i Node.js business application. You can find Part 1 here. In Part 2 of our free Node.js Webinar Series, Brian May teaches you the different tooling options available for writing code, debugging, and using Git for version control. Brian will briefly discuss the different tools available, and demonstrate his preferred setup for Node development on IBM i or any platform. Attend this webinar to learn:

  • SB Profound WP 5539More than ever, there is a demand for IT to deliver innovation. Your IBM i has been an essential part of your business operations for years. However, your organization may struggle to maintain the current system and implement new projects. The thousands of customers we've worked with and surveyed state that expectations regarding the digital footprint and vision of the company are not aligned with the current IT environment.

  • SB HelpSystems ROBOT Generic IBM announced the E1080 servers using the latest Power10 processor in September 2021. The most powerful processor from IBM to date, Power10 is designed to handle the demands of doing business in today’s high-tech atmosphere, including running cloud applications, supporting big data, and managing AI workloads. But what does Power10 mean for your data center? In this recorded webinar, IBMers Dan Sundt and Dylan Boday join IBM Power Champion Tom Huntington for a discussion on why Power10 technology is the right strategic investment if you run IBM i, AIX, or Linux. In this action-packed hour, Tom will share trends from the IBM i and AIX user communities while Dan and Dylan dive into the tech specs for key hardware, including:

  • Magic MarkTRY the one package that solves all your document design and printing challenges on all your platforms. Produce bar code labels, electronic forms, ad hoc reports, and RFID tags – without programming! MarkMagic is the only document design and print solution that combines report writing, WYSIWYG label and forms design, and conditional printing in one integrated product. Make sure your data survives when catastrophe hits. Request your trial now!  Request Now.

  • SB HelpSystems ROBOT GenericForms of ransomware has been around for over 30 years, and with more and more organizations suffering attacks each year, it continues to endure. What has made ransomware such a durable threat and what is the best way to combat it? In order to prevent ransomware, organizations must first understand how it works.

  • SB HelpSystems ROBOT GenericIT security is a top priority for businesses around the world, but most IBM i pros don’t know where to begin—and most cybersecurity experts don’t know IBM i. In this session, Robin Tatam explores the business impact of lax IBM i security, the top vulnerabilities putting IBM i at risk, and the steps you can take to protect your organization. If you’re looking to avoid unexpected downtime or corrupted data, you don’t want to miss this session.

  • SB HelpSystems ROBOT GenericCan you trust all of your users all of the time? A typical end user receives 16 malicious emails each month, but only 17 percent of these phishing campaigns are reported to IT. Once an attack is underway, most organizations won’t discover the breach until six months later. A staggering amount of damage can occur in that time. Despite these risks, 93 percent of organizations are leaving their IBM i systems vulnerable to cybercrime. In this on-demand webinar, IBM i security experts Robin Tatam and Sandi Moore will reveal:

  • FORTRA Disaster protection is vital to every business. Yet, it often consists of patched together procedures that are prone to error. From automatic backups to data encryption to media management, Robot automates the routine (yet often complex) tasks of iSeries backup and recovery, saving you time and money and making the process safer and more reliable. Automate your backups with the Robot Backup and Recovery Solution. Key features include:

  • FORTRAManaging messages on your IBM i can be more than a full-time job if you have to do it manually. Messages need a response and resources must be monitored—often over multiple systems and across platforms. How can you be sure you won’t miss important system events? Automate your message center with the Robot Message Management Solution. Key features include:

  • FORTRAThe thought of printing, distributing, and storing iSeries reports manually may reduce you to tears. Paper and labor costs associated with report generation can spiral out of control. Mountains of paper threaten to swamp your files. Robot automates report bursting, distribution, bundling, and archiving, and offers secure, selective online report viewing. Manage your reports with the Robot Report Management Solution. Key features include:

  • FORTRAFor over 30 years, Robot has been a leader in systems management for IBM i. With batch job creation and scheduling at its core, the Robot Job Scheduling Solution reduces the opportunity for human error and helps you maintain service levels, automating even the biggest, most complex runbooks. Manage your job schedule with the Robot Job Scheduling Solution. Key features include:

  • LANSA Business users want new applications now. Market and regulatory pressures require faster application updates and delivery into production. Your IBM i developers may be approaching retirement, and you see no sure way to fill their positions with experienced developers. In addition, you may be caught between maintaining your existing applications and the uncertainty of moving to something new.

  • LANSAWhen it comes to creating your business applications, there are hundreds of coding platforms and programming languages to choose from. These options range from very complex traditional programming languages to Low-Code platforms where sometimes no traditional coding experience is needed. Download our whitepaper, The Power of Writing Code in a Low-Code Solution, and:

  • LANSASupply Chain is becoming increasingly complex and unpredictable. From raw materials for manufacturing to food supply chains, the journey from source to production to delivery to consumers is marred with inefficiencies, manual processes, shortages, recalls, counterfeits, and scandals. In this webinar, we discuss how:

  • The MC Resource Centers bring you the widest selection of white papers, trial software, and on-demand webcasts for you to choose from. >> Review the list of White Papers, Trial Software or On-Demand Webcast at the MC Press Resource Center. >> Add the items to yru Cart and complet he checkout process and submit

  • Profound Logic Have you been wondering about Node.js? Our free Node.js Webinar Series takes you from total beginner to creating a fully-functional IBM i Node.js business application.

  • SB Profound WC 5536Join us for this hour-long webcast that will explore:

  • Fortra IT managers hoping to find new IBM i talent are discovering that the pool of experienced RPG programmers and operators or administrators with intimate knowledge of the operating system and the applications that run on it is small. This begs the question: How will you manage the platform that supports such a big part of your business? This guide offers strategies and software suggestions to help you plan IT staffing and resources and smooth the transition after your AS/400 talent retires. Read on to learn: