L6: Exhaustive Search and Generation II

This is the last lab of the course. We consider the remaining problems from Jutge.org, section EDA \rightarrow Exhaustive search and generation.

Jutge exercises

In this lab we consider the following Jutge exercises.

• X92609 Two coins of each kind (3) 🔶
• P62138 Topological orderings 🔶
• P37197 Incompatible species 🔶
• P76807 Sudoku
• P70756 Partitions
• P40685 Equal sums (1) 🔶
• P82660 Equal sums (2)
• P11655 Equal sums (3) 🔶
• P93741 Satisfiability ❗

Suggested workflow

Once you have chosen a problem to solve, download the .zip archive of the problem and unzip it. In the obtained folder there are:

• a file .pdf with the official problem statement
• one or more text files with examples of input sample.inp
• the corresponding correct outputs sample.cor

Step 1: Getting the C++ code to compile

After creating a C++ source file to solve the problem, compile it with g++ -std=c++11.

Common error(s)

Not using the flag -std=c++11.

Possible useful flags are -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG

Step 2: Testing testing testing

Test the executable file obtained on the given example(s), for instance with ./a.out < sample.inp > output. Also, test your code against simple/trivial inputs, e.g. a graph with no-edges.

Common error(s)

Writing the input by hand.
Not checking the exact formatting of the output.

To see whether the output is the same as sample.cor a way is to use diff output sample.cor

Step 3: Submitting the solution to the Jutge

Once the code compiles and on the given samples it gives the correct output submit it to the Jutge for automatic evaluation.

Common error(s)

Sending to the Jutge code that was not even compiled locally.
Not checking if the output was correct on the given inputs.

Step 4: I’m stuck. What can I do?

You are “stuck” on a problem if you spent around 1 hour trying to solve it but still the Jutge is rejecting your solution.

Possible approaches to getting “un-stuck” are:

• do not think about that problem for some time and come back to your code with fresh eyes

• look again at the theory

• try to explain your code to another student

• ask for hints, e.g. by email. Be specific on the type of help you need. Include in the email the code of your approach.

From this block of exercises, in class we solve together the ones marked with 🔶. They are the same as the one listed below.¹

Remember that for any doubt on the exercises you can ask me by email too until 6 days before the lab exam.

Footnotes

1. Recall that ❗ marks possibly harder problems.