Showing posts with label dfs. Show all posts
Showing posts with label dfs. Show all posts

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)

Posted by at No comments:
Labels: , , , ,

Thursday, 30 October 2014

Simple bfs and dfs

// N-> total nodes , graph[N][N] adjacency matrix

int bfs(int start,int end)
{
    list <int > q ;
    q.push_back(y);
    int visited[N],frontt;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!q.empty())
    {
          frontt=q.front();
          
          q.pop_front();
          for(int i=0;i<N;i++)
          { 
                   if(graph[frontt][i] && !visited[i])
                   {
                         visited[i]=1;
                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(i==end)
                                return 1;
                        q.push_back(i);
                  }
           }
      }
return 0;
}







int dfs(int start,int end)
{
    list <int > st ;
    st.push_back(y);
    int visited[N],Top;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!st.empty())
    {
          Top=st.back();
          
          st.pop_back();
          for(int i=0;i<N;i++)
          { 
                   if(graph[Top][i] && !visited[i])
                   {
                         visited[i]=1;
                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(i==end)
                                return 1;
                        st.push_back(i);
                  }
           }
      }
return 0;
}



Some tweaks for adjacency  list

If there are N nodes
Input form
N->total number of nodes
then N lines with x and as first element (showing its connected to x elements)


scanf("%d",&N);
vector <int>  graph [N];
for(int i=0;i<N;i++)
{
    scanf("%d",&x);
    for(int j=0;j<N;i++)
    {
        scanf("%d",&e);
        v[j].push_back(e);
    }
}


Code modifications in dfs (similar for bfs)


int dfs(int start,int end)
{
    list <int > st ;
    st.push_back(y);
    int visited[N],Top;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!st.empty())
    {
          Top=st.back();
          
          st.pop_back();
          vector <int>:: iterator iii;

          for(int iii=graph[Top].begin();iii!=graph[Top].end();iii++)
          { 
                   if(graph[Top][i] && !visited[i])
                   {
                         visited[*iii]=1;
                         //graph[srart][*iii]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(*iii==end)
                                return 1;
                        st.push_back(*iii);
                  }
           }
      }
return 0;
}







Posted by at No comments:
Labels: , , ,
Subscribe to: Posts (Atom)