Posts

Aggressive cow

  #include<iostream> #include <vector> #include<string> #include<queue> #include<algorithm> #include <unordered_map>   using namespace std ; typedef long long int ll ;     bool possible ( vector < int > v, ll mid, ll k ) {   int last ; int cnt = 0 ; last = v [ 0 ] ; cnt ++ ; for ( int i = 1 ; i < v. size ( ) ; i ++ ) { if ( v [ i ] - last >= mid ) { cnt ++ ; last = v [ i ] ;   if ( cnt == k ) return true ; } }   if ( cnt >= k ) return true ; else return false ;         }     int main ( ) {     int t ; cin >> t ; while ( t -- ) {   int n, k ; cin >> n >> k ;   vector < int > v ( n, 0 ) ;   for ( int i = 0 ; i < n ; i ++ ) cin >> v [ i ] ;   sort ( v. begin ( ) , v. end ( ) ) ;   long long int resul...
Post a Comment
Read more

LRU Cache Implementation

 // LRU Cache implementation #include <iostream> #include <unordered_map> using namespace std; class DLLNode { public: int key; int value; DLLNode *next; DLLNode *prev; DLLNode(int k, int v) { this->key = k; this->prev = NULL; this->value = v; this->next = NULL; } }; //Data structure and globals unordered_map<int, DLLNode*> cache; int Size =0; int capacity; DLLNode * head = new DLLNode(-1, -1); DLLNode * tail = new DLLNode(-1, -1); void addNodeAtHead(DLLNode *node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; return; } void removeNode(DLLNode* node) { DLLNode* prev = node->prev; DLLNode* next = node->next; prev->next = next; next->prev = prev; } int removeFromTail() { DLLNode* temp = tail->prev; removeNode(temp); return temp->key; } void moveToHead(DLLNode *node) { cout << "access this key" << node->key...
Post a Comment
Read more

Segmentation Tree

#include< iostream > #include< string > #include< vector > #include< algorithm > using namespace std ; void Build ( int arr [], int segtree [], int s , int e , int index ) {      if ( s == e ) {         segtree [ index ] = arr [ s ];      }      else {          int mid = ( s + e ) / 2 ;         Build ( arr , segtree , s , mid , 2 * index );         Build ( arr , segtree , mid + 1 , e , 2 * index + 1 );          if ( segtree [ 2 * index ] < segtree [ 2 * index + 1 ])             segtree [ index ] = segtree [ 2 * index ];          else    ...
Post a Comment
Read more

Dynamic Creation of Graphs for competitive programming

  In competitive programming, usually STL is used for faster programming and there the problem when we need to create dynamic array if we represent the graph by adjacency list. in most of Visual studio, the only option is using new operator which is not very useful in competitive programming. here is alternative way to make a graph using vector of  vector instead of array in case we need to create a graph of  (n+1) nodes when we have taken "n" as input. // vector of vector for adjacency list. vector<vector<long long int>> adjlist; adjlist.resize(n+1);   // it will help to create a graph of (n+1) nodes. // input the edges for (long long int i = 0; i < m; i++) { long long int u; long long int v; cin >> u >> v; adjlist[u].push_back(v); adjlist[v].push_back(u); } //Visited array for DFS vector<long long int> visited(n + 1); for (long long int i = 0; i <= n; i++) visited[i] = -1; //Standard DFS Code. visited[0] ...
Post a Comment
Read more