 # RECNDNUM - Editorial

Author: Ritesh Gupta
Editorialist: Ritesh Gupta

EASY

MATH, EQUATIONS

# PROBLEM:

A game is defined on non-negative x-axis as you have to start your journey from 0_{th} location in positive x direction and every time you visit a new integer location, you have to come again at 0^{th} position. It will take 1 second to reach from i^{th} location to (i-1)^{th} location or (i+1)^{th} location**.

You are given two non-negative integers N(0 \le N \le 10^9) and K(1 \le K \le 10^9). You have to tell the time at which you arrive at x = N location on the positive x-axis for K^{th} time.

# QUICK EXPLANATION:

• For 0^{th} location, the time at which you are here are: \{0,2,6,12...\} which is given by K * (K-1).
• For any other location, the answer is given by - N * N + (K//2) * (2*N) + ((K+1)//2) * ((K+1)//2 - 1) where // represents the integer division.

# EXPLANATION:

• For N = 0, we know that we will reach the 0^{th} location for every time we visit a new location. So, we observe that time taken to visit an i^{th} location from the 0^{th} location and come back to 0^{th} location, is equal to 2*i and if we formulate it then the K^{th} term is given by K * (K-1).

• Otherwise, we know that we visit any i^{th} location first time after visiting 0^{th} location (i-1) times plus the time is taken from 0^{th} location to i^{th} location which takes (i-1)*(i) + i = i*i.

• The second time, it will take time equal to the first time + \space 2*i, as it will go up to 0^{th} location and come back again.
• The third time, it will take time equal to the second time + \space 2, as it will go up to (i+1)^{th} location and come back again.
• The fourth time, it will take time equal to the third time + \space 2*i, as it will go up to 0^{th} location and come back again.
• The fifth time, it will take time equal to the fourth time + \space 4, as it will go up to (i+2)^{th} location and come back again.
And so on…

By formulating, it evaluates to N * N + (K//2) * (2*N) + ((K+1)//2) * ((K+1)//2 - 1) where // represents the integer division, N(>0) is the location and K(>=0) is the count of the visit.

TIME: O(1)
SPACE: O(1)

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>

#define int long long
#define mod 1000000007
#define endl "\n"

using namespace std;

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

int t;
cin >> t;

while(t--)
{
int n,k;
cin >> n >> k;

if(n == 0)
{
cout << (k*(k-1))%mod << endl;
continue;
}

int ans = n*n;
ans %= mod;
ans += 2*(k/2)*n;
ans %= mod;
k = (k+1)/2;
ans += k*(k-1);
ans %= mod;

cout << ans << endl;
}
}
``````
Tester's Solution
``````T=int(input())
MOD=int(1e9+7)
for t in range(T):
N,K=[int(a) for a in input().split()]
M=K//2
# ans= ((K%2)?( (N+M)*(N+M) + M ):( (N+M)*(N+M) - M) )
ans=(N+M)*(N+M) -M
if(K%2):
ans+=2*M
if(N==0):
ans=K*(K-1)
print(ans%MOD)
``````
6 Likes

HOW TO THINK LIKE THAT.

10 Likes

With your brain  Jokes aside, I wrote a brute force solution and analyzed the occurrences of each element.

3 Likes

N∗N+(K//2)∗(2∗N)+((K+1)//2)∗((K+1)//2−1)
where did you get this formula? or how you derived?

Missed the n==0 case 1 Like
``````l = 

for i in range(1, 10):
l.extend(list(range(1, i+1)) + list(range(i-1, -1, -1)))

d = {}

for i, j in enumerate(l):
d[j] = d.get(j, []) + [i]

for i, j in d.items():
print(i, j)
``````

This is the python code I used to figure out the solution.

``````0 [0, 2, 6, 12, 20, 30, 42, 56, 72, 90]
1 [1, 3, 5, 7, 11, 13, 19, 21, 29, 31, 41, 43, 55, 57, 71, 73, 89]
2 [4, 8, 10, 14, 18, 22, 28, 32, 40, 44, 54, 58, 70, 74, 88]
3 [9, 15, 17, 23, 27, 33, 39, 45, 53, 59, 69, 75, 87]
4 [16, 24, 26, 34, 38, 46, 52, 60, 68, 76, 86]
5 [25, 35, 37, 47, 51, 61, 67, 77, 85]
6 [36, 48, 50, 62, 66, 78, 84]
7 [49, 63, 65, 79, 83]
8 [64, 80, 82]
9 
``````

This is the output. I just checked the output for the first 4 elements.

For 0:

``````0, 2, 6, 12, 20, 30, 42, 56, 72, 90
+2 +4 +6 ...
``````

For 1:

``````1, 3, 5, 7, 11, 13, 19, 21, 29, 31, 41, 43, 55, 57, 71, 73, 89
+2 +2 +4 +2 +6 +2 ...
``````

For 2:

``````4, 8, 10, 14, 18, 22, 28, 32, 40, 44, 54, 58, 70, 74, 88
+4 +2 +4 +4 +4 +6 +4 ...
``````
3 Likes I did the exact same thing, but I was saved by my random testcase generator

1 Like

I used binary search

2 Likes

How ?

Consider case of n = 1 Till first occurance we have n^2 time elapsed (golden in image). Then onwards look at the points to the left and points to the right.

The left points (red) form mountains of constant height and each containing 2n points.

The right mountains (green) form a sequence 2, 4, 6, 8. Now all that remains is to find out how many of these left and right mountains are required to reach our k.

If you look at editorial expression, the first term is time to reach k = 1. Second term is contribution of left mountains, and third term is contribution of right mountains. 4 Likes

if k is even
(n+(k/2))(n+(k/2))-(k/2)
else
(n+(k/2))
(n+(k/2))+(k/2)

1 Like

See all sequences starting from 0 and ending to 1 as a block. We can get the index of 0 by the formula i*(i+1), where i is the index of the i’th occurence of 0 . Upto the i’th block, the total count of n is 1+(i-n)*2. At each stage, see if this is less than or greater than k and recurse.

General term of sequence where difference of numbers of sequence differ by 2 is `pow(n,2)+ c*n +k` where c and k can be calculated by plugging in some values of n (n denotes the term number of sequence).

Do check out my unofficial editorial Chef and Walk editorial (UNOFFICIAL)

1 Like

Can anyone help me with this plz…which test case will not work with the following code??

ll n,k,x,ans;
cin>>n>>k;
if(n==0)
cout<<((k)*(k-1))%MOD<<endl;
else{
x = (n+k/2)%MOD;
ans = (x * x)%MOD;
if(k&1){
ans = (ans+abs(n-x))%MOD;
}
else{
ans -= abs(n-x);
}
cout<<ans<<endl;

It’s because of overflow Try this testcase `1000000000 1000000000`

Thanks. But I’m still getting wrong submission with this changed code.

``````        ll n,k,x;
unsigned ll ans;
cin>>n>>k;
if(n==0){
cout<<((k)*(k-1))%MOD<<endl;
}
else{
x = (n+k/2)%MOD;
ans = (x*x)%MOD;
if(k&1){
ans = (ans+abs(n-x))%MOD;
}
else{
ans = (ans-abs(n-x))%MOD;
}
cout<<ans<<endl;
}
``````

Can u tell what I’m doing wrong.

I am not able to find what’s wrong with my code. Here’s my code

https://www.codechef.com/viewsolution/32373259

#define lli long long int
#define mod 1000000007
#include
using namespace std;
#include<bits/stdc++.h>
{
char c;
lli n = 0;
while ((c = getchar_unlocked ()) < 48);
n += (c - ‘0’);
while ((c = getchar_unlocked ()) >= 48)
n = n * 10 + (c - ‘0’);
return n;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

``````lli T=read();

while(T--)
{

// t=n*(n+1) this formula is for total time of nth round (returned back to zero)
lli t=((n%mod)*((n+1)%mod))%mod;

k--;

if(k>0)
{
/*
t=(n+(k/2))*(n+(k/2)+1) same as above but putting k/2 extra rounds with n
i.e. putting n=n+(k/2)
*/

t=(( ((n%mod) + ((k/2)%mod) )%mod) * ((((n%mod) + ((k/2)%mod) +1))%mod));

if(k%2==0)
t=((t%mod)-(n%mod))%mod;//t=t-n
else
t=((t%mod)+(n%mod))%mod;//t=t+n

}
else
t=( (t%mod)-(n%mod))%mod;//t=t-n

cout<<t%mod<<endl;
}
return 0;
``````

}

instead of using long long for n, k. Can we use ‘int’ for them? And only use a long long variable to store the ans. Is this possible or will it overflow then?