How to Approach Solving a UVA Problem

• Requirements Analysis
  • Read and understand the Problem
  • Analyze the Problem
• Design
• Incremental Implementation Testing (testing)
• What to do if something goes wrong?
  • Cannot figure out what algorithm to use
  • Output for sample data is wrong
  • Run time error
  • Sample data works, but Wrong Answer judgement

Requirements Analysis

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

Read and Understand the Problem

Suggestions:

• Glance over problem
• Read it thoroughly once
• Make sure input and output make sense to you
• Make sure you can get the output from the given input

Analyze the Problem

Questions to answer before moving on:

• Are there any gotchas?
• What is the domain (how might input vary)?
• How does input/processing stop?
• What is the range (how might the output vary)?
• What are the edge/corner cases?
• What kind of problem is this? (big number, sort, flood fill, ...)

Design

Questions to answer?

• What will be the general program layout? (trailer card, counted, EOF, custom)
• What data structures make sense?
• What algorithms make sense?
• What will run time be? (Big O)
• Will data fit into memory constraints?

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:

• reread the problem
• make sure you can process the sample data properly
• confirm your data structures and algorithms
• talk to teammates/classmates
• use the steps below

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:

• Sleep on it and/or go to another problem
• Restart the entire process (reread, ...)
• If you know what algorithm to use but do not know how to implement that algorithm, try these:
  • Look the algorithm up on wikipedia.
  • Try your favorite reference book
  • Try the Cormen Introduction to Algorithms book.
  • Try Skiena's Programming Challenges
  • Try Halim's Competitive Programming
  • Try the Algorithmist
  • Try the UVA Forums (search on google for uva/online judge problem-number and title in quotes)
  • Ask classmates
  • Bring it up in class
  • Ask Isaac
  • Ask the class mailing list
  • Look at the toolbox
  • Search for uva online judge problem-number and title of problem in quotes
  • Use UVA site to make sure other folks have actually solved this problem (if the solvency rate is low, the problem may be very hard or may have an error).

Output for sample data is wrong

Here are some things to do:

• Reread the problem - make sure you understand
• Can you manually get the output from the input? If not, then figure out how. If you can do it manually, figure out where your code is not doing what you are?
• Are all cases wrong?
  • Confirm data is still being loaded correctly.
  • Did all variables get initialized properly?
  • Make sure routines are getting called (did you write a sort and forget to call it?).
  • Review your computation to make sure it is correct.
  • Start inserting output statements to trace runtime and figure out where the codes operation deviates from your expectation.
  • Explain your code to somebody (not necessary for them to know the language, but it can help).
• First case right, all others wrong. Almost always this relates to not clearing/resetting some value after the first iteration. Carefully make sure that every variable starts out with the right initial value(s).
• Some cases wrong.
  • What do these case have in common? This could point to a section of code that contains the error.
  • What do the right answers have in common. Sometimes it is the other way around. Sometimes the wrong ones seem to be random. Usually, this implies that the right ones have something in common that the wrong ones do differently.
  • It is possible that more than one thing is broken that is causing multiple different wrong answers.
  • It is possible that all of the right answers are not right because your code is. People have written code that gets the right answer (sometimes/always) without doing the correct computation.
  • Take advantage of people/class/mailing list.
  • Use uDebug to process the sample input to make sure that the sample output is correct (problem statements have been know to wrong. Maybe formatting is messed up because of html misleading you).

Run time error

These can be frustrating. Here are a few ideas:

• Do you get runtime error on sample data? -- see Output for sample data is wrong
• Sample data right, but runtime error from judge
  • Try more input data
    • Make some up yourself
    • Check uDebug for additional input files
    • Check the UVA Forums for additional sample data (run the input through uDebug and compare to that output)
  • Make sure everything is properly initialized (overall and each iteration)
  • Check limits -- make sure any limit you have in your code (array size, loops, stack, ...) match the problem definition.
  • Try increasing limits (a problem I just did said there would be at most 100 input cases but the forum said the input had over 300)
  • Avoid storing lists of things unnecessarily. If something is not needed long term, don't load it in a list and then process the list -- just process it dynamically. Without a list, you cannot run out of space to save entries.
  • Try steps listed under Cannot figure out what algorithm to use. The resources there may help you spot the problem.
  • If you have a table or something declare the table big enough to have a border around it make sure that border area (where nothing should ever write) remains pristine.

Sample data works, but Wrong Answer judgement

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