Tag Archives: spoj

Spoj ACPC10A solution

Spoj ACPC10A solution. Spoj Whats Next solution. Category: AdHoc, Math, Formula This question is based on direct application of Arithmetic Progression‘s common difference and Geometric Progression‘ common ratio. First check whether there is a common difference (c-b) and (b-a) , or whether there is common ratio (c/b) and (b/a). Spoj ACPC10A solution code: #include <bits/stdc++.h> using… Read More »

Spoj PRISMSA solution

Spoj PRISMSA solution. Spoj TRIANGULAR PRISM solution. Category: AdHoc, Math, Formula This question is of minimization of Surface Area for a Triangular Prism whose volume is given. Applying the standard differentiating procedure, the value of “a” comes out to be: a = (4V)1/3  , h = a/ sqrt(3) Putting the values together, we get: Surface Area = 3*a*a*sqrt(3) / 2;… Read More »

Spoj TETRA solution

Spoj TETRA solution. Spoj Sphere in a tetrahedron  solution. Category: AdHoc, Geometry, Formula This question is based on geometry as we need to find the radius of the sphere subscribed inside an irregular tetrahedron Required Radius = (3*volume of Tetrahedron)/(sum of surface areas of triangular faces). This requires calculation of volume of Irregular Tetrahedron using its edge… Read More »

Spoj PIR solution

Spoj PIR solution. Spoj Pyramids solution. Category: AdHoc, Geometry, Formula This question is based on geometry as we need to find the volume of Irregular Tetrahedron using its edge lengths. Here is the formula required: Spoj Pyramids solution code: #include <bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(false); int t; cin>>t; while(t–) { double u,v,w,U,V,W,vol,a,b=12; cin>>u>>v>>w>>W>>V>>U; /*steps to calculate volume… Read More »

Spoj MAJOR solution

Spoj MAJOR solution. Spoj MAJORITY solution. Category: AdHoc, Algorithm In this question we need to check if there is a majority element in the given array or not. This question can be solved in O(n) complexity in two traversals using Moore’s Voting algorithm. Spoj MAJOR solution code: Here is the working code: #include <bits/stdc++.h> using… Read More »

Spoj BUGLIFE solution

Spoj BUGLIFE solution. Spoj A Bug’s Life solution. Category: Graph Theory, BFS In this question we have to check whether the given graph is Bipartite or not. We use the standard procedure to using the BFS traversal, to colour alternate BUGs(level nodes) using two different colours (we use integers). Spoj BUGLIFE solution code: Here is the working… Read More »

Spoj PT07Z solution

Spoj PT07Z solution. Spoj Longest path in a tree solution. Category: Graph Theory, DFS/BFS In this question, we need to find the Longest Path length in a Tree. This can be solved using either 2 BFS traversals of single DFS traversal, we discuss the solution using DFS traversal. We use the DFS travesal on two sub-graphs and… Read More »

Spoj PT07Y solution

Spoj PT07Y solution. Spoj Is it a tree soltuion Category: Graph Theory, BFS/DFS In this question, we need to check whether the given graph is a tree or not. To solve this either BFS/DFS can be used, we need to mark a node as visited, the first time we visit it. If the node occurs again i.e it is… Read More »

Spoj HOTELS solution

Spoj HOTELS solution. Spoj Hotels Along the Croatian Coast Solution. Category: Dynamic Programming, DP This problem uses a technique called sliding window method or Kadane’s algorithm (Modified version is used). It is fairly easy to understand. Logic used: In this, you need a continuous set of hotels. To consider a set (window), we will use two pointers-… Read More »

Spoj BRCKTS solution

Spoj BRCKTS solution. Spoj Brackets solution. Category : Segment Trees In this problem, we are given a string containing parenthesis (open and closed), which requires making updates to individual parenthesis (changing an open parenthesis to closed or vice versa), and checking if the whole string represents a correct parenthesization. Only 2 things are needed in each segment… Read More »