| Problem | solution | code |
|---|---|---|
| ChessBoard and Queens | Diagnols have constant value. Each right diagnol is (i+j) and each main diagnol is i-j | code |
| digit queries | there are 9 number with 1 length digit, 90 numbers with 2 length digits , 900 (3) digit numbers | code |
| Grid paths | A path that forms a loop can't be traversed.(if front and back are visited and left and right not visited then do not traverse the path.) | code |
| Problem | solution | code |
|---|---|---|
| Dice Combinations | dp[0]=1(when no dice is thrown). get i as sum from dp[i-diceNum] ways | code |
| Minimizing Coins | 10^8 worked on cses, dp[i]=min(dp[i],1+dp[i-coins[i]]) | code |
| Coin Combinations I | for any no. of combination loop through coins again and again for each sum of money. dp[i]+=dp[i-coins[j]] | code |
| Coin Combinations II | for unique combination traverse each coin once. dp[j]+=dp[j-coins[i]] | code |
| Removing digits | always remove max digit | code |
| Grid Paths | dp[i][j]=dp[i-1][j]+dp[i][j-1] | code |
| Book Shop | 0-1 knapsack, dp[i][cost]=max(dp[i-1][cost],dp[i-1][cost-c[i]]) | code |
| Array Description | if arr[i]=0 new dp[i]=previous dp[i-1]+dp[i]+dp[i+1] else rest dp[i]=0 | code |
| Counting Towers | for (n,n-1) sub-block it can be considered as 2X2 block which has 8 possible solution.there can be 4 states where transition is from vertical line block -> no line block,vertical line-> vertical line, no line->vertical line, no line-> no line. dp[i][0]=((dp[i-1][0]<<1)+dp[i-1][1])%mod , dp[i][1]=((dp[i-1][1]<<2)+dp[i-1][0])%mod | code |
| Edit Distance | if string is of 0 length the min operation would be the other strings length. dp[i][j]=min(1+dp[i-1][j],1+dp[i][j-1],a[i]==b[j]+dp[i-1][j-1]) | code |
| Rectangle Cutting | base case is when square is formed then dp[i][i]=0. here dp[i][j] means iXJ dimensional rectangle and not the not matrix indices.To compute for iXJ rectangle cut the rectangle into two pices column wise then row wise as each smaller cut is already computed, so iXJ can be found out.Its cost is minimum of all sub rectangular division+1 | code |
| money sums | dp[0]=1 , iterate all coins and for each coin iterate all possible sum and mark that different sum. At last count all marked sum that are possible | code |
| Removal Game | If two people are playing alternatively then both person will have different set of digits. let set 1 has total sum of X and set 2 has total sum of Y then X+y= total sum of array. Here we want to find X if both player play optimally. if we get X-Y = T somehow then X can find as X=(totalsum+T)/2. we have array arr[i....j] then if a person choose arr[i] or arr[j] and remove them then it will be max of both choice , then ans=max(arr[i]-dp[i+1...j],arr[j]-dp[i...j-1]). Also a-(b-(c-(d-(e...))))= (a+c+e)-(b+d) .final ans will be the value of X-Y and hence X can be calculated | code |
| Two sets II | it is 0-1 knapsack | code |
| increasing subsequence | end[i] is the minimum number which ends of longest increasing subsequence having length i+1. end[] is not the final LIS but it stores the least number that are end of lis having length i+1.If a number num is encountered while traversing then it is put at position where length is i+1 and its least there using binary search lower bound , if no such position is found then it is put at the end of end[] array.end[] is always an increasing sequence. | code |
| projects | sort according to the end work day of each project.dp[i] will store the maximum amount of money that can be earned till ith day.dp[i]=max(dp[i-1],lower_bound(start of work day[i])), it is either taking score of the ith day to final answer or not including it to final answer. | code |
| Elevator Rides | bitmask dp, if dp[100101] is to be calculated then it is result of dp[000101], dp[100001] and dp[1000100]. traverse from 0 to pow(2,n) and larger subset dp can be calculated by removing each bits at a time as subproblems solution is known then the dp can be computed.Here we have to find number of minimum rides for all the people and how much total weight is in the last ride. dp[subsequence]={rides,min_weight at last ride} is calculated by going through each subset from smaller to higher . dp[0]={1,0} , for no people in lift total rides is least 1 and last ride weight in lift is 0 this is the base case. | code |
| Counting Tilings | Thinking brute force way , first find total number of ways to tile first column , then 2nd column and so on.previous Tile can be represented as binary number of max length 10. each valid binary tiling way is find out taking previous tiling way into consideration. [tiling way for particular column] +=[tiling way for previous column] because if a particular column can be tiled in a way then it has some horizontal tiles then for next column tiles can be placed in only some position then all possible ways of tiling for those positions is found out.At the end we get the answer | code |
| counting numbers | Always apply reccurence solution for digit dynamic programming first , index of array and tight is always there for every digit dp. then other constrainst like sum or previous digit or leading zeros can be added to parameters . if tight is true traversal is bounded till that fixed digit in the number otherwise traversal is till 9, then recursively solve the problem.convert it to dp & initially all dp states is -1 | code |
| Problem | solution | code |
|---|---|---|
| Counting Rooms | simple dfs | code |
| Labyrinth | track previous path visited (bfs) | code |
| Building Roads | connect one node from each non connected sets of graph | code |
| Message Route | Store previous node info while bfs | code |
| Round Trip | here we have to find the loop in the undirected graph. Store previous node info(parent) using node and print the loop elements. | code |
| Monsters | its simple bfs, first process all monsters then player, use simple visited matrix & track previous path followed. | code |
| Shortest Routes I | Simple dijkstra, but two citys can have different distance in between them, so process only city's paht that can reach us to another city with bare min distance. | code |
| Shortest Routes II | it's floyd warshall algorithm , for each intermediate city compute shortest distance between two cities. | code |
| High Score | mark those nodes that can be visited by starting node ( here starting node is 1).It can have positive cycle which can increase score when cycle is visited again and again to track this cycle bellman ford is applied on nodes which are marked initially. once bellman ford is applied store the score of destination node and reapply bellman ford on nodes which are marked initially and make new distance as infinite because there will be cycle and positive cycles add upto infinite , at end of this bellmand ford algorithm the end node or destination node may change if the positive cycle affected it's score. if it affects then return -1 else display score. | code |
| Flight Discount | Apply dijkstra starting from node 1 such that we get all other distances from node 1.After reversing graph, Apply dijkstra starting from node n such that we get all other distances from node n. Now iterate over all edges and cost =minimum(cost,cost1[a]+weight/2+costn[b]). | |
| Cycle Finding | apply floyd warshall and also store previous nodes connecting the node. cycle can be O-O like two negative cycles connecting each other and we can not determine using a node if it's inside a cycle or not. To overcome this problem revisit previous node each time n times . after it will be sure that start node is in a negative cycle as there are max n nodes.Then store and display the cycle. | code |
| Flight routes | maintain a array of max priority queue for storing distance of best k shortest routes . Perform dijkstra , if size of distance array is less than k then insert the current distance , else insert more smaller distance and remove bigger distance, size shouldn't exceed k for any priority queue. array[n] will contain the answer. | code |
| Round Trip II | Don't ever try to store previous state in dfs on graph, I lack understanding and it's very difficult more me.Just Maintain a onStack array if the node is onStack and it's visited then it is the end element of the solution, retrack using dfs and insert all other elements after it and we get the final solution.just reverse and display it. | code |
| Course Schedule | Simply apply topological sort.Topological sort uses queue | code |
| Longest Flight Route | It's an directed acyclic graph so rather than applying dijkstra having complexity O(NlogN) , apply topological sort (O(n)) where it makes sure that a node comes before another node. Then dis[] array can be used efficiently to compute shortest distance as well as maintaning prev connected node. | code |
| Game Routes | any directed acyclic graph can be converted to Dynamic programming and any Dynamic programmming problem can be converted to acyclic graph. In this question for possible paths dfs(v)=dfs(u1)+dfs(u2)+...dfs(ui). As dfs closely resembles with topological sort where one node has to occur previous of another node , here nodes can be arranged in topological order and dp can be applied on each node for its successive node and hence dp[n] can be found out. | code |
| Investigation | Simple dijsktra's problem | code |
| Planets Queries I (Binary Uplifting) | Global variables or arrays are declared in heap memory where as inside function variables stored in stack.Heap memory can store as large as the constraints on memory are given in online platform.Stack overflow may occur for large size such as 10^7 or 10^8, Hence stack overflow may cause error. therefore declare constant size arrays for large size array globally.cout<<endl also consumes time so use cout<<"\n" .for fast input output use ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); | code |
| Planet Queries II (Binary uplifting) | Find dfs to compute distance starting from particular node and check if binarylift(a,distance)==b | code |
| Planet Cycles | Any node on cycle will have cycle length distance and any node outside cycle will have distance as distance from it to cycle and length of cycle.Cycle can be detected using floyd's algorithm(tortoise and hare) then mark it visited and compute it's length. | code |
| Road preparation | kruskal's algorithm(union & find), sorting | code |
| Road construction | Disjoint set union algorithm(kruskal using weight) | code |
| Flight routes check | This is strongly connected component problem, perform kosaraju algorithm and check if number of component is 1 | code |
| Planets and kingdoms | perform kosaraju algorithm and track component of each planet. | code |
| Giant Pizza (2SAT) | 2 Sat is satisfiability problem in which every statement is true and each statement has 2 variables . Example (a or b) and (b or ~c) . atleast one variable from each statement must be true to make whoe expression's value true. Now a or b has edges = (~a-> b) and (~b->a). if ~a is reachable by a and a is rechable by ~a then both should be true which is not possible, so variable and it's complement should not be in same component. The Kosaraju's algorithm form's strongly connected components in topoplogical sorted way. We can check that if index of a variable and it's complementary variable is same then it must be in same component hence solution will not exist.If they have different index and a is rechable by ~a then a must be true otherwise false. | |
| Coin Collector | Perform kosaraju algorithm, this algorithm generates topological sorted components . The component cost is sum of cost of each node in component because they can reach each other. make a new graph of components using edges , each component must be linked to a different component. Because components form acyclic directed graph then dynamic programming can easily be applied. Perform DFS and apply dynamic programming to find maximum cost. | code |
| Mail Delivery | It is eulerian tour in which starting and ending node are same. In an undirected graph the eulerian path exist if all the edges are visited once and degree of each node is even or degree of two nodes is odd.Eulerian path having odd degree is not eulerian tour.In a directed graph either all nodes has outdegree equivalent to indegree or one of two nodes having outdegree 1 greater than indegree and indegree one greater than it's outdegree. The one greater outdegree node is the starting node and one greater indgree node is ending node of eulerian path in directed graph.To print eulerian path use fleury algorithm in which if a node is in the path then all the nodes edges are processed , removed and recursively other nodes connected to it are traversed. After removing all the connected edges to it the node is added to the path. | |
| code | ||
| De Bruijn Sequence | De Bruijn Sequence is minimum-length bit string that contains all possible substrings of length n. This String can be build by finding eulerian path on nodes having values has bit string of n-1 length . Each node either has outgoing edge of 0 and 1 . Then indegree[node]==outdegree[node]==2 for each node. Therefore eulerian algorithm can be applied. Find the eulerian path starting from 0 using fleury algorithm, (print each cycles one by one) | code |
| Teleporters path | In a directed graph either all nodes has outdegree equivalent to indegree or one of two nodes having outdegree 1 greater than indegree and indegree one greater than it's outdegree. The one greater outdegree node is the starting node and one greater indgree node is ending node of eulerian path in directed graph.To print eulerian path use fleury algorithm in which if a node is in the path then all the nodes edges are processed , removed and recursively other nodes connected to it are traversed. After removing all the connected edges to it the node is added to the path. | code |
| Hamiltonian Flights | It's a NP hard problem, where we have to find path visiting all the nodes exactly once from start to destination.A brute force would be to form an array of path containing values from 1 to N and check for each permutation of this path, this would be O(N!) time complexity.A more optimized way to solve is using dynamic programming similar to Elevator Rides problem in CSES where bitmask DP is applied.Iterate from smaller subset to bigger subset , for each subset calculate number of ways for each element. Example dp[1111]=dp[0111]+dp[1011]+dp[1101]+dp[1110]. In this problem dp[1<<N][N] is formed in which every state from 1 to N is calculated for each subset. for Each subset's element smaller subset is checked if it's element can reach bigger subset's element then smaller subset's ways is added to bigger subset's element way's.A good optimization would be to skip the computation if subset contains last node/element or destination node and we haven't reached this node /the end node.The destination nodes number of ways would be calculated at last when whole subset is to be computed. | code |
| Knight's Tour | Warnsdorff suggested a simple rule: Always move the knight to a square from which it will have the fewest available subsequent moves.Do a simple DFS and find all valid path's , sort these paths in ascending order according to least subsequent move's for each path.Traverse using DFS .Time complexity would be O(N^4) to O(N^5) / O(6000) or O(7000). | |
| code | ||
| Download Speed | A problem where maximum flow is asked to find out we apply fordFulkerson algorithm using The Edmonds–Karp algorithm O(m^2n) or Scaling algorithm (m^2 logc).Ford Fulkerson suggest that to find max flow repeatedly find path from source to destination until it exist .For each phase of finding path once the path is found find the minimum cost edge of the path and subtract all edges cost from this minimum cost and make a reverse edge add this cost to the reverse edge.This minimum cost corresponds to that this amount of flow is send from source to destination and hence this amount of flow got removed from the path and added to reverse edge.Once done then repeatedly find other paths and remove minimum cost and add to corresponding reverse edge. If later the path is found better then reverse edge can be used to find path and subtracting flow from reverse edge and adding it to actual edge can happen and other path is found out with greater flow. Using BFS and finding minimum will cost O(m^2n) complexity , however if Scaling algorithm is applied then it is more efficient. As a number can be represented in binary form for each power of 2 number from higher to lower it is checked if path exist where this power 2 number is less than every edge cost or flow. then every edge cost is reduced by this 2 power number. It is similar to reducing with minimum cost except here minimum cost is found out using binary representation for each power of 2. The maximum flow would be equivalent to reverse edge flow for destination node. A maximum flow is equivalent to minimum cut so that flow cannot reach the end. | code |
| Police Chase | A max flow problem is equivalent to minimum cut so ford fulkerson is applied through BFS algorithm. Again BFS is done and checked if a node can be reached and it's edge node can't be reached to find out the edge which is cut. | code |
| School Dance | When unique path's are to be found / Unique edges from source to destination then this is equivalent to ford fulkerson algorithm for finding max flow. Each pair can be represented as bipartite graph where left side is connected to start node with each edge weight as 1. The right side of bipartite graph is connected to destination node with each edge weight 1 .Then just find out max flow from source to destination which is equivalent to maximum unique pairs . | code |
| Distinct Routes | Number of distinct routes can be found out using ford fulkerson(edmonds karp) where once the whose algorithm is executed then bfs can be applied to path's whose edges are missing and mark those edges so those are not visited again for new distinct route.So for distinct route only those edges are visited which were orignally present and is unvisited and now removed through ford fulkerson algorithm for max cost. | code |
| Problem | solution | code |
|---|---|---|
| Static Range Sum Queries | Find prefix sum S[], sum of range a to b is S[b]-S[a-1] | code |
| [] |