Setting Up Vscode for Single-file C++ Builds

So I have these self-contained C++ files and with a shortcut key I want to automatically build and run active file, and then use a debugger as well if I want to. Who would want to do this? Either you are just learning the language and want a quick way to prototype, or you are doing competitive programming (UVa, Codeforces, etc). The latter reason is why I’m writing this; me and my colleagues just started an “Algo Party” where we gather together to solve coding puzzles.

I’ve only tested this on osx and linux, but if you are using MinGW and you have GDB installed it should work.

Build and Run Any Random C++ File

When you open any C++ file, vscode is smart enough to suggest a bunch of extensions you should install. But after installing them you will realize that you can’t just run immediately start running hello world from your editor. To run the file in your active editor, install Code Runner.

Now you can run the active file with the shortcut cmd+alt+n or ctrl+alt+n. There are some nice settings to have, like running in terminal, saving the file before run, and that juicy C++14 goodness. You can configure them via extension settings:

"code-runner.runInTerminal": true,
"code-runner.saveFileBeforeRun": true,
"code-runner.executorMap": {
    // ...leave as is
    "cpp": "cd $dir && g++ $fileName -std=c++14 -o $fileNameWithoutExt && $dir$fileNameWithoutExt && echo ''",
    // ...leave as is
}

Note that echo '' is just to print a new line after running the program. If you know you will always execute the program with an input file, simply add <input.txt to the command above (before && echo '').

Press Ctrl+Alt+n to build and run the active file

Now if that’s all you want then you can stop here. The next section let’s you use a debugger, but requires a different setup.

Using Vscode Tasks To Build The Active File

This one is a project level configuration, so it assumes you keep your C++ files in one folder, like how I organize my solutions to my CodeForces problems in this git repository. To get started you can simply copy the json files from my .vscode folder over to yours.

Now on any C++ file in that project, simply hit cmd+shift+b to build the file. In addition to building the file, I’ve also added a -g argument to the compiler to build debugging symbols as well. You can remove this by tweaking the tasks.json. The file itself is fairly straightforward to understand. I already have a task to both build and run the file at once called “build and run cpp” (I always run my solutions with a file “input.txt”; if that’s not what you want you can simply tweak the command).

You can assign this to a shortcut key by going to File > Preferences > Keyboard Shortcuts and click the link in the message “For advanced customizations open and edit keybindings.json”. There you can assign the task to a shortcut you want (I use ctrl+9):

    {
        "key": "ctrl+9",
        "command": "workbench.action.tasks.runTask",
        "args": "build and run cpp"
    }

Build and run the active file using vscode tasks

Setting Up The Debugger

Hit f5 (or click the green arrow if you are in debug mode) to launch the debugger. This will launch an external terminal instead of using the integrated one.

Using the debugger in vscode

If you don’t use an input file then all is good, otherwise it is a hassle to constantly keying in inputs into the program. Unfortunately for us we can’t pass in the input file as an argument where the debugger is concerned (at least, for now).

Fortunately there is a simple workaround.

In STL, both the console input and file input are input streams. So what we can do is override cin to replace it with an ifstream. Because of the scope, our custom version will always take precedence:

#include <iostream>
#include <fstream> // std::ifstream

using namespace std;

int main()
{
    ifstream cin('input.txt'); // replace cin with our version

    // rest of the code remains the same:
    int p, q;
    cin >> p >> q;
}

Don’t forget to comment out that custom cin before you submit your solution to the online judge!

Advertisements

445A – Boredom – CodeForces Tutorial

Inasmuch as this is a CodeForces tutorial, I’d also want to use Boredom as an introduction to dynamic programming (dp). I will also compare the dp solution to its alternate recursive implementation. This tutorial also caters to people who can’t seem to wrap their head around the solution or tutorial from CodeForces.

I won’t be explaining the problem itself. Should be pretty straightforward.

Gotchas

The maximum points can exceed the limit for the 32-bit data type int. In some of the test cases that value can be as high as 9999899998 (the maximum capacity for 32-bit int is 2147483647). The maximum value for the n integers may be up to 10^5, but they can total up to a lot higher than that.

That is why you will see C/C++ solutions out there the data type long long int:

typedef long long int bigInt;

Solution Overview

You can try to understand the succinct tutorial from CodeForces, if you haven’t already looked into it.

The sequence of n numbers needed to be grouped together and kept count, because when selecting a single number, it makes sense to repeatedly select it (thereby adding it to your points) until it doesn’t exist in the sequence. We will keep track of this count in array c, where c[i] contains the number of occurrences of i.

Let f be a function that calculates the maximum number of points to a value up to i. Now there will be 2 base cases:

  1. If i = 0, then f(0) = 0
  2. If i = 1, then f(0) = c[1]

I hope the 2nd point is clear. Up to 1 the maximum number of points you can get by selecting 1 is the number of occurrences of 1 in the array c.

When i >= 2, you have 2 choices in deciding which will be f(i):

  1. Select f(– 2), in which you can also add with i * c[i].
  2. Select f(i – 1), but in doing so you can’t choose to add i * c[i] because of the condition that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence.

Choosing between 1 and 2 is as simple as choosing which is largest.

Now let m be the largest number in the sequence. The solution is therefore f(m). The CodeForces tutorial writes f(n), but I doubt n here implies the number of elements in the sequence. To avoid confusion, I used m instead.

Most implementations I see online simply put f(100000).

It helps that you trace the algorithm step by step on paper, should it not be apparent to you how it works. For example for input:

10
10 5 8 9 5 6 8 7 2 8

You can track the values of i, c[i], and f(i):

i    c[i]   i*c[i]   f(i)
0    0      0        0
1    0      0        0
2    1      2        2
3    0      0        2
4    0      0        2
5    2      10       12
6    1      6        12
7    1      7        19
8    3      24       36
9    1      9        36
10   1      10       46

Do not undermine this method; learning how to trace algorithms in a systematic way can be very helpful to help you understand it.

Recursive Implementation

Based on the solution as detailed above, here the recursive implementation.

#include <algorithm>
#include <iostream>
#include <vector>

typedef long long int bigInt;

using namespace std;

vector<bigInt>  c(100001, 0);

bigInt f(const int i)
{
	if (i == 0) return 0;
	if (i == 1) return c[1];

	return max(f(i - 1), f(i - 2) + i*c[i]);
}

int main() 
{
	int n, x, m = 0;
	cin >> n;

	while(n--) {
		cin >> x;
		c[x]++;
		m = max(m, x);
	}

	cout << f(m);
}

Don’t submit this solution; it will fail at test 9 (time limit exceeded).

That’s it! In 30 lines of code you can solve this problem! The issue? Well, try and increase the values in the sequence (not the number of elements in the sequence. This doesn’t affect the growth of the function). Even a value as small as 30 and I had to wait a few seconds for it to compute.

Analysis of Recursive Implementation

We can define the performance of this recursive implementation by the number of recursive calls.

Let us trace the recursive calls of the function f in a recursion tree. I used paler colors to signify the depth of the recursion tree; the deeper it gets, the paler it gets:

Recursion tree of function f

That is a total of 9 recursive calls. How about f(5)?

recursion tree- f(5)

5+9+1 (including itself) = 15 function calls.

If you observe for awhile, you will be able to deduce a pattern. Let q be a function that finds the number of function calls for f given i. Then we write q as: q(i)=q(i-1) + q(i-2) + 1, for all i >= 2; q(0)=1; q(1)=1. If you plot this function as a graph, you will get this:

exponenetial graph

So time complexity is O(2^n); Implementation scales exponentially.

By the time i reaches 18, q(18) = 8361. When i = 30, the number of function calls becomes 2692537! This would explain that bit of lag earlier. Just imagine i going as big as 10000. It is no surprise then, that when this happens, the program crashes due to stack overflow:

stack overflow!

Dynamic Programming Implementation

Dynamic programming, in essence, is an optimization technique that dramatically cuts down computational time but taking out a bit of space to store calculated answers to overlapping subproblems. The overlapping subproblems here are the calls to f, which for example in the recursion tree f(4) we can see that f(1) is called 3 times and f(2) and f(0) is called 2 times.

Furthermore, we can take the solutions the subproblems to compute the solution of the main problem. For example f(5) can be determined by f(4) and f(3), and f(4) can be determined by f(3) and f(2), and so on. This property is called Optimal Substructure.

To recap, the 2 properties that must exist for a problem to be made solvable by dp:

Let’s put theory to practice.

We can reduce the time complexity from O(2^n) to O(n) by keeping an array DP of the same size as cDP will store the calculated values of f for all i. The solution, therefore, is DP[m], since it contains f(m). Below is the dynamic programming solution:

#include <algorithm>
#include <iostream>
#include <vector>

typedef long long int bigInt;

using namespace std;

int main() 
{
	const int MAX_N = 100001;

	int n, x;
	vector<bigInt> dp(MAX_N, 0);
	vector<bigInt>  c(MAX_N, 0);

	cin >> n;

	while(n--) {
		cin >> x;
		c[x]++;
	}

	dp[0] = 0;
	dp[1] = c[1];

	for (int i = 2; i < MAX_N; i++) {
		dp[i] = max(dp[i - 1], dp[i - 2] + i*c[i]);
	}

	cout << dp[MAX_N - 1];
}

In the dp solution, f(i) is computed from 0 to 10000 (bottom to top), whereas in the recursive solution f(i) is computed from m to 0 (top to bottom).

Notice I didn’t bother keep track the largest value in the sequence (variable m). You can have that bit of optimization if you use it, but it isn’t necessary for this problem. In essence we have f (the block of code inside that for loop) called a constant 10000 times each time this program is called, and this works granted the largest value in the sequence doesn’t exceed 10000.

What is fascinating about this implementation is that it solves the problem with the same amount of code! Ladies and gentlemen, the power of algorithms!

References

510C – Fox And Names – CodeForces Tutorial

Understanding the Problem

Given a list of words, modify the order of the alphabets such that the words are sorted in lexicographical (alphabetical) order. We compare based on the left most position of the each word, but should there not exist one (i.e. “care” and “careful”) the shortest short is the lesser. This meant that if there is a sequence like “aaaaaaa” preceding “aaa”, it is invalid.

To help better understand this problem, I created a small program that assigns a value of 0 to 25 to the alphabetical sequence given and outputs the values bellow a word. Bellow is a sample run of one of the given pretests using the default alphabetical sequence:

$ ./permTester abcdefghijklmnopqrstuvwxyz < input1.txt
car
2 0 17
care
2 0 17 4
careful
2 0 17 4 5 20 11
carefully
2 0 17 4 5 20 11 11 24
becarefuldontforgetsomething
1 4 2 0 17 4 5 20 11 3 14 13 19 5 14 17 6 4 19 18 14 12 4 19 7 8 13 6
otherwiseyouwillbehacked
14 19 7 4 17 22 8 18 4 24 14 20 22 8 11 11 1 4 7 0 2 10 4 3
goodluck
6 14 14 3 11 20 2 10

Now with a sequence that puts the list of words in lexicographic order:

$ ./permTester acbdefhijklmnogpqrstuvwxyz < input1.txt
car
1 0 17
care
1 0 17 4
careful
1 0 17 4 5 20 10
carefully
1 0 17 4 5 20 10 10 24
becarefuldontforgetsomething
2 4 1 0 17 4 5 20 10 3 13 12 19 5 13 17 14 4 19 18 13 11 4 19 6 7 12 14
otherwiseyouwillbehacked
13 19 6 4 17 22 7 18 4 24 13 20 22 7 10 10 2 4 6 0 1 9 4 3
goodluck
14 13 13 3 10 20 1 9

So now you should get an idea of what the question wants.

Explaining the Solution

NOTE: If you have no knowledge about graph theory, check out Algorithms by Robert Sedgewick and Kevin Wayne. In addition to the book, they have a website and a Coursera online course (Graphs are in part II). The algorithms I will talk about references from this book. I refer it here as the Princeton Algorithms book.

So the main hint from the provided tutorial was:

It is actually the classic topological order question

You then model the question as a precedence-constrained scheduling problem. From the Princeton Algorithms book:

Given a set of jobs to be completed, with precedence constraints that specify that certain jobs have to be completed before certain jobs are begun, how can we schedule the jobs such that are all completed while still respecting the constraints?

Our “jobs” here are the alphabets a-z. For example, given a sequence of words “tourist”, “petr” and “wjmzbmr”, you will have a chain t->p->w. If there a sequence like “qac”, “qab” and “zab”, you will have 2 chains c->b and q->z. There can be many chains, and these chains can connect to each other. 

I usually have some print messages to assist in debugging my code. The part where it adds the precedence constraints (or edges) you can uncomment to see how it is making those decisions:

compare qac and qab
c precedes b
compare qab and zab
q precedes z

Detecting whether a sequence of words is “Impossible” is as simple as detecting whether there are any cycles in a directed graph, for example in the 2nd example input:

2015-10-26 13_34_43-Graph Creator

The cycles present are s->o->s and t->p->w->y->v->s->r->t. It is not important to find the cycles, just whether or not one exists. You can achieve this by tracing the nodes of every recursive call a node traverses in a DFS. If within a recursive call of a node it traverses itself, there is a cycle. Here is the code for cycle detection; you pass a DiGraph and you check the boolean hasCycle:

class DiCycle
{
public:
	DiCycle(const DiGraph &g) : hasCycle(false)
	{
		for (int i = 0; i < g.getSize(); ++i) {
			onStack.push_back(false);
			marked.push_back(false);
		}
		
		for (int i = 0; i < g.getSize(); ++i) {
			if (!marked[i] && !hasCycle) dfs(g, i);
		}
	}
	
	bool hasCycle;
	
private:
	void dfs(const DiGraph &g, const int &v)
	{
		if (hasCycle) return;
		
		onStack[v] = true;
		marked[v] = true;
		
		for (const auto &w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			} else if (onStack[w]) {
				hasCycle = true;
				return;
			}
		}
		
		onStack[v] = false;
	}
	
	vector<bool> onStack;
	vector<bool> marked;
};

The algorithm above traces the DFS using a vector of booleans onStack (recursion uses a stack internally), where the indices of the vector correspond to the graph nodes.

The DiGraph here used is an adjacency set.

Once you validate that the digraph has no cycles (or a DAG; Directed Acyclic Graph), the topological order is as simple as finding the reverse post order of the DAG:

class Topological 
{
public:
	Topological(const DiGraph &g)
	{
		for (int i = 0; i < g.getSize(); ++i) {
			marked.push_back(false);
		}
		
		for (int u = 0; u < g.getSize(); ++u) {
			if (!marked[u]) dfs(g, u);
		}
	}

	deque<char> order; // used as stack
	
private:
	void dfs(const DiGraph &g, const int &v)
	{
		marked[v] = true;
		
		for (const auto &w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			}
		}
		
		order.push_front(ALPHABETS[v]);
	}

	vector<bool> marked;
};

I used a deque here over the STL stack because stack doesn’t expose iterators for me to loop through. Also, stack actually uses a deque internally.

So, in the end we do DFS (Depth First Search) twice on the digraph; first pass to check for cycles, and second pass to get the topological order. Here’s the summary:

int main()
{
	DiGraph g(ALPHABETS.size());
	
	/** --code for adding edges removed for brevity-- **/
	
	DiCycle cycle(g);
	
	if (cycle.hasCycle) {
		cout << "Impossible";
		return 0;
	}
	
	Topological topo(g);
	
	for (const auto &c : topo.order) cout << c;
}

It may surprise you that the output tends to be in the reverse order of the alphabets (cause the alphabets are added in order to a stack), but rest assured it is still a valid answer.