I am trying to solve http://www.spoj.com/problems/GS . Here is my approach.

Let u, v denote the start and end vertices. [0 based index]

Let E[i] = expected number of roads to cross while going from vertex i to vertex v [0 <= i <= N-1]

Let preferred value of an edge (i, j) be P(i, j).

Now, from vertex i (other than vertex v), there are degree(i) possibilities.

Let the neighbors of i be i1, i2, ..., ik.

Thus, E[i] = [(1+E[i1])*P(i, i1) + ... + (1+E[ik])*P(i, ik)] / [P(i, i1) + ... + P(i, ik)]

For vertex v, E[v] = 0

So, we get a linear equation for each vertex. Overall, we get N equations with N unknowns, which can be solved by elimination.

However, I am getting Wrong Answer. I think there is a bug in my implementation of Gauss Jordan Elimination (this is the first time I am coding that). Can somebody help me?

Here is my code.

typedef long double db;
typedef vector<db> vd;
typedef vector<vd> vvd;
#define EPS 1e-9

db GaussJordan(vvd &A, vvd &b) {
	int N = A.size();
	assert(A[0].size() == N && b.size() == N);
	int M = b[0].size();
	db det = 1.0;
	for (int i = 0; i < N; i++) {
		if (fabs(A[i][i]) < EPS) {
			int j = i+1;
			for (; j < N; j++)
				if (fabs(A[j][i]) >= EPS)
					break;
			if (j == N)
			{
				assert(1 == 0);
				exit(-1);
			}
			for (int k = 0; k < N; k++)
				swap(A[i][k], A[j][k]);
			for (int k = 0; k < M; k++)
				swap(b[i][k], b[j][k]);
			det *= -1.0;
		}
		assert(fabs(A[i][i]) >= EPS);
		db pivot = A[i][i];
		det *= pivot;
		for (int k = 0; k < N; k++)
			A[i][k] /= pivot;
		for (int k = 0; k < M; k++)
			b[i][k] /= pivot;
		for (int j = i+1; j < N; j++) {
			db mul = A[j][i];
			for (int k = 0; k < N; k++)
				A[j][k] -= A[i][k]*mul;
			for (int k = 0; k < M; k++)
				b[j][k] -= b[i][k]*mul;
		}			
	}
	for (int i = N-1; i >= 0; i--) {
		for (int j = i-1; j >= 0; j--) {
			db mul = A[j][i];
			for (int k = 0; k < N; k++)
				A[j][k] -= A[i][k]*mul;
			for (int k = 0; k < M; k++)
				b[j][k] -= b[i][k]*mul;
		}
	}
	return det;
}

vector<pii> adj[20];

int main() {
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		int N, u, v;
		scanf("%d %d %d", &N, &u, &v);
		for (int i = 0; i < N-1; i++) {
			int x, y, p;
			scanf("%d %d %d", &x, &y, &p);
			adj[x-1].push_back(pii(y-1, p));
			adj[y-1].push_back(pii(x-1, p));
		}
		vvd A;
		vvd b;
		for (int i = 0; i < N; i++) {
			db tmp[N];
			for (int j = 0; j < N; j++)
				tmp[j] = 0.0;
			if (i == v-1)
			{
				tmp[i] = 1.0;
				A.push_back(vd(tmp, tmp+N));
				vd t;
				t.push_back(0.0);
				b.push_back(t);
				continue;
			}
			int sum = 0;
			for (int j = 0; j < adj[i].size(); j++)
				sum += adj[i][j].second;
			for (int j = 0; j < adj[i].size(); j++)
				tmp[adj[i][j].first] = -(db)adj[i][j].second/(db)sum;
			tmp[i] = 1.0;
			A.push_back(vd(tmp, tmp+N));
			vd t;
			t.push_back(1.0);
			b.push_back(t);
		}
		GaussJordan(A, b);
		printf("%.5lLf\n", b[u-1][0]);
	}
	return 0;
}

I am trying to solve AND Round http://www.spoj.com/problems/ANDROUND/

Problem Statement:

You are given a cyclic array A having N numbers. In an AND round, each element of the array A is replaced by the bitwise AND of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after K such AND rounds?

Here is my approach.

Let the original array be A[N] and the final array be C[N].

(1) If 2*K+1 >= N, then C[i] = bitwise AND of all elements of A, for all i.

(2) Otherwise, C[i] = bitwise AND of 2*K+1 elements of A (centered at index i) i.e.

C[i] = bitwise AND of (A[i-K], A[i-K+1],...,A[i-1], A[i], A[i+1],..., A[i+K-1], A[i+K]) where the indexes are circular.

To implement this, I have constructed another array B to handle the circularity. Let B = A'+A+A, where A' = reverse of A. Now, I have used a segment tree built on top of array B to compute the bitwise AND of a range of elements.

I am getting Wrong Answer. Is there anything fundamentally wrong in this approach?

Here is my code.

#include<algorithm>     
using namespace std;

typedef long long LL;
#define INF 1000000000000000LL

LL *segtree;
LL array[30001];
LL arr[90001];

void init_segtree(LL idx, LL b, LL e)
{
	if (b == e)
	{
		segtree[idx] = arr[b];
		return;
	}
	int mid = (b+e)>>1;
	init_segtree(2*idx+1, b, mid);
	init_segtree(2*idx+2, mid+1, e);
	segtree[idx] = (segtree[2*idx+1]&segtree[2*idx+2]);
}

LL query(LL idx, LL b, LL e, LL qb, LL qe)
{
	if (b > qe || qb > e)
		return -1LL;
	if (b >= qb && e <= qe)
		return segtree[idx];
	int mid = (b+e)>>1;
	LL ansL = query(2*idx+1, b, mid, qb, qe);
	LL ansR = query(2*idx+2, mid+1, e, qb, qe);
	return (ansL&ansR);
}

int main()
{
	LL T;
	scanf("%lld", &T);
	for (int t = 0; t < T; t++)
	{
		LL N, K;
		scanf("%lld %lld", &N, &K);
		for (int i = 0; i < N; i++)
			scanf("%lld", &array[i]);
		if (2*K+1 >= N)
		{
			LL ans = array[0];
			for (int i = 1; i < N; i++)
				ans = (ans&array[i]);
			for (int i = 0; i < N; i++)
				printf("%lld ", ans);
			printf("\n");
		}
		else
		{
			for (int i = 0; i < N; i++)
				arr[i] = array[N-1-i];
			for (int i = N; i < 2*N; i++)
				arr[i] = array[i-N];
			for (int i = 2*N; i < 3*N; i++)
				arr[i] = array[i-2*N];
			LL A = 3*N;
			segtree = new LL[4*A];
			init_segtree(0, 0, A-1);
			for (int i = 0; i < N; i++)
				printf("%lld ", query(0, 0, A-1, N+i-K, N+i+K));
			printf("\n");
		}
	}
	return 0;
}

I am trying to solve http://www.spoj.com/problems/HORRIBLE/. I have used segment tree with lazy propagation. But I am getting wrong answer. I tried debugging my code but I am unable to find any bug. Can anyone help me? Here is my code.

#include<cstdio>        
using namespace std;
typedef long long LL;

struct node
{
	LL ans;
	LL pro;
};

node *segtree;

LL query(int idx, int b, int e, int qb, int qe)
{
	if (b > qe || qb > e)
		return 0;
	if (segtree[idx].pro > 0)
	{
		segtree[idx].ans += (LL)(e-b+1)*segtree[idx].pro;
		if (b != e)
		{
			segtree[2*idx+1].pro += segtree[idx].pro;
			segtree[2*idx+2].pro += segtree[idx].pro;
		}
		segtree[idx].pro = 0;
	}
	if (b >= qb && e <= qe)
		return segtree[idx].ans;
	int mid = (b+e)>>1;
	LL ansL = query(2*idx+1, b, mid, qb, qe);
	LL ansR = query(2*idx+2, mid+1, e, qb, qe);
	return ansL+ansR;
}

void update(int idx, int b, int e, int qb, int qe, LL v)
{
	if (b > qe || qb > e)
		return;
	if (segtree[idx].pro > 0)
	{
		segtree[idx].ans += (LL)(e-b+1)*segtree[idx].pro;
		if (b != e)
		{
			segtree[2*idx+1].pro += segtree[idx].pro;
			segtree[2*idx+2].pro += segtree[idx].pro;
		}
		segtree[idx].pro = 0;
	}
	if (b >= qb && e <= qe)
	{
		segtree[idx].pro = v;
		return;
	}
	segtree[idx].ans += (LL)(min(e, qe)-max(b, qb)+1)*v;
	int mid = (b+e)>>1;
	update(2*idx+1, b, mid, qb, qe, v);
	update(2*idx+2, mid+1, e, qb, qe, v);
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++)
	{
		int N, Q;
		scanf("%d %d", &N, &Q);
		segtree = new node[4*N];
		for (int i = 0; i < 4*N; i++)
		{
			segtree[i].ans = 0;
			segtree[i].pro = 0;
		}
		int c, p, q;
		LL v;
		for (int i = 0; i < Q; i++)
		{
			scanf("%d %d %d", &c, &p, &q);
			if (c == 0)
			{
				scanf("%I64d", &v);
				update(0, 0, N-1, p-1, q-1, v);
			}
			else
				printf("%I64d\n", query(0, 0, N-1, p-1, q-1));
		}
	}
	return 0;
}