L1: Use of STL data structures

Welcome to the first lab class of EDA!

In this class we consider the problems from Jutge.org, section EDA \rightarrow Use of STL data structures.

First revise some aspects of The C++ Standard Template Library (STL).

A way more comprehensive treatment of the STL is in cppreference.com.

Jutge exercises

In this lab we consider the following Jutge exercises.

• P50709 Collection of numbers
• P40902 Casino
• P69781 Collatz pseudo-sequences (2) ❗
• P84415 Bag of words
• P37064 Dynamic median ❗
• P59282 Statistical measures 🔶
• P69932 The longest sequence ❗
• P60296 Role classification 🔶
• P60219 Easy game?
• P62653 Ticket distribution 🔶
• P63584 K-th element (~ Problem 4.11 you will see in the problem class P5)

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.