algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit e499c2fe4d6700eae6adeb8fd2e21fa4f2f9addd
parent e3d4e9653dcdfda8b60a40a3e624c726deacf2bd
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 28 Oct 2026 11:53:46 -0500

caveman + robot factory codeforces (graph / comb + dfs / bitmask respectively)

Diffstat:
Acomp/caveman/ex1.in | 14++++++++++++++
Acomp/caveman/main.cpp | 90+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/caveman/problem.txt | 145+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/robot-factory/ex1.in | 5+++++
Acomp/robot-factory/main.cpp | 78++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/robot-factory/problem.txt | 48++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 380 insertions(+), 0 deletions(-)

diff --git a/comp/caveman/ex1.in b/comp/caveman/ex1.in @@ -0,0 +1,14 @@ +4 +3 1 +1 2 +3 2 +1 2 +1 3 +3 3 +1 2 +2 3 +1 3 +4 3 +1 2 +2 3 +3 4 diff --git a/comp/caveman/main.cpp b/comp/caveman/main.cpp @@ -0,0 +1,90 @@ +#include <iostream> +#include <unordered_map> +#include <vector> +#include <unordered_set> + +int dfs(std::unordered_map<int, std::vector<int>>& edges, std::unordered_set<int>& visited, int visiting, int parent, int& longest) { + + if(visited.contains(visiting)) { + return -1; + } + + visited.insert(visiting); + auto& toFollow = edges[visiting]; + int bestDepth = 0; + int secondDepth = 0; + + for(int i = 0; i < toFollow.size(); ++i) { + if(toFollow[i] == parent) { + continue; + } + int depthOf = dfs(edges, visited, toFollow[i], visiting, longest); + if(depthOf == -1) { + return -1; // cycle + } + if(depthOf > bestDepth) { + secondDepth = bestDepth; + bestDepth = depthOf; + } else if(depthOf > secondDepth) { + secondDepth = depthOf; + } + } + + if(bestDepth + secondDepth + 1 > longest) { + longest = bestDepth + secondDepth + 1; + } + return bestDepth + 1; // inclusive +} + +std::string solve(int vertices, std::unordered_map<int, std::vector<int>>& edges) { + + for(int i = 0; i < vertices; ++i) { + if(edges[i].size() == 0) { + return "Brain Melt"; + } + } + + std::unordered_set<int> visited {}; + int components = 0; + + for(int i = 0; i < vertices; ++i) { + if(!visited.contains(i)) { + components += 1; + if(components > 1) { + return "Many"; + } + int longest = 0; + int res = dfs(edges, visited, i, -1, longest); + if(res == -1 || longest >= 4) { + return "Many"; + } + } + } + + return "2"; +} + +int main() { + + int testCases, numEdges, numVertices, c1,c2; + std::cin >> testCases; + + for(int i = 0; i < testCases; ++i) { + std::cin >> numVertices; + std::cin >> numEdges; + + std::unordered_map<int, std::vector<int>> edges {}; + + for(int x = 0; x < numEdges; ++x) { + std::cin >> c1; + std::cin >> c2; + c1 -= 1; + c2 -= 1; // make this zero indexed + edges[c1].push_back(c2); + edges[c2].push_back(c1); + } + std::cout << solve(numVertices,edges) << std::endl; + } + + return 0; +} diff --git a/comp/caveman/problem.txt b/comp/caveman/problem.txt @@ -0,0 +1,145 @@ +D. Caveman +time limit per test2 seconds +memory limit per test512 megabytes +Monocarp drew an undirected graph with n + vertices and m + edges. He wants to color each vertex red or blue so that every vertex has at least one neighbor of the opposite color. He needs to calculate the number of colorings that suit him. + +Monocarp is a caveman: he knows only the numbers 1 +, 2 +, and "many" (any number greater than 2 +). He does not know about zero, so if there are no valid colorings, his brain melts. + +Help Monocarp count the valid colorings in his language. Two colorings are considered different if at least one vertex has a different color in them. + +Input +The first line contains an integer t + (1≤t≤104 +) — the number of test cases. + +The first line of each test case contains two integers n + and m + (3≤n≤3⋅105 +; 0≤m≤min(n(n−1)2,3⋅105) +) — the number of vertices and edges. + +Each of the next m + lines contains two integers ui + and vi + (1≤ui,vi≤n +) — the numbers of the vertices connected by the i +-th edge. The graph has no self-loops or multiple edges. + +Additional constraints on the input: + +the sum of n + over all test cases does not exceed 3⋅105 +; also the sum of m + over all test cases does not exceed 3⋅105 +. +Output +For each test case, print on a separate line: + +1 or 2, if the number of valid colorings is equal to 1 + or 2 + respectively; +Many, if the number of valid colorings is greater than two; +Brain Melt, if there are no valid colorings. + +--- + +- n vertices, m edges, undirected graph +- two-coloring s.t. every vertex of a given color has at least one neighbor of the other color +- Two colorings are considered different if at least one vertex has a different color in them. + - this implies there are at least two colorings if a coloring is possible bc just swap the colors, no statement about isomorphism or the like + +- cases: + - 2 + - many (>2) + - brain melt (0) + +--- + +3 1 +1 2 + + +v := {1,2,3} +e := {{1,2}} + +1 := blue +2 := red +3 := blue + +no possible colorings like this because 3 is disconnected. generally, if there's a single disjoint vertex 0 is the answer + + +--- + +3 2 +1 2 +1 3 + + +{1,2,3} +{{1,2}, {2,3}} + +1 := blue +2 := red +3 := blue + +// heuristic: set the first element to be blue, second to red, unless first is red then second is blue (bipartite) + +flip the colors is another option so return 2 + +--- + +3 3 +1 2 +2 3 +1 3 + +{1,2,3} + +1,2 - 2,3 - 1,3 + +1 := blue +2 := red +3 := blue + +since there's a cycle it seems we can do more colorings? + +option 2: invert opt 1 + +option 3: + +1 := blue +2 := blue +3 := red + +--- + +4 3 +1 2 +2 3 +3 4 + +{1,2,3,4} + +1 -> 2 +2 -> 3 +3 -> 4 + +1 := blue +2 := red +3 := blue +4 := red + +invert + +1 := blue +2 := red +3 := red +4 := blue + +--- diff --git a/comp/robot-factory/ex1.in b/comp/robot-factory/ex1.in @@ -0,0 +1,5 @@ +4 5 +9 14 11 12 13 +5 15 11 6 7 +5 9 14 9 14 +3 2 14 3 14 diff --git a/comp/robot-factory/main.cpp b/comp/robot-factory/main.cpp @@ -0,0 +1,78 @@ +#include <vector> +#include <algorithm> +#include <iostream> + +// - idea: +// - for each position: +// - dfs +// - each step returns the size of the connected component that's newly visited from the position (there will likely be cycles) +// - dfs: +// - go up,left,right,down if there's not a wall on that side +// - we don't have to check bounds because walls are on edges. + +int searchFrom(std::vector<std::vector<int>>& grid, std::vector<bool>& visited, int y, int x) { + int currentIdx = (y * grid[0].size()) + x; + if(visited[currentIdx]) { + return 0; + } + visited[currentIdx] = true; + + int res = 1; + int current = grid[y][x]; + + // North, East, South, West + if((current & 0b1000) == 0) { + res += searchFrom(grid,visited, y-1, x); + } + + if((current & 0b0100) == 0) { + res += searchFrom(grid,visited, y, x+1); + } + + if((current & 0b0010) == 0) { + res += searchFrom(grid,visited, y+1, x); + } + + if((current & 0b0001) == 0) { + res += searchFrom(grid,visited, y, x-1); + } + return res; +} + +int main() { + int rows,cols,current; + std::cin >> rows; + std::cin >> cols; + + std::vector<std::vector<int>> grid {}; + for(int y = 0; y < rows; ++y) { + std::vector<int> cLs {}; + for(int x = 0; x < cols; ++x) { + std::cin >> current; + cLs.push_back(current); + } + grid.push_back(cLs); + } + + std::vector<bool> visited (grid[0].size() * grid.size(), false); + std::vector<int> result {}; + + for(int y = 0; y < rows; ++y) { + for(int x = 0; x < cols; ++x) { + int res = searchFrom(grid,visited,y,x); + if(res != 0) { + result.push_back(res); + } + } + } + + std::sort(result.begin(), result.end()); + std::reverse(result.begin(), result.end()); + + for(int i = 0; i < result.size(); ++i) { + std::cout << result[i] << " "; + } + + std::cout << std::endl; + +} diff --git a/comp/robot-factory/problem.txt b/comp/robot-factory/problem.txt @@ -0,0 +1,48 @@ +J. Robot Factory +time limit per test1 second +memory limit per test256 megabytes +You have received data from a Bubble bot. You know your task is to make factory facilities, but before you even start, you need to know how big the factory is and how many rooms it has. When you look at the data you see that you have the dimensions of the construction, which is in rectangle shape: N x M. + +Then in the next N lines you have M numbers. These numbers represent factory tiles and they can go from 0 to 15. Each of these numbers should be looked in its binary form. Because from each number you know on which side the tile has walls. For example number 10 in it's binary form is 1010, which means that it has a wall from the North side, it doesn't have a wall from the East, it has a wall on the South side and it doesn't have a wall on the West side. So it goes North, East, South, West. + +It is guaranteed that the construction always has walls on it's edges. The input will be correct. + +Your task is to print the size of the rooms from biggest to smallest. + +Input +The first line has two numbers which are N and M, the size of the construction. Both are integers: + +n + (1≤n≤103 +) + +m + (1≤m≤103 +) + +Next N x M numbers represent each tile of construction. + +Output +Once you finish processing the data your output consists of one line sorted from biggest to smallest room sizes. + +--- + +- construction size is MxN +- factory tiles are bounded from 0 -> 15 + - consider them in binary + - 1111 + - 1's mean a wall on that side + - ordering: + - north, east, south west +- print room sizes from smallest to largest +- it is guaranteed that the construction always has walls on it's edges. The input will be correct. + +--- + +- idea: + - for each position: + - dfs + - each step returns the size of the connected component that's newly visited from the position (there will likely be cycles) + - dfs: + - go up,left,right,down if there's not a wall on that side + - we don't have to check bounds because walls are on edges.