BILLRD-Editorial

PROBLEM LINK:

Practice
Div-3 Contest

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;
				}

VIDEO EDITORIAL:

4 Likes

Can u tell me what was wrong in my code. All the things were done same as yours. I have check dry run cases but after submission it’s always giving me wrong answer.

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t,n;

cin>>t;

while(t--)

{

   int  n,k,x,y;

   cin>>n>>k>>x>>y;

         if(x==y)

            {

               x=n;

               y=n;

            } 

        if(x>y)

        {

            if(k%4==1)

            {

               y=y+n-x;

               x=n;

            }

           else if(k%4==2)

           {

                x=y+n-x;

                y=n;

            }

           else if(k%4==3)

           {

                y=x-y;

                x=0;

            }

            else if(k%4==0){

                x=x-y;

                y=0;

            }

         }     

        if(x<y)

        {

            if(k%4==1)

            {

                x=(n+x)-y;

                y=n;

            }

            else if(k%4==2)

            {

                y=(n+x)-y;

                x=n;

            }

           else if(k%4==3)

           {

                x=y-x;

                y=0;

            }

            else if(k%4==0)

            {    

                y=y-x;

                x=0;

            }

        }

        cout<<x<<" "<<y<<endl;

    }

}

Using if conditions is wrong, use else if
For eg: if (x > y) and k % 4 == 2, this make x < y after the update so it next enters in if (x < y) condition too

Thanks Man!!! That was the silly mistake I was doing.

can anyone help me with this? why it’s not getting accepted?

#include
using namespace std;

void billRd(float N , int K, float a, float b)
{
if(a-b == 0)
{
cout<< N <<" β€œ<< N <<endl;
}else if(a-b>0)
{
if(K%4==1)
cout<< N <<” β€œ<< N + b - a <<endl;
else if(K%4==2)
cout<< N + b - a <<” β€œ<< N <<endl;
else if(K%4==3)
cout<< 0 <<” β€œ<< a - b <<endl;
else if(K%4==0)
cout<< a - b <<” "<< 0 <<endl;

  }
  else if(a-b<0)
  {
       if(K%4==1)
              cout<< N + a - b <<" "<< N <<endl;
        else if(K%4==2)
              cout<< N <<" "<< N + a - b <<endl;
        else if(K%4==3)
              cout<< b - a <<" "<< 0 <<endl;
        else if(K%4==0)
              cout<< 0 <<" "<< b - a <<endl; 
  }

}
int main()
{
int T;
cin>>T;

  while(T--)
  {
        float num;
        int collision;
        cin>>num;
        cin>>collision;
        float x,y;
        cin>>x;
        cin>>y;
        
        billRd(num , collision , x , y);
        
  }
  return 0;

}

https://www.codechef.com/viewsolution/41616202
Why my code giving NZEC ?

point1, point2 = k%4 -1 is wrong ll give -1 if k%4==0 hence NZEC

Can u paste the link to your WA solution

here:
https://www.codechef.com/viewsolution/41593962

If I remove -1 then output for second test case (5 2 3 1) gives wrong answer

Hi! Could you please help me identify the issue in this solution:

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define um unordered_map
#define fop first
#define sop second
#define ll long long int
#define vl vector<ll>
#define vi vector<unsigned int>
#define vs vector<string>
#define print(a) cout << a

#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define test(string,a) cout<<string<<a

#define FEI(el,s) for(int el : s)
#define FOR(index,a,n) for (ll index = a; index < n; index++)
#define FORD(index,a,n) for (ll index = a; index >= n; index--)
#define NL cout<<"\n"
#define TAB '\t'

int main()
{
	sync;
	unsigned int t,n,k,x,y; 
	unsigned int cx[4], cy[4];
	
	cin>>t;	
	
	while(t--)
	{
		cin >> n >> k >> x >> y;
	
			if(x==y)
			{
				cout<<n<<" "<<n<<"\n";
				continue;
			}
			
			else if(x>y)
			{
				cx[1]=n;			cy[1]=y+(n-x);
				cx[2]=cy[1];		cy[2]=cx[1];
				cx[3]=0;			cy[3]=x-y;		//y3=x-y
				cx[4]=cy[3];		cy[4]=cx[3];
			
			}
			
			else
			{
				cx[1]=x+(n-y);		cy[1]=n;
				cx[2]=cy[1];		cy[2]=cx[1];
				cx[3]=y-x;	        cy[3]=0;				//x3=y-x
				cx[4]=cy[3];		cy[4]=cx[3];

			}
		
			cout<<cx[k%4]<<" "<<cy[k%4]<<"\n";
	}

return 0;
}

t = int(input())
for i in range(t):

    n, k, x, y = map(int, input().split())
    if x == y:
        print(n, n)

    else:
        if x-y > 0:
            x = x-y
            x1, y1 = n, (n - x)
            x2, y2 = y1, n
            x3, y3 = 0, n - x2
            x4, y4 = x, 0

        else:
            y = y - x
            x1, y1 = n - y, n
            x2, y2 = n, x1
            x3, y3 = n - y2, 0
            x4, y4 = 0, y
        if k % 4 == 0:
            print(x4, y4)
        elif k % 2 == 0:
            print(x2, y2)
        elif (k-1) % 4 == 0:
            print(x1, y1)
        else:
            print(x3, y3)

Since u have used float your output will be like
1e+009 1e+009
1.25962e+006 0
0 5.36349e+008
8.93793e+008 1e+009
1e+009 9.40415e+008
0 8.01452e+007
6.59194e+008 0
1e+009 9.13287e+008
9.94672e+008 1e+009
0 1

as you can see it will be rounded up
one way to get right ans is to set precision limit higher

instead of cx[4] and cy[4] use cx[0] and cy[0]