Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2020 -- CSC 2700 Section 01 (Patrick Taylor 1218, 6:00 PM - 7:50 PM)

How to Approach Solving a UVA Problem


Requirements Analysis


Before going any further, lets make sure we really understand the problem.

Read and Understand the Problem

Suggestions:


Analyze the Problem

Questions to answer before moving on:


Design

Questions to answer?


Incremental Implementation Testing (testing in yellow)

At this point, I would deviate a little from the classic Software Development Cycle. Because these problems are relatively small and time to implement is constrained, I would suggest doing iterative implementation and testing. In other words, right the overall program structure and make sure it compiles. The proceed through each section one at a time.

This basic approach is a top-down design process. By going in this manner, you will avoid writing utility code that you never use (maybe you write a sort thinking you need and then realize you don't). Pretend the program is actually a big software system. First you implement the workflow structure (main program). Then you develop each separate program/module in the system. So, in actuality, we are not deviating from the SDLC, we are simply using it recursively inside a single program.


Input

Write the code to load the data in. If complicated, write a dump function to display the input to make sure it was loaded properly. Resist the temptation to do input inline of the processing. If the input is anything other than trivial, making the input logic and the processing logic work together can be tricky. Our goal is to simplify.


Base Processing

Now start writing the basic processing code that you will need to solve the problem. As details or sub-processes come up make function calls for them. Then go write dummy function stubs as placeholders.

Get this basic logic working. At this point you also stuff in the desired output code. Here is a good chance to ensure that your planning has everything you need to output.


Iteratively fill in the stubs

Now you should start writing the various utility functions you determined you needed (maybe a sort or search, or an insert, ...). As you write each one, compile it and test it as best as you can.


What to do if something goes wrong?

The first step is to go back to the beginning:


Cannot figure out what algorithm to use

This might also be phrased as "I do not know where to start". In a contest, this means that you should not do this problem. Either someone else on the team needs to do it or it needs to be skipped. If everything else is done and you are doing this because time is left over, then soldier forward. Brainstorm. Work as a team on this. Resort to bottom up. Ge the basic structure done. Make sure input works. Then start throwing code at it...

If you are not in a contest, you have more options. Here are some:


Output for sample data is wrong

Here are some things to do:


Run time error

These can be frustrating. Here are a few ideas:


Sample data works, but Wrong Answer judgement

This is very similar to Run time error. Make sure you are testing all data cases.