DECOSNKE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Subhadeep Chandra
Editorialist: Ritesh Gupta

DIFFICULTY:

EASY

PREREQUISITES:

Pattern, Math

PROBLEM:

The letters u, d, l, and r where u, d, l, and r represents up, down, left, and right respectively. If you start from (0, 0) and move according to the below-mentioned string then print the position at t second. It is given that a single move takes 1 sec. You have to find out the position on the cartesian plane at t second.
The string has this structure - ulddrruuulllddddrrrruuuuu… and so on.

Constraints:

  • 1 \leq T \leq 10^6
  • 1 \leq t \leq 10^{18}

EXPLANATION:

Let’s find out the pattern:
Start from (0, 0) then 1 u, 1 l, 2 d, 2 r, and 1 u.
Strat from (1, 0) then 2 u, 3 l, 4 d, 4 r, and 2 u.
Strat from (2, 0) then 3 u, 5 l, 5 d, 6 r, and 3 u.
\ldots
Strat from (n, 0) then (n+1) u, (2*n+1) l, (2*n+1) d, (2*n+2) r, and (n+1) u.

Now, we can calculate the time taken to reach the (n, 0) is given by:
Sum of first n numbers + Sum of first n odd numbers + Sum of first n odd numbers + 2 \cdot Sum of first n numbers + Sum of first n numbers =
4 \cdot Sum of first n numbers + 2 \cdot Sum of first n odd numbers

We can either use a binary search or simple math operations to find out the coordinate on non-negative x-axis such that time taken to reach that position is less or equal to t. If (n, 0) is that position and it requires t’ time to reach this position then subtract it from t and rest t is covered by this:

Strat from (n, 0) then (n+1) u, (2*n+1) l, (2*n+1) d, (2*n+2) r, and (n+1) u.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

#define int long long
#define endl “\n”

using namespace std;

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int tt;
cin >> tt;

while(tt--)
{
    int t;
    cin >> t;

    int n = (sqrt(t))/2;

    while(t >= (4*n*n+3*n))
        n++;

    n--;

    cout << n << endl;

    int x = n;
    int y = 0;

    t -= (4*n*n + 3*n);

    if(t){
        y += min(n+1,t);
        t -= min(n+1,t);
    }

    if(t){
        x -= min(2*n+1,t);
        t -= min(2*n+1,t);
    }

    if(t){
        y -= min(2*n+2,t);
        t -= min(2*n+2,t);
    }

    if(t){
        x += min(2*n+2,t);
        t -= min(2*n+2,t);
    }

    if(t){
        y -= min(n+1,t);
        t -= min(n+1,t);
    }

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

}

Tester's Solution

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;

inline void input(ll *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
while (c>33)
{
*a=a10+c-‘0’;
c=getchar_unlocked();
}
}

main()
{
ll n,t;
input(&t);

while(t--)
{
	input(&n);
	 
	ll lo=0,hi=2e9,mid;
	 
	while(lo<=hi)
	{
		mid=(lo+hi)>>1;
		 
		if((((mid)*(mid+1))>>1)>(n>>1))
			hi=mid-1;
		else
			lo=mid+1;
	}
	 
	ll left=0,up=0;
	 
	if(hi%2)
	{
		left=(hi+1)>>1;
		up=(hi+1)>>1;
	}
	else
	{
		left=-((hi+1)>>1);
		up=-((hi+1)>>1);
	}
	 
	n-=hi*(hi+1);
	 
	hi++;
	 
	if(hi%2)
	{
		left+=min(hi,n);
	}
	else
	{
		left-=min(hi,n);
	}
	 
	n-=min(hi,n);
	 
	if(hi%2)
	{
		up+=min(hi,n);
	}
	else
	{
		up-=min(hi,n);
	}
	 
	printf("%lld %lld\n",-up,left);
}

}