Official
Let us consider the complexity, which depends on the number of tuples of vertices $(z, x, y)$ enumerated by the innermost loop. Let us proof by exhaustion: $x=y$ and $x \neq y$.
The number of tuples such that $x=y$ is bounded by the number of vertex pairs $(z, x)$ where there is an edge between $z-x$, which in turn is bounded by the number of edges $M$.
That of $x \new y$ can be bounded by $T(T-1)+1$ using the Pigeonhole Principle: since the array $M$ has $T(T-1)$ elements with $x\neq y$, and the program terminates once it accesses the same element twice, by the Pigeonhole Principle, by the time $(z,x,y)$ are enumerated $T(T-1)+1$ times, there are at least one element accessed twice and the program terminates.
Therefore, the problem has been solved in a total of $\mathrm{O}(S+M+T^2)$ time.
F - Find 4-cycle Editorial by en_translator
This problem requires a kind of ad-hoc ideas. Some of you may come up with the answer with a couple of hints, so let us reveal them one by one.
Hint 1
There are $\mathrm{O}(T^2)$ pairs of vertices in $V_2$, where $T^2 \simeq 10^7$ is sufficiently small.Hint 2
Suppose that, for a pair $(x,y)$ of vertices in $V_2$, we found two vertices in $V_1$ which are adjacent to both $x$ and $y$. (Let $z$ and $w$ be these vertices.) Then, $(x, y, z, w)$ forms a 4-cycle. The key is that "all we need is such two vertices."Hint 3
We can construct a fast algorithm based on Hint 1 and 2 as well as a mathematical idea ...Hint 4
which is called "the Pigeonhole Principle."Solution
The problem can be solved with the algorithm described by the following procedure.- Store the edges of $G$ in an adjacency list $L$ where the indices correspond to the vertices in $V_1$ and the elements in the list to those in $V_2$.
- Prepare a $T \times T$ two-dimensional array $M$ whose indices correspond to the vertices in $V_2$. The elements of $M$ are all initialized with $M$.
-
For each $z \in V_1$, scan $L[z]$ (that is, the list of vertices adjacent to $z$) with a double for-loop like
for x in L[z]: for y in L[z]:
. - In the for loop, do the following:
-
If $x=y$, then
continue
without doing anything. - If $x \neq y$, do one of the following depending on $M[x][y]$.
- If $M[x][y]$ equals $-1$, then it means that we have not found a vertex adjacent to $x$ and $y$ yet, so let $M[x][y] = z$ and continue.
- If $M[x][y]$ does not equal $-1$, then let $w = M[x][y]$. $w$ is a vertex adjacent to both $x$ and $y$. Thus, $x,y,z$, and $w$ form a 4-cycle, so print them and terminate the program.
-
If a 4-cycle wasn't found after scanning all $z$, print
-1
and terminate the program.
Let us consider the complexity, which depends on the number of tuples of vertices $(z, x, y)$ enumerated by the innermost loop. Let us proof by exhaustion: $x=y$ and $x \neq y$.
The number of tuples such that $x=y$ is bounded by the number of vertex pairs $(z, x)$ where there is an edge between $z-x$, which in turn is bounded by the number of edges $M$.
That of $x \new y$ can be bounded by $T(T-1)+1$ using the Pigeonhole Principle: since the array $M$ has $T(T-1)$ elements with $x\neq y$, and the program terminates once it accesses the same element twice, by the Pigeonhole Principle, by the time $(z,x,y)$ are enumerated $T(T-1)+1$ times, there are at least one element accessed twice and the program terminates.
Therefore, the problem has been solved in a total of $\mathrm{O}(S+M+T^2)$ time.
posted:
last update: