Background
Today I gave Atcoder ABC442. In problem E, I observed some analogy of setup of this problem with concepts of Linear Algebra.
Observations
Monsters are depicted as vectors in R^2 From Linear Algebra perspective, every monster i at coordinates (xi,yi) is a vector [Xi Yi]^transpose in the vector space R^2.Takahashi stands at the origin (the zero vector). When he faces a monster, he is aligning his "sight vector" with the subspace spanned by that monster's vector.
The problem frequently asks if two monsters are in the "same direction." In Linear Algebra, two non-zero vectors u and v are collinear (linearly dependent) if one is a scalar multiple of the other.
Quadrant/Basis Partitioning:The space R^2 is divided by the standard basis vectors i = (1,0) and j = (0,1). We can partition the plane into two half-planes (Upper and Lower) based on the sign of the y-component (and x-component if y is 0). This is a rough sort. Or there is Fine Sorting via Determinant: Within the same half-plane, determine the relative order of any two vectors u and v using their determinant (the "cross product").
Linear Algebra doesn't naturally have a "start" and "end" for angles like $$$0^\circ$$$ to $$$360^\circ$$$. Instead, partition R^2 into two half-planes (Upper and Lower) to create a strict linear order. Upper Half-Plane: Vectors where y > 0 or (y = 0 and x > 0). Lower Half-Plane: Vectors where y < 0 or (y = 0 and x < 0). Within each half-plane, the determinant uniquely determines the order.
Questions
- Did anyone find any other way to think about the setup of this problem within space of linear algebra?
- I saw multiple problems involving graphs and flow between nodes of graphs to be solvable using linear algebra. So far whatever book/blog/pdf of competitive programming I read this approach of thinking in realms of linear algebra in graphs problems is not being formalised. Is there any formalised way to think on this or its not possible?
- Graphs are non linear data structures in terms of arrangement of nodes so if linear algebra applies to them then it must not deal with arrangement of nodes mostly. May be deal with flow of aggregated values among nodes. Can someone confirm or share his thoughts on this?
