Stream#headOption

A stream is basically a lazy evaluated list, it only evaluates the element when it’s asked.

Given a stream of elements of type A and some helper functions.
Implement how to get Some of the first(head) element if it exists or None if it doesn’t exist.

Implement headOption first to have an idea how you might implement headOptionWithFold

The basic idea is we want to evaluate the first element only and avoid evaluating the rest of the list.

List[A] traverse with Either[+E, +A]

Given a list of elements of type A and a function from A to Either[E, B].
Write a function traverse with this signature

def traverse[E, A, B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]]

If applying function f on any of the elements of the list results in Left the function should return Left, otherwise it should return a Right with a list of all the B values.

Solution
For the purpose of the implementation we need to implement functions map and flatMap for Either

Then the implementation of the function is fairly easy, similar to the implementation with Option

Example

The difference between Either and Option is that here if an Exception occurred it will be saved in the Left value of the Either while in the Option it will be just None value with no indication of what really happened.

List[A] traverse with Option[B]!

Given a list of elements of type A and a function from A to Option[B].
Write a function traverse with this signature

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]]

If applying function f on any of the elements of the list results in None the function should return None, otherwise it should return a Some with all the B values.

Solution

This can be useful in cases like this.

ماتسبش نفسك تقع

C++ references, because pointers are overrated

Muhamad Hesham's T-Blog

I read some day in some C++ book a quote: “References are the sweets of C++”. I can almost swear that this quote belongs to Bjarne Stroustrup as my weak memory remembers, but I have no evidence. This quote is the motivation behind this blog post.

GOALS

• Shed the light on C++ references beauty
• Suggest a Do/Don’t guidelines and good practices for using references
• Indirectly begging you not to use pointers everywhere to look geek

NON-GOALS

• Another cplusplus.com tutorial on references or pointers
• Another stackoverflow question in the regex form of: * Pointers * References *?
• Illustrate how dumb is writing using namespace in header files

TO KNOW

References and Pointers have exact dereference and member function call assembly

In case you thought that one has performance advantage over the other, they only differ in semantics

Pointers inheritance/polymorphism rules apply

DO

Pass Out and In/Out parameters by reference and…

View original post 493 more words

11280 – Flying to Fredericton

Problem Statement

All it needs is a slight modification in the Bellman ford algorithm.

#include <bits/stdc++.h>
using namespace std;

struct io {
	template<class T>
	static inline T next() {
		T x; std::cin >> x;
		return x;
	}
};

const int M = 105;
const int INF = numeric_limits<int>::max() / 10;

int cost[M][M];
int dp[M][M];

void process(const vector<vector<int>>& g) {
	const int n = g.size();
	for (int i = 0; i < n; ++i)
		dp[i][0] = 0;

	for (int it = 1; it <= n; ++it)
		for (int v = 1; v < n; ++v) {
			dp[it][v] = dp[it - 1][v];
			for (int e : g[v]) {
				dp[it][v] = min(dp[it][v], dp[it - 1][e] + cost[v][e]);
			}
		}
}

int main(int argc, char** args) {
	int T = io::next<int>();
	for (int t = 1; T-- > 0; ++t) {
		if (t > 1) cout << endl;

		unordered_map<string, int> index;
		const int cities = io::next<int>();
		for (int i = 0; i < cities; ++i) {
			index[io::next<string>()] = cities - i - 1;
		}

		for (int i = 0; i < cities; ++i)
			for (int j = 0; j < cities; ++j) {
				cost[i][j] = INF;
				dp[i][j] = INF;
			}

		vector<vector<int>> g(cities);
		int roads = io::next<int>();
		while (roads-- > 0) {
			const int a = index[io::next<string>()];
			const int b = index[io::next<string>()];
			g[a].push_back(b);
			cost[a][b] = min(cost[a][b], io::next<int>());
		}

		process(g);

		cout << "Scenario #" << t << endl;
		for (int queries = io::next<int>(); queries-- > 0; ) {
			const int stopovers = io::next<int>() % cities;
			const int result = dp[stopovers + 1][cities - 1];
			if (result == INF)
				cout << "No satisfactory flights" << endl;
			else
				cout << "Total cost of flight(s) is $" << result << endl;
		}
	}
}

1253 – Infected Land

Problem Statement

“The area where the vehicle is in, which is uninfected, has the same effect to its adjacent areas as an infected area as far as the transition rules are concerned.”
This line from the problem statement made the problem a lot easier to implement.

Breadth First Search practice problem.
state = { x, y, cost, grid };
You can use a string or an integer as a mask to represent the grid.

#include <bits/stdc++.h>
using namespace std;

struct io {
	template<class T>
	static inline T next() {
		T x; std::cin >> x;
		return x;
	}
};

const int dx[] = { -1, 1, -1, 1, 0, 0, 1, -1 };
const int dy[] = { 1, -1, -1, 1, -1, 1, 0, 0 };

struct state {
	int x, y;
	int c;
	int grid;

	state() { }

	state(int x, int y, int c, int g)
		: x(x), y(y), c(c), grid(g) { }
};

inline bool ok(const int x, const int y, const int n) {
	return x >= 0 && x < n && y >= 0 && y < n;
}

inline int index(const int i, const int j, const int n) {
	return i * n + j;
}

template<typename Fun>
void for_each_adjacent(const int i, const int j, const int n, Fun f) {
	for (int d = 0; d < 8; ++d) {
		const int nx = i + dx[d];
		const int ny = j + dy[d];
		if (ok(nx, ny, n)) f(nx, ny);
	}
}

int process(const int x, const int y, const int n, const int old_grid) {
	int grid = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			if (i == x && j == y)
				continue;

			int count = 0;
			const int bit = index(i, j, n);
			for_each_adjacent(i, j, n, [&](const int nx, const int ny) {
				if ((old_grid & (1 << index(nx, ny, n))) || (nx == x && ny == y))
					++count;
			});
			if (count == 3)
				grid |= (1 << bit);
			else if (count == 2 && (old_grid & (1 << bit)))
				grid |= (1 << bit);
		}
	return grid;
}

int solve(const int sx, const int sy, const int src, const int trg, const int n) {
	set<tuple<int, int, int>> visited;
	visited.insert(make_tuple(sx, sy, src));

	queue<state> q;
	for (q.push(state(sx, sy, 0, src)); !q.empty(); q.pop()) {
		const state s = q.front();
		if (s.grid == trg)
			return s.c;
		for_each_adjacent(s.x, s.y, n, [&](const int x, const int y) {
			if (s.grid & (1 << index(x, y, n)))
				return;
			const int grid = process(x, y, n, s.grid);
			const tuple<int, int, int> next = make_tuple(x, y, grid);
			if (visited.find(next) == visited.end()) {
				visited.insert(next);
				q.push(state(x, y, s.c + 1, grid));
			}
		});
	}
	return -1;
}

int main(int argc, char** args) {
	for (int n; cin >> n && n; ) {
		int grid = 0;
		int x, y;
		for (int i = 0; i < n; ++i) {
			const string s = io::next<string>();
			for (int j = 0; j < n; ++j) {
				if (s[j] == '@')
					tie(x, y) = make_pair(i, j);
				else if (s[j] == '#')
					grid |= (1 << index(i, j, n));
			}
		}
		cout << solve(x, y, grid, 0, n) << endl;
	}
	return 0;
}

12444 – Bits and Pieces

Problem Statement

You’ll have to build the result { a, b }, for each bit in { c, d } you have three options:
1 – both bits are one, then sit the bits in { a, b } with one.
2 – the c bit is one and the d bit is zero, here you will return -1, because if the c bit is one, this means that
the current bit in a and b must be one.
3 – the c bit is zero and the d bit is one, if the it is the first occurrence for this case, sit the b with one,
else sit a with one.

#include <bits/stdc++.h>
using namespace std;

struct io {
	template<class T>
	static inline T next() {
		T x; std::cin >> x;
		return x;
	}
};

ostream& operator << (ostream& sout, const pair<int, int>& p) {
	if (p.first == -1 || p.second == -1)
		sout << -1;
	else
		sout << p.first << " " << p.second;
	return sout;
}

pair<int, int> solve(const int c, const int d) {
	int a = 0;
	int b = 0;
	bool first = true;
	for (int i = 31; i >= 0; --i) {
		const bool C = (c & (1 << i)) != 0;
		const bool D = (d & (1 << i)) != 0;

		if (C && D) {
			a |= (1 << i);
			b |= (1 << i);
		} else if (!C && !D) {
		} else if (C && !D) {
			return { -1, -1 };
		} else {
			if (first)
				b |= (1 << i);
			else
				a |= (1 << i);
			first = false;
		}
	}
	return { a, b };
}

int main(int argc, char** args) {
	for (int T = io::next<int>(); T-- > 0; ) {
		const int c = io::next<int>();
		const int d = io::next<int>();
		cout << solve(c, d) << endl;
	}
	return 0;
}

12086 – Potentiometers

Problem Statement

#include <bits/stdc++.h>
using namespace std;

struct io {
	template<class T>
	static inline T next() {
		T x; std::cin >> x;
		return x;
	}

	template<class T>
	static inline std::vector<T> next_array(const int n) {
		std::vector<T> row(n);
		for (int i = 0; i < n; ++i)
			row[i] = io::next<T>();
		return row;
	}
};

template<typename T = int, typename Op = std::plus<T>>
class fenwick_tree {
private:
	T identity;
	Op op;
	std::vector<T> tree;

public:
	explicit fenwick_tree(int size = 0, Op op = Op(), T identity = T())
		: tree(size + 1, identity), op(op), identity(identity) { }

	int size() const {
		return tree.size();
	}

	void update(int idx, const T delta) {
		while (idx < size()) {
			tree[idx] = op(tree[idx], delta);
			idx += (idx & -idx);
		}
	}

	T sum(int idx) const {
		T result = identity;
		while (idx > 0) {
			result += tree[idx];
			idx -= (idx & -idx);
		}
		return result;
	}

	T sum(const int a, const int b) const {
		return sum(b) - (a == 1 ? 0 : sum(a - 1));
	}

	T sum_exclusive(int idx) const {
		return idx == 0 ? identity : sum(idx - 1);
	}
};

int main(int argc, char** args) {
	for (int n, T = 1; cin >> n && n > 0; ++T) {
		vector<int> data = io::next_array<int>(n);

		fenwick_tree<> tree(n);
		for (int i = 0; i < n; ++i)
			tree.update(i + 1, data[i]);

		if (T > 1)
			cout << endl;

		cout << "Case " << T << ":" << endl;
		for (string command = io::next<string>(); command != "END"; command = io::next<string>()) {
			const int a = io::next<int>();
			const int b = io::next<int>();
			if (command == "M") {
				cout << tree.sum(a, b) << endl;
			} else if (command == "S") {
				tree.update(a, -data[a - 1]);
				tree.update(a, b);
				data[a - 1] = b;
			}
		}
	}
	return 0;
}

12532 – Interval Product

Problem Statement

Just use Segment tree.

#include <bits/stdc++.h>
using namespace std;

struct io {
	template<class T>
	static inline T next() {
		T x; std::cin >> x;
		return x;
	}

	template<class T, typename Fun>
	static inline T next(Fun f) {
		T x; std::cin >> x;
		return f(x);
	}

	template<class T>
	static inline std::vector<T> next_array(const int n) {
		std::vector<T> row(n);
		for (int i = 0; i < n; ++i)
			row[i] = io::next<T>();
		return row;
	}

	template<class T, typename Fun>
	static inline std::vector<T> next_array(const int n, Fun f) {
		std::vector<T> row(n);
		for (int i = 0; i < n; ++i)
			row[i] = io::next<T>(f);
		return row;
	}
};

int normalize(const int v) {
	if (v > 0) return 1;
	if (v < 0) return -1;
	return 0;
}

struct node {
	int b, e, m, p;
};

class segment_tree {
private:
	vector<node> tree;
	vector<int> data;

public:
	segment_tree(const vector<int>& values) {
		data = values;
		const int size = values.size();
		tree = vector<node>(size << 2);
		init(0, 0, size - 1);
	}

	void update_value(const int index, const int value) {
		update_value(0, index, value);
	}

	int get_product(const int b, const int e) {
		return get_product(0, b, e);
	}

private:
	int l(const int x) {
		return 2 * x + 1;
	}

	int r(const int x) {
		return 2 * x + 2;
	}

	void collect(const int root) {
		tree[root].p = tree[l(root)].p * tree[r(root)].p;
	}

	void set_base_value(const int root, const int i) {
		tree[root].p = data[i];
	}

	void init(const int root, const int b, const int e) {
		node& n = tree[root];
		n.b = b, n.e = e;
		n.m = (b + e) >> 1;
		if (b != e) {
			init(l(root), n.b, n.m);
			init(r(root), n.m + 1, n.e);
			collect(root);
		} else {
			set_base_value(root, n.b);
		}
	}

	void update_value(const int root, const int index, const int value) {
		node& n = tree[root];
		if (n.b == n.e) {
			data[n.b] = value;
			set_base_value(root, n.b);
		} else {
			if (index <= n.m)
				update_value(l(root), index, value);
			else
				update_value(r(root), index, value);
			collect(root);
		}
	}

	int get_product(const int root, const int b, const int e) {
		node& n = tree[root];
		if (n.b > e || n.e < b)
			return 1;
		if (n.b >= b && n.e <= e)
			return n.p;
		return get_product(l(root), b, e) * get_product(r(root), b, e);
	}
};

int main(int argc, char** args) {
	for (int n, q; cin >> n >> q; cout << endl) {
		vector<int> values = io::next_array<int>(n, normalize);
		segment_tree tree(values);
		while (q-- > 0) {
			const char command = io::next<char>();
			if (command == 'C') {
				const int i = io::next<int>() - 1;
				const int v = io::next<int>(normalize);
				tree.update_value(i, v);
			} else {
				const int b = io::next<int>() - 1;
				const int e = io::next<int>() - 1;
				const int result = tree.get_product(b, e);
				cout << (result < 0 ? "-" : result > 0 ? "+" : "0");
			}
		}
	}
	return 0;
}