it is the minimum number of vertex that need to be selected such that every edge in graph is selected
https://www.youtube.com/watch?v=RD7Oaw0H-W4
https://www.youtube.com/watch?v=RD7Oaw0H-W4
Saturday, 10 January 2015
bfs and dfs spoj questions extra dp question list
BFS & DFS
Dijkstra, Floyd Warshall, Prim & Kruskal
• Longest Increasing Subsequence (LIS) – Classical
1. UVa 103 - Stacking Boxes (Longest Path in DAG ≈ LIS)
2. UVa 111 - History Grading (straight-forward)
3. UVa 231 - Testing the Catcher (straight-forward)
4. UVa 481 - What Goes Up? (must use O(n log k) LIS)
5. UVa 497 - Strategic Defense Initiative (solution must be printed)
6. UVa 10051 - Tower of Cubes (can be modeled as LIS)
7. UVa 10534 - Wavio Sequence (must use O(n log k) LIS twice)
8. UVa 11790 - Murcia’s Skyline (combination of classical LIS+LDS, weighted)
9. UVa 11003 - Boxes
10. UVa 11456 - Trainsorting (get max(LIS(i) + LDS(i) - 1), ∀i ∈ [0 . . . N -1])
11. LA 2815 - Tiling Up Blocks (Kaohsiung03)
• Coin Change – Classical
1. UVa 147 - Dollars (similar to UVa 357 and UVa 674)
2. UVa 166 - Making Change
3. UVa 357 - Let Me Count The Ways (a variant of the coin change problem)
4. UVa 674 - Coin Change
553.4. DYNAMIC PROGRAMMING
c Steven & Felix, NUS
5. UVa 10306 - e-Coins
6. UVa 10313 - Pay the Price
7. UVa 11137 - Ingenuous Cubrency (use long long)
8. UVa 11517 - Exact Change
• Maximum Sum
1. UVa 108 - Maximum Sum (maximum 2-D sum, elaborated in this section)
2. UVa 836 - Largest Submatrix (maximum 2-D sum)
3. UVa 10074 - Take the Land (maximum 2-D sum)
4. UVa 10667 - Largest Block (maximum 2-D sum)
5. UVa 10827 - Maximum Sum on a Torus (maximum 2-D sum)
6. UVa 507 - Jill Rides Again (maximum 1-D sum/maximum consecutive subsequence)
7. UVa 10684 - The Jackpot (maximum 1-D sum/maximum consecutive subsequence)
• 0-1 Knapsack – Classical
1. UVa 562 - Dividing Coins
2. UVa 990 - Diving For Gold
3. UVa 10130 - SuperSale
4. LA 3619 - Sum of Different Primes (Yokohama06)
• String Edit (Alignment) Distance – Classical (see Section 6.3)
• Longest Common Subsequence – Classical (see Section 6.3)
• Non Classical (medium difficulty)
1. UVa 116 - Unidirectional TSP (similar to UVa 10337)
2. UVa 473 - Raucuous Rockers
3. UVa 607 - Scheduling Lectures
4. UVa 10003 - Cutting Sticks (discussed in this book)
5. UVa 10337 - Flight Planner (DP solvable with Dijkstra)
6. UVa 10891 - Game of Sum (2 dimensional states)
7. UVa 11450 - Wedding Shopping (discussed in this book)
8. LA 3404 - Atomic Car Race (Tokyo05)
• DP + Bitmasks
1. UVa 10364 - Square (bitmask technique can be used)
2. UVa 10651 - Pebble Solitaire
3. UVa 10908 - Largest Square
4. UVa 10911 - Forming Quiz Teams (elaborated in this section)
5. LA 3136 - Fun Game (Beijing04)
6. PKU 2441 - Arrange the Bulls
• DP on ‘Graph Problem’
1. UVa 590 - Always on the Run
2. UVa 910 - TV Game (straightforward)
3. UVa 10681 - Teobaldo’s Trip
4. UVa 10702 - Traveling Salesman
5. LA 4201 - Switch Bulbs (Dhaka08)
6. SPOJ 101 - Fishmonger
563.5. CHAPTER NOTES
c Steven & Felix, NUS
• DP with non-trivial states
1. LA 4106 - ACORN (Singapore07) (DP with dimension reduction)
2. LA 4143 - Free Parentheses (Jakarta08) (Problem set by Felix Halim)
3. LA 4146 - ICPC Team Strategy (Jakarta08) (DP with 3 states)
4. LA 4336 - Palindromic paths (Amritapuri08)
5. LA 4337 - Pile it down (Amritapuri08)
6. LA 4525 - Clues (Hsinchu09)
7. LA 4526 - Inventory (Hsinchu09)
8. LA 4643 - Twenty Questions (Tokyo09)
• DP on Tree
1. UVa 10243 - Fire! Fire!! Fire!!! (Min Vertex Cover ≈ Max Independent Set on Tree)
2. UVa 11307 - Alternative Arborescence (Min Chromatic Sum, 6 colors are sufficient)
3. LA 3685 - Perfect Service (Kaohsiung06)
4. LA 3794 - Party at Hali-Bula (Tehran06)
5. LA 3797 - Bribing FIPA (Tehran06)
6. LA 3902 - Network (Seoul07)
7. LA 4141 - Disjoint Paths (Jakarta08)
which graph is tree (Is it a tree)
For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the number of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS or BFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. ( Every time we are on some node, we calculate the number of his neighbors which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any other trees apart form our graph.
Friday, 2 January 2015
Header Extras
// struct pair
typedef struct mmm
{
int a,b;
}pai;
// (a^b)%c
lld mod_power(lld a, lld n, lld mod){
// returns (a^n) % mod.
// '%' represents modulus operation.
lld y = 1;
while(n){
if(n & 1)
y = (y * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return y;
}
// inverse modulo
lld inverse(lld num){
// returns the inverse of num w.r.t. (10^9 + 7).
// uses the property a^(-1) mod p = a^(p-2) mod p.
return mod_power(num, MOD - 2, MOD);
}
sieve
bool p[10000000000];
int prime(int a)
{
for(int i=2;i*i<=a;i++)
{
if(!p[i])
for(int j=2;i*j<=a;j++)
p[i*j]=1;
}
}
typedef struct mmm
{
int a,b;
}pai;
// (a^b)%c
lld mod_power(lld a, lld n, lld mod){
// returns (a^n) % mod.
// '%' represents modulus operation.
lld y = 1;
while(n){
if(n & 1)
y = (y * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return y;
}
// inverse modulo
lld inverse(lld num){
// returns the inverse of num w.r.t. (10^9 + 7).
// uses the property a^(-1) mod p = a^(p-2) mod p.
return mod_power(num, MOD - 2, MOD);
}
sieve
bool p[10000000000];
int prime(int a)
{
for(int i=2;i*i<=a;i++)
{
if(!p[i])
for(int j=2;i*j<=a;j++)
p[i*j]=1;
}
}
my header
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int main()
{
// freopen("kr.in","r",stdin);
scanf("%d",&t);
while(t--)
{
}
return 0;
}
using namespace std;
int t,n,m;
int main()
{
// freopen("kr.in","r",stdin);
scanf("%d",&t);
while(t--)
{
}
return 0;
}
grid traversal (smart way ;) ) with bfs
now to move in the four direction of a grid we can use
}
| int positionsX[4]= {0,-1,0,1}; | |
| int positionsY[4]= {-1,0,1,0}; |
how to use it in the code part
| for(int i=0;i<4;i++){ | |
| int newx=top.first+positionsX[i],newy=top.second+positionsY[i]; |
we can also use a function
(validPosition(newx,newy))
and put the necessary condition in it , to make sure that the newly formed position is correct
code example
(with bfs traversal in a grid)
spoj question -> BITMAP
SOLUTION LINK
Thursday, 1 January 2015
bipartite graph (BUGS LIFE) SPOJ
http://www.spoj.com/problems/BUGLIFE/
usual mistake treated the vertices in the code starting from 0 but not modifying the input which is generally of the form where numbering starts from 1.
so that needs to taken care of in graph (ALWAYS)
#include<stdio.h>
#include<vector>
#include<queue>
int N,flag;
using namespace std;
int visited[2000+5];
vector<int> g[2000];
int bpg(int v)
{
visited[v]=1;
queue<int> q;
q.push(v);
// int flag=0;
while(!q.empty())
{
int y=q.front();
q.pop();
for(int i=0;i<g[y].size();i++)
{
int r=g[y][i];
if(!visited[r])
{ q.push(r);
if(visited[y]==1)
{
visited[r]=2;
}
else if(visited[y]==2)
visited[r]=1;
}
else
{
if(visited[r]==visited[y])
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
}
int main()
{
//freopen("kr.in","r",stdin);
int t,m,n ,i,a,b;
int ee=0;
scanf("%d",&t);
while(t--)
{ flag=0;
ee++;
scanf("%d %d",&m,&n);
//vector<int > g[m];
for( i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
// remember if it doesnt work make it undirected
}
N=m;
for(i=0;i<2000;i++)
{
visited[i]=0;
}
for( i=0;i<m;i++)
{
if(!visited[i])
{
bpg(i);
}
}
printf("Scenario #%d:\n",ee);
if(flag==1)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
for( i=0;i<2000;i++)
g[i].clear();
}
}
usual mistake treated the vertices in the code starting from 0 but not modifying the input which is generally of the form where numbering starts from 1.
so that needs to taken care of in graph (ALWAYS)
#include<stdio.h>
#include<vector>
#include<queue>
int N,flag;
using namespace std;
int visited[2000+5];
vector<int> g[2000];
int bpg(int v)
{
visited[v]=1;
queue<int> q;
q.push(v);
// int flag=0;
while(!q.empty())
{
int y=q.front();
q.pop();
for(int i=0;i<g[y].size();i++)
{
int r=g[y][i];
if(!visited[r])
{ q.push(r);
if(visited[y]==1)
{
visited[r]=2;
}
else if(visited[y]==2)
visited[r]=1;
}
else
{
if(visited[r]==visited[y])
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
}
int main()
{
//freopen("kr.in","r",stdin);
int t,m,n ,i,a,b;
int ee=0;
scanf("%d",&t);
while(t--)
{ flag=0;
ee++;
scanf("%d %d",&m,&n);
//vector<int > g[m];
for( i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
// remember if it doesnt work make it undirected
}
N=m;
for(i=0;i<2000;i++)
{
visited[i]=0;
}
for( i=0;i<m;i++)
{
if(!visited[i])
{
bpg(i);
}
}
printf("Scenario #%d:\n",ee);
if(flag==1)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
for( i=0;i<2000;i++)
g[i].clear();
}
}
Subscribe to:
Posts (Atom)