Tutorial
Contents:
- Problem A: Decimal Part
- Problem B: Gotcha!
- Problem C: Kiosk Change
- Problem D: Usernames
- Problem E: Mike’s Puzzle
Now we have the final results of the Welcome-Back Challenge, it is time to review and discuss the problems and their solutions in detail. There is always more than way to implement a solution in programming. We often speak of a better solution/algorithm as the one that requires less memory or execution time. Also, a better algorithm will perform fairly well on a small input as with the large input i.e. if it takes the algorithm 1 second to find a solution for 10X10 grid, it should not take a day to find the solution for 1,000,000X1,000,000 grid.
Click here to download the PDF of the problems.
Note: All the source code snippets will be provided in C++. The provided code snippets are examples of many ways to solve the problems.
Problem A: Decimal Part
The problem had two key challenges: how to extract the fraction part of a decimal number and how to format a number to display only four decimal places.
- Extracting a fraction part of a decimal number
This can be achieved by finding the difference between the decimal number and the whole/integer part of the number.
float fraction = number - int( number );
- Display only four decimal places of a number
In C++, the number of decimal places can be fixed using Input/Output Manipulation header (#include<iomanip>) tags: fixed and setprecision as shown below.
cout << fixed << setprecision(4) << fraction << endl;
Problem B: Gotcha!
This problem requires the application of a typical if-then-else block. After inputting the two numbers (say A and B), the sum and product of the two numbers can be compared as follows.
if( A+B > A*B ) cout << "SUM" << endl; else if( A+B < A*B ) cout << "PRODUCT" << endl; else cout << "GOTCHA!" << endl;
Problem C: Kiosk Change
This is an example of a problem that utilizes a greedy algorithm.
A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. Source
The minimum number of notes/coins can be determined by always asking the question: What is the biggest note/coin that can fit the current change?
Suppose that we need to return the change of TZS 3,500. The biggest note/coin we can use at the moment is 2000-note. After this, the remaining change will be TZS 1,500. At this point, the biggest note/coin is 1000-note. This will leave TZS 500 which we can use a 500-coin for. Hence, a TZS 3,500 change can be effectively be returned using 3 notes/coins.
Therefore, for any given change, we can walk through the given list of notes/coins (10000, 5000, 2000, 1000, 500, 200, 100, and 50) in descending order and check if the current note can be used to return the remaining change. Suppose the change is in variable change, the above algorithm can be implemented to produce the results in variable notes_needed.
const int DENOM_COUNT = 8;
const int DENOMS[] = { 10000, 5000, 2000, 1000, 500, 200, 100, 50 };
int notes_needed = 0;
while( change > 0 ){
for( int i = 0; i < DENOM_COUNT; i++ ){
if( change >= DENOMS[i] ){
notes_needed += change / DENOMS[i];
change %= DENOMS[i];
}
}
}
Problem D: Usernames
The objective of this problem is straight forward. We have to go through the list of names and track every time a name is repeated. The challenge is how to maintain a unique count of usernames, and display the total number of unique names before printing the entire list of modified names.
It is always a good practice to ask the question: Is there any data structure that I can leverage?
For tracking a unique list of elements both a set and a map can be used in C++. Since the problem requires to track how many times a username has already been used, a map will be more desirable. Refer to Programming and Data Structure in C++ for a detailed explanation and examples on maps and sets.
Also, the problem requires us to print the total number of unique names before listing the modified names. This suggests that we will have to store the list of modified names somewhere before printing them. There are several ways to accomplish this in C++, here we shall use a string stream.
// Get the total count of usernames
int N;
cin >> N;
stringstream output; // Stores modified names
map<string, int> uniqueNames; // Tracks unique names and how many times they are used
string name;
// Process the list of names
while( N-- ){
cin >> name;
uniqueNames[name]; // Add the name with a count of zero if it's not in the list
if( uniqueNames[name] == 0 ){ // First time to encounter the name
output << name << endl;
uniqueNames[name] = 1;
}else{ // The name has already been used
output << name << ++uniqueNames[name] << endl;
}
}
// Display the results
cout << uniqueNames.size() << endl;
cout << output.str();Code language: PHP (php)Problem E: Mike’s Puzzle
The objective of problem E is to trace a path from the top left corner to the bottom left corner while counting the number of visited cells and the direction changes made.
The problem makes this easier since it has guaranteed that the path has neither loops nor branches. This means there is only a single path between the top left and bottom right corner.
This is an example of a simulation problem. As Jonathan described below when answering the question “What does it mean by ‘simulation type problem’ in competitive programming?” in Quora:
It means that the main difficulty in the problem is not figuring out how to solve it conceptually, but instead writing code that follows the (usually complex) set of rules they tell you. The challenge is writing this code quickly and accurately. It is called a “simulation” problem because your code is simulating whatever situation is described in the problem. Source
Jonathan Paulson in Quora
Clearly an array will be a great data structure to use (specifically, an N by N array where N refers to the provided size of the grid). Then, we can fill the array with the ones and zeros.
Before we can start to navigate through the array, we need a way of marking the cells that we have already visited. Since we need to visit the grid only once, we can clear the cell (i.e. change the one to zero) once we visit it. This will simplify tracking the visited cells.
// Get the grid size
int N;
cin >> N;
// Construct and fill in the grid
int grid[N][N];
for(int x = 0; x < N; x++)
for(int y = 0; y < N; y++)
cin >> grid[x][y];
int dirChange = 0; // Track how many times direction changes
int tiles = 1; // Count how many tiles were touched
enum { NOT_SET, UP, DOWN, RIGHT, LEFT } dir = NOT_SET; // Define and track the direction
// Walk through the grid starting from the top left corner
int x = 0, y = 0; // Current position
while( x != N-1 || y != N-1 ) { // Stop when reaching the bottom right (N-1, N-1)
if( x+1 < N && grid[x+1][y] ){ // Check if can go down
grid[++x][y] = 0; // Clear the tile from the path
if( dir != NOT_SET && dir != DOWN ) dirChange++; // Track if direction changed
dir = DOWN; // Assign the current direction
}else if( x-1 >= 0 && grid[x-1][y] ){ // Check if can go up
grid[--x][y] = 0; // Clear the tile from the path
if( dir != NOT_SET && dir != UP ) dirChange++; // Track if direction changed
dir = UP; // Assign the current direction
}else if( y+1 < N && grid[x][y+1] ){ // Check if can go right
grid[x][++y] = 0; // Clear the tile from the path
if( dir != NOT_SET && dir != RIGHT ) dirChange++; // Track if direction changed
dir = RIGHT; // Assign the current direction
}else if( y-1 >= 0 && grid[x][y-1] ){ // Check if can go left
grid[x][--y] = 0; // Clear the tile from the path
if( dir != NOT_SET && dir != LEFT ) dirChange++; // Track if direction changed
dir = LEFT; // Assign the current direction
}
tiles++; // Increment visited tiles
}
cout << tiles - dirChange << endl;Code language: JavaScript (javascript)