Problem in short:
Given a tree consisting of N nodes (<= 10^5). Assign a letter ('A'-'Z') to each node. For any 2 distinct nodes having t...
It's a basic implementation of centroid decomposed tree. Though after reading a while and solving a couple of problems i'm still unable to understand the necessity(and intuition) behind the centroid decomposition.The only time i think its useful is when two nodes are on two different subtree and then lca(on CD tree) can store some information about them.
For this specific problem.
In CD-tree, if two nodes have same rank,then they must have a common ancestor.
Problem in short: Consider an undirected graph of N nodes, M edges. Each edge is labeled with two integers A, B. Find a spanning tree of this graph which has the maximum possible value for the following expression:
Ac in one go!Thanks to Hussain's hints.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 111111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;priority_queue <pair < pair < double , int > , pii > > pq ;vector <pair < int , pii > > g[MAXN] ;int sumA , sumB ;bool visited[MAXN] ;
Given undirected graph of N nodes, M edges and a ranked list of exciting cities. You are to answer Q queries of the form (u, v, K), asking you to find the cost of the shortest path from u to v...
straightforward implementation of Floyd Warshall algorithm.just treat k as a[k] where a[k] is the array of ranked cities.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;int dp[152][152][151] , a[151];int main() {
R-numbers are numbers which have the property that they do not have the digit '0 ' and sum of every two adjacent digits of the number is prime. 123 is a R-number because 1+2 =3 and 2+3 =5 and 3 , 5 are primes.
How many R-numbers can be formed with at most length N?
find out the digit dp.for 1:
here is the solution.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111#define MOD 1000000007#define rep(i ,start , n) for(int i = start ;i<= n ; i++)
Given two non-negative integers N and M, you have to calculate the sum F(N) + F(N + 1) + ... + F(M) mod 1000000007, where F(X) = X-th fibonacci number
my recurrence relation goes like :
and watch out for the negatives.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))
You will be given a square matrix M and a positive integer power N. You will have to compute M raised to the power N. (that is, M multiplied with itself N times).
learned how to transform linear recurrence into matrix form and awesome matrix exponentiation implementation from fushar blog .
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MOD 1000000007#define REP(i ,n) for(int i = 1 ;i<=n ;i++)const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;typedef vector < vector < ll > > matrix ;
Interesting problem with more thinking and less implementation. You can find hints and more discussion here : POI 10 Sums. Problem is from Polish Olympiad in Informatics.
what a great problem!never thought of implementing dijkstra like this:
small intuition:Suppose x is the smallest number of set A and s_num[r] is the smallest number correspond to remainder r. now if input gives a number y such that y<s_num[r] and y%x == r.how can we prove that y can't be made from set A?
==> suppose we can make y from set A.then as per the smallest value concern we must choose y to be in the smallest number for remainder 'r' . as it didn't happen.our initial assumption is not true.so we can't make y from set A.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()
Problem in Short:
There are N star systems in the space, connected by M wormholes. Each wormhole can teleport you from a system A to system ...
This problem caused me a lot of troubles.thanks to Hussain's insights.specifically 2:
1.you need to deploy a dummy node.as bellman ford is SSSP algorithm.
2.you need to reverse the direction of the edges.cause upon reversing if you can relax any edge u→v in nth iteration .3things can happen:
1.Either both u and v is part of negative cycle.
2.one of them is a part of negative cycle.
3.none of them is part of negative cycle
in all of the three cases you can always visit the negative cycle from u and v(inclusive) .
Using set .with no optimization.implementation credit : Michal Forišek's answer to What is the most simple & efficient C++ code for Dijkstra's shortest path algorithm?
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;int dijkstra(vector < vector <pii > > &g , int start , int target) {vector < int > d(g.size()+1 , INT_MAX) ;d[start] = 0 ;set < pii > city ;
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 111111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;vector < int > g[MAXN] ;int cnt = 0 ;bool visited[MAXN] ;void dfs(int u) {cnt++ ;visited[u] = true ;for(int i = 0 ;i<g[u].size() ;i++)
