Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2019 -- CSC 2700 Section 01 (Patrick Taylor 1212 (CEBA) [expane.toop.mimc], 6:00 PM - 7:50 PM)

How to Approach Solving a Online Judge 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 wiritng 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 devlope 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 imput 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 asic 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.

Ge tthis 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 becuase time is left over, then soldier forward. Brainstorm. Work as a team on this. Resort to bottom up. Ge thte basic strucutre 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.