8000 Add tags to DP and Geometry · cp-algorithms/cp-algorithms@dff436d · GitHub
[go: up one dir, main page]
Skip to content

Commit dff436d

Browse files
author
Oleksandr Kulkov
committed
Add tags to DP and Geometry
1 parent 08cbb5b commit dff436d

29 files changed

+159
-2
lines changed

‎src/dynamic_programming/divide-and-conquer-dp.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
---
2+
tags:
3+
- Original
4+
---
5+
16
# Divide and Conquer DP
27

38
Divide and Conquer is a dynamic programming optimization.

‎src/dynamic_programming/knuth-optimization.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
---
2+
tags:
3+
- Original
4+
---
5+
16
# Knuth's Optimization
27

38
Knuth's optimization, also known as the Knuth-Yao Speedup, is a special case of dynamic programming on ranges, that can optimize the time complexity of solutions by a linear factor, from $O(n^3)$ for standard range DP to $O(n^2)$.

‎src/dynamic_programming/profile-dynamics.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: profile_dynamics
5+
---
6+
17
# Dynamic Programming on Broken Profile. Problem "Parquet"
28

39
Common problems solved using DP on broken profile include:

‎src/dynamic_programming/zero_matrix.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: maximum_zero_submatrix
5+
---
6+
17
# Finding the largest zero submatrix
28

39
You are given a matrix with `n` rows and `m` columns. Find the largest submatrix consisting of only zeros (a submatrix is a rectangular area of the matrix).

‎src/game_theory/games_on_graphs.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: games_on_graphs
5+
---
6+
17
# Games on arbitrary graphs
28

39
Let a game be played by two players on an arbitrary graph $G$.

‎src/game_theory/sprague-grundy-nim.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: sprague_grundy
5+
---
6+
17
# Sprague-Grundy theorem. Nim
28

39
## Introduction

‎src/geometry/area-of-simple-polygon.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
---
2-
title: Finding area of simple polygon in O(N)
2+
title: Finding area of simple polygon in O(N)
3+
tags:
4+
- Translated
5+
e_maxx_link: polygon_area
36
---
47
# Finding area of simple polygon in $O(N)$
58

‎src/geometry/basic-geometry.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
---
2+
tags:
3+
- Original
4+
---
5+
16
# Basic Geometry
27

38
In this article we will consider basic operations on points in Euclidean space which maintains the foundation of the whole analytical geometry.

‎src/geometry/check-segments-intersection.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: segments_intersection_checking
5+
---
6+
17
# Check if two segments intersect
28

39
You are given two segments $(a, b)$ and $(c, d)$.

‎src/geometry/circle-circle-intersection.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
---
2+
tags:
3+
- Translated
4+
e_maxx_link: circles_intersection
5+
---
6+
17
# Circle-Circle Intersection
28

39
You are given two circles on a 2D plane, each one described as coordinates of its center and its radius. Find the points of their intersection (possible cases: one or two points, no intersection or circles coincide).

0 commit comments

Comments
 (0)
0