PROBLEM LINK:
Author: Daanish Mahajan
Tester: Radoslav Dimitrov
Editorialist: Daanish Mahajan
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
Given a horizontal square table of size N with lower left corner at (0, 0), find the position of the ball which when hit from the coordinate (0 < x < N, 0 < y < N) at an angle 45^{\circ} (with the horizontal) strikes the table for the K^{th} time or the coordinate of the corner where the ball stopped. Its assumed that collision is elastic and angle of incidence is equal to angle of reflection and the ball has a constant velocity throughout its motion.
QUICK EXPLANATION:
Since the table is square in shape, if the ball is striked along the diagonal then answer is (N, N) else the ball strikes exactly 4 distinct points and then repeats its trajectory.
EXPLANATION:
Subtask 1: For this task \sum_{i=1}^{T} K_i <= 10^7, so we can have a \mathcal{O}(K) brute force solution finding the point of next collision using the point of intersection of line from present point and the angle of projection with the side of square.
Subtask 2: It can be further divided into 3 cases.
1) x = y: Here the answer always remains (N, N).
For the further 2 cases, the ball strikes exactly 4 distinct points and then repeats its trajectory. Therefore points of collision are periodic with period 4. That is answer for K = \{1, 5, 9...\}, \{2, 6, 10...\}, \{3, 7, 11...\}, \{4, 8, 12...\} is same. So the answer for K is equivalent to answer for K \% 4. Let K' = K \% 4.
Depending on whether the starting point is in the lower triangle (i.e, below the Y = X line) or the upper triangle, the ball will follow an anti-clockwise or clockwise trajectory. Hence, we separate these as the two following cases:
2) y > x: Let (X , Y) be the axis variables. So the line passing through (x, y) at 45^{\circ} can be represented as X = Y - y + x.
Proof
Slope = Tan(45^{\circ}) = 1 = \frac{Y - y}{X- x}
Using this we can find the point of intersection with lines X = 0 and Y = N giving result for fourth and first collision ,i.e, K' = \{0, 1\} respectively which are the mirror coordinates for K' = \{3, 2\} respectively along the line Y = X.
Case Work
if(k' == 1){
x = n + x1 - y1; y = n;
}else if(k' == 2){
x = n; y = n + x1 - y1;
}else if(k' == 0){
x = 0; y = y1 - x1;
}else{
x = y1 - x1; y = 0;
}
3) x > y: Same logic applies here but the order of intersecting lines is different.
Case Work
if(k' == 1){
x = n; y = n - x1 + y1;
}else if(k' == 2){
x = n - x1 + y1; y = n;
}else if(k' == 0){
x = x1 - y1; y = 0;
}else{
x = 0; y = x1 - y1;
}
So finally we have a constant time solution. Hence the final complexity is \mathcal{O}(T).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int maxt = 1e5;
const int maxn = 1e9;
const int maxk = 1e9;
int main()
{
int t; cin >> t;
while(t--){
int n, k, x1, y1; cin >> n >> k >> x1 >> y1;
int x, y;
if(x1 == y1){
x = n; y = n;
}else{
if(x1 > y1){
if(k % 4 == 1){
x = n; y = n - x1 + y1;
}else if(k % 4 == 2){
x = n - x1 + y1; y = n;
}else if(k % 4 == 0){
x = x1 - y1; y = 0;
}else{
x = 0; y = x1 - y1;
}
}else{
if(k % 4 == 1){
x = n + x1 - y1; y = n;
}else if(k % 4 == 2){
x = n; y = n + x1 - y1;
}else if(k % 4 == 0){
x = 0; y = y1 - x1;
}else{
x = y1 - x1; y = 0;
}
}
}
cout << x << " " << y << endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 20);
int n, x, y, k;
void read() {
cin >> n >> k >> x >> y;
}
void solve() {
if(x == y) {
cout << n << ' ' << n << endl;
return;
}
bool to_swap = false;
if(x > y) {
to_swap = true;
swap(x, y);
}
pair<int, int> answer;
if(k % 4 == 0) answer = {0, y - x};
if(k % 4 == 1) answer = {n + x - y, n};
if(k % 4 == 2) answer = {n, n + x - y};
if(k % 4 == 3) answer = {y - x, 0};
if(to_swap) swap(answer.first, answer.second);
cout << answer.first << ' ' << answer.second << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}