Installing albert on ubuntu 19.04

Installing Albert on Ubuntu 19.04...

Albert is not still released for ubuntu 19.04. But still, you can install it using the following commands.

curl https://build.opensuse.org/projects/home:manuelschneid3r/public_key | sudo apt-key add -
echo 'deb http://download.opensuse.org/repositories/home:/manuelschneid3r/xUbuntu_19.04/ /' | sudo tee /etc/apt/sources.list.d/home:manuelschneid3r.list
apt update
apt install albert

After installing Albert, run it and set the settings as per your wish.

If you are using Wayland. Than the hotkey most probably won't work. In that case, go to settings, then in devices, keyboards, shortcuts, and add one shortcut with the command: "albert show"

Now close settings. And press your set shortcut and you are done.

Tips for applying Back Tracking or Complete Search.

Tips

Suppose that your Complete Search takes ~10 Seconds on worst-case and TL is 10 Seconds, and the judge gives TLE, then you should tweak the code instead of designing a new algorithm.

Tip 1: Filtering versus Generating:

Programs that examine lots of(if not all) candidate solutions and choose the ones that are correct are called filters.

Programs that build the solutions and prune out invalid partial solutions -> generators.

Usually, 'generator' programs are easier to implement when written recursively as it gives us greater flexibility for pruning the search space...

Tip 2: Prune Infeasible?Inferior Search Space Early

Most often, we may encounter a partial solution that will never lear to a full solution. We can keep a note of it and prune the search space there and explore other parts of the search space. As a rule of thumb, the earlier you can prune the search space, the better.

Tip 3: Utilize Symmetries

Some problems have symmetries, and this can be taken advantage of.

In Cp, this is usually not the best way (we want to minimize the bugs). If the gain obtained by dealing with symmetry is not significant in solving the problem, just ignore this tip.

Tip 4: Pre-Computation a.k.a. Pre-Calculation

Sometimes it is helpful to generate tables or other DS that accelerate the lookup of a result prior to the execution of the program itself. This is called Pre-Computation.

Tip 5: Optimizing your source code

1. Use C++ instead of Java. C++ gets implemented faster in C++ than in Java. Few judges give Java users extra time for this lag though.

2. User scanf/printf rather than cin/cout.

3. Access a 2D array in a row-major fashion(row by row) rather than in a column-major fashion. Multidimensional arrays are stored in row-major order in memory.

4. Bit manipulation on the built-in integer data types is more efficient than index manipulation in an array of booleans. If we need more than 64 bits, use the C++ STL bitset rather than vector<bool>.

5. Preer arrays over vectors if memory is not an issue. 

8. Declare most data structures(especially the bulky ones) by placing them in the global scope. And clear it as and when needed.

9. If there is an option to write code iteratively or recursively, choose the iterative version.

10. Array access costs. If you need to access A[i] many times, it may be good to store it in temp=A[i] and work with it instead.

11. Use macros or inline functions.

12. C-style character arrays are faster than string.

Tip 7:

Using better DS and Algo will beat all other tips.

Disclaimer: All my notes are based on the Competetive Programming 3 book.

Brute Force/Complete Search/ recursive backtracking: the eight queens example

Back Tracking or Brute Force

I stopped writing for a few days, but now I am back. So let us get the job started.

In Brute force, we traverse the entire search space.

In a programming competition, a contestant should keep brute force as his last option.

I found this example interesting:

Statement:

In chess (with an 8 × 8 board), it is possible to place eight

queens on the board such that no two queens attack each other. Determine all such possible

arrangements given the position of one of the queens (i.e. coordinate (a, b) must contain a

queen). Output the possibilities in a lexicographical (sorted) order.

The most naive solution:

Enumerate all combinations of 8 different cells out of 8*8=64 possible cells, this is $^6^4C8$ ~ 4B, thus it is not even worth trying.

Better but naive solution:

Each queen can only occupy one column, so we can put exactly one queen in each column. There are $8^8$ possibilities now. (8*8*...) ~17M

Better:

No two queen can share the same column or the same row. This makes it an 8!~40K problem. This will get accepted.

Yet Better:

They can't even share the same diagonal. This makes it far less than 8! And we will be able to easily make it.

Implementation:

This tutorial is based on CP3 book, so is my code:

#include <bits.stdc++.h>
	using namespace std;
	int row[8];
	bool place(int r, int c){
	for (int prev = 0; prev < c; prev++) // check previously placed queens
	if (row[prev] == r || (abs(row[prev] - r) == abs(prev - c)))
	return false; // share same row or same diagonal -> infeasible
	return true;
	}
	void backtrack(int c){
	if(c==8&&row[b]==a){
	for (int j = 1; j < 8; j++) printf(" %d", row[j] + 1);
	printf("\n");
	}
	for(int r=0;r<8;r++){
	if(canPlace(r, c)){
	row[c] = r;
	backtrack(c+1);
	}
	}//iterating for all rows in this column
	}
	int main(int argc, char const *argv[]) {
	int T;
	cin>>T;
	while (T--) {
	int a, b;
	a--; b--;
	memset(chess, 0, sizeof(chess));
	printf("SOLN COLUMN\n");
	backtrack(0);
	}
	return 0;
	}

Union-Find Disjoint Sets Practice questions.

Practice Questions

Here are the questions you can do to practice Union-Find Disjoint Sets.

1. UVa 00793 - Network Connections *

2. UVa 01197 - The Suspects

3. UVa 10158 - War

4. UVa 10227 - Forests

5. UVa 10507 - Waking up brain 

6. UVa 10583 - Ubiquitous Religions

7. UVa 10608 - Friends

8. UVa 10685 - Nature

9. UVa 11503 - Virtual Friends

10. UVa 11690 - Money Matters

Here is the link to the set of questions: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=636

Here are my solutions and hints to some of these problems:

Hints and solutions

We are using the implementation we discussed previously. Here I am sharing it again:

class UnionFind{
	private: vector<int> p, rank;
	public:
	UnionFind(int N){//N is the number of elements
	rank.assign(N, 0);//////create n nodes assign 0 to each
	p.assign(N,0);
	for(int i=0;i<N;i++)
	p[i]=i;
	}
	int findSet(int i){
	return (p[i]==i)?i: (p[i]=findSet(p[i])); //also doing the path compression simultaneously
	}
	bool isSameSet(int i, int j){
	return findSet(i)==findSet(j);
	}
	void unionSet(int i, int j){
	if(!isSameSet(i,j)){
	int x=findSet(i), y=findSet(j);
	if(rank[x]>rank[y])
	p[y]=x;
	else{
	p[x]=y;
	if(rank[x]==rank[y])
	rank[y]++;
	}
	}
	}
	int numDisjointSets(){
	set<int> set;
	for(int i=0;i<p.size();i++){
	int a=p[i];
	set.insert(findSet(a));
	}
	return set.size();
	}
	int sizeOfSet(int i){
	int t = findSet(i);
	int count=0;
	for(int i=0;i<p.size();i++){
	int a = p[i];
	if(t==findSet(a)){
	count++;
	}
	}
	return count;
	}
	};

All the problems in this category are very similar. You are given what points are connected and are either asked if two points are connected or similar such questions.

Uva 00793. Network Connections

int main(int argc, char const *argv[]) {
	int t;
	scanf("%d", &t);
	int temp=1;
	while (t--) {
	int numberofComp;
	scanf("\n%d\n", &numberofComp);
	UnionFind uf(numberofComp);
	char ch;
	int a, b;
	int successfulanswers=0;
	int failure=0;
	string s;
	while (1) {
	if(!getline(cin, s)||s.empty())
	break;
	sscanf(s.c_str(), "%c %d %d", &ch, &a, &b);
	if(ch=='c')
	uf.unionSet(a-1, b-1);
	if(ch=='q'){
	if(uf.isSameSet(a-1, b-1))
	successfulanswers++;
	else
	failure++;
	}
	}
	if(temp!=1)
	cout<<endl;
	cout<<successfulanswers<<','<<failure<<endl;
	temp++;
	}
	return 0;
	}

Uva 10608 Friends

int main(int argc, char const *argv[]) {
	int T;
	scanf("%d", &T);
	while (T--) {
	int N, M;
	scanf("%d %d", &N, &M);
	UnionFind uf(N);
	while (M--) {
	int a, b;
	scanf("%d %d", &a, &b);
	uf.unionSet(a-1, b-1);
	}
	std::vector<int> arr;
	arr.assign(N, 0);
	for (size_t i = 0; i < N; i++) {
	arr[uf.findSet(i)]++;
	}
	sort(arr.begin(), arr.end());
	cout<<arr[N-1]<<endl;
	}
	return 0;
	}

Uva 0583 Ubiquitous Religions

int main(int argc, char const *argv[]) {
	int k=1;
	while(true){
	int n, m;
	scanf("%d %d", &n, &m);
	if(n==0&&m==0)
	break;
	UnionFind uf(n);
	while(m--){
	int a, b;
	scanf("%d %d", &a, &b);
	uf.unionSet(a-1, b-1);
	}
	printf("Case %d: %d\n", k++, uf.numDisjointSets());
	}
	return 0;
	}