↵
↵
<spoiler summary="Solution">↵
It is very uncomfortable for us to keep track of Gigi's players. More specifically, it's awkward to note the fact that each second we must update all the blocked positions due to their movement. So, we make the following claim: A pass is unsuccesful if the segment [ (x_1,y), (x_2, y + (x_2-x_1)) ] intersects any player of Gigi's.↵
↵
↵
↵
↵
We can prove this by induction.↵
First, when we refer to (a,b)=1 at some time, it means that this point will be blocked at that time.↵
↵
Base case: (a+1,b), T=1 <=> (a+1,b+1), T=0 (i.e. they are equivalent points at different times)↵
↵
This derives from the statement, since if (a+1,b+1), T=0, then (a+1-1,b+1), T=1↵
↵
Inductive step: $$((a+x,b), T=x <=> (a+x,b+x), T=0) ==> ((a+x+1,b), T=x <=> (a+x+1,b+x+1), T=0)$$↵
↵
applying the base case on $(a+x+1,b+x), T=0$ we get ↵
↵
$$(a+x+1,b+x), T=1 <=> (a+x+1,b+x+1), T=0$$↵
then again, by default, we have $$(a,b)=val, T=x <=> (c,d)=val, T=y <===> (a+1,b), T=x+1 <=> (c+1,d), T=y.$$↵
↵
So $$(a+x+1,b+x), T=1 <=> (a+x+1,b+x+1), T=0$$ And $$ (a+x,b), T=x <=> (a+x,b+x), T=0 $$, so↵
$$ (a+x+1,b+x+1) T=0 <=> (a+x+1,b+x),T=1 <=> (a+x+1,b+1),T=x+1 $$↵
↵
QED↵
↵
Now, let's assume we have to solve the following problem:↵
↵
Given some vertical segments, determine for each query consisting of a horisontal segment if this intersects any of the earlier given segments.↵
↵
This is a classical exaample of a problem that can be solved using the technique of line-sweeping. The solution we know, at least, is the following: sort both the vertical segments and the horizontal ones by their greatest X-coordinate. Then:↵
A vertical segment is an update on all the Y-coordinates it covers.↵
A horizontal segment is a point-query that asks if the latest vertical segment that covers this Y-coordinate happened after the left-X-limit of the segment.↵
This can be solved using a Segment Tree with lazy propagation↵
↵
The problem is that momentarily we have queries on lines parallel to ( (0,0), (1,1) ), and segments for updates parallel to Oy. With more consideration, we can say that we are currently working in the space defined by↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
1 & 1 ↵
\end{pmatrix}↵
$$↵
So, we have to transform it to↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
0 & 1 ↵
\end{pmatrix}↵
$$↵
↵
This can be obviously done by multiplying with the inverse of the first matrix (by the definition of matrixes) and then multiplying it with the latter (which is the identity matrix, so it won't have any effect). The inverse we are talking about is of course:↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
-1 & 1 ↵
\end{pmatrix}↵
$$↵
↵
The effect on this matrix on ever \sout{point} vector in the plane is basically just subtracting the x-coordinate value from the y-coordinate value. So we use this to recalculate the input to the "normal" version. Then we can use the sweep-line algorithm we described earlier to solve the problem.↵
↵
Time complexity: O((N+M)*(log(N+M)+log(COORDMAX)))↵
↵
Space complexity: O(N+M+COORDMAX)↵
↵
<spoiler summary="Author's Note">↵
I do agree that I might have over-complicated the solution, but all of this was just for rigorous mathematical demonstration purposes. I also note that if we were to give the problem using something of the sorts "passes move with speed X, and players go down with speeds Y", the problem could've easily made it as the easy problem from some TST (the solution would be to change the first column of the initial transformation to (a,b)). We decided not to do this, because we didn't want to implement Segment trees over doubles, and neither would the contestant in this case. Also, as "artificial" the problem might seem, the idea for the original problem is as you see it in the statement (except the initial problem didn't have the bounds that the passes were horizontal and the blockers were vertical).↵
</spoiler>↵
↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
It is very uncomfortable for us to keep track of Gigi's players. More specifically, it's awkward to note the fact that each second we must update all the blocked positions due to their movement. So, we make the following claim: A pass is unsuccesful if the segment [ (x_1,y), (x_2, y + (x_2-x_1)) ] intersects any player of Gigi's.↵
↵
↵
↵
↵
We can prove this by induction.↵
First, when we refer to (a,b)=1 at some time, it means that this point will be blocked at that time.↵
↵
Base case: (a+1,b), T=1 <=> (a+1,b+1), T=0 (i.e. they are equivalent points at different times)↵
↵
This derives from the statement, since if (a+1,b+1), T=0, then (a+1-1,b+1), T=1↵
↵
Inductive step: $$((a+x,b), T=x <=> (a+x,b+x), T=0) ==> ((a+x+1,b), T=x <=> (a+x+1,b+x+1), T=0)$$↵
↵
applying the base case on $(a+x+1,b+x), T=0$ we get ↵
↵
$$(a+x+1,b+x), T=1 <=> (a+x+1,b+x+1), T=0$$↵
then again, by default, we have $$(a,b)=val, T=x <=> (c,d)=val, T=y <===> (a+1,b), T=x+1 <=> (c+1,d), T=y.$$↵
↵
So $$(a+x+1,b+x), T=1 <=> (a+x+1,b+x+1), T=0$$ And $$ (a+x,b), T=x <=> (a+x,b+x), T=0 $$, so↵
$$ (a+x+1,b+x+1) T=0 <=> (a+x+1,b+x),T=1 <=> (a+x+1,b+1),T=x+1 $$↵
↵
QED↵
↵
Now, let's assume we have to solve the following problem:↵
↵
Given some vertical segments, determine for each query consisting of a horisontal segment if this intersects any of the earlier given segments.↵
↵
This is a classical exaample of a problem that can be solved using the technique of line-sweeping. The solution we know, at least, is the following: sort both the vertical segments and the horizontal ones by their greatest X-coordinate. Then:↵
A vertical segment is an update on all the Y-coordinates it covers.↵
A horizontal segment is a point-query that asks if the latest vertical segment that covers this Y-coordinate happened after the left-X-limit of the segment.↵
This can be solved using a Segment Tree with lazy propagation↵
↵
The problem is that momentarily we have queries on lines parallel to ( (0,0), (1,1) ), and segments for updates parallel to Oy. With more consideration, we can say that we are currently working in the space defined by↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
1 & 1 ↵
\end{pmatrix}↵
$$↵
So, we have to transform it to↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
0 & 1 ↵
\end{pmatrix}↵
$$↵
↵
This can be obviously done by multiplying with the inverse of the first matrix (by the definition of matrixes) and then multiplying it with the latter (which is the identity matrix, so it won't have any effect). The inverse we are talking about is of course:↵
$$↵
\begin{pmatrix}↵
1 & 0 \\↵
-1 & 1 ↵
\end{pmatrix}↵
$$↵
↵
The effect on this matrix on ever \sout{point} vector in the plane is basically just subtracting the x-coordinate value from the y-coordinate value. So we use this to recalculate the input to the "normal" version. Then we can use the sweep-line algorithm we described earlier to solve the problem.↵
↵
Time complexity: O((N+M)*(log(N+M)+log(COORDMAX)))↵
↵
Space complexity: O(N+M+COORDMAX)↵
↵
<spoiler summary="Author's Note">↵
I do agree that I might have over-complicated the solution, but all of this was just for rigorous mathematical demonstration purposes. I also note that if we were to give the problem using something of the sorts "passes move with speed X, and players go down with speeds Y", the problem could've easily made it as the easy problem from some TST (the solution would be to change the first column of the initial transformation to (a,b)). We decided not to do this, because we didn't want to implement Segment trees over doubles, and neither would the contestant in this case. Also, as "artificial" the problem might seem, the idea for the original problem is as you see it in the statement (except the initial problem didn't have the bounds that the passes were horizontal and the blockers were vertical).↵
</spoiler>↵
↵
↵
↵
</spoiler>↵
↵
