Problem:-
Paraphrase:-
We have a sequence,
0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,3,4,3,2,1,0....
we can only move to left in the above sequence, no skipping is allowed and to move chef from one number to next number costs us 1 unit of time, given n an k and we’ll have to find the time it takes chef to be on n^{th} number for the k^{th} time.
My Approach and Observations:-
No matter which category of the two below you choose…just please haaalp me…
I spent hours and hours on generating logic, writing codes, failed like crazy 10 times, writing and editing this huge editorial like length.
BTW, I also wrote a custom test case generator to generate all values of 0\le n \le 10^3 and for each n I generated 1\le k \le 10^3 values, wrote a checker program to match my answers again setters code generated answers…and found not a single mismatch. I even checked for n = k = 10^9 and got the same answer as setters.
For those who directly jump to formulas and test, here’s everything in order
Approach
row = n + \Large (\frac {(k-1)}{2}) \normalsize + (k-1) - 2*\Large (\frac {(k-1)}{2}) (integer divisions only)
r_{limit} = row * (row+1)
l_{limit} = (row-1)^2 + row
if(k\%2 = 0 \parallel n =0) \rightarrow ans = l_{limit}+n - 1
else \rightarrow ans = l_{limit} + 2*row - n-1
For those who want to take a deeper look how I derived them and test.
Detailed Approach
row time time
1 | 1 || 0 1 | 2
2 | 3 || 0 1 2 1 | 6
3 | 7 || 0 1 2 3 2 1 | 12
4 | 13 || 0 1 2 3 4 3 2 1 | 20
5 | 21 || 0 1 2 3 4 5 4 3 2 1 | 30
-
If you can observe, the left part of the sequence
1,2,3,4,5...is the row and right part of the sequence2,6,12,20,30...is maximum time it takes to reach the end of the sequence. I considered that to reach starting of the sequence which is ‘0’ costs 1 unit of time, however in the finial answer I subtracted 1. -
The first occurrence of any number x in the sequence is at x^{th} row. Like for first occurrence of 2 is in the 2^{nd} row, 3 is in the 3^{rd} row and so on…
-
For every x when 0 < x < row in the row^{th} row, x exists twice. And for x = row and x=0, it occurs only once. For example, in 4^{th} row 4 and 0 occurs only once and \{1,2,3\} occurs twice.
-
For any given row the time it takes to reach the end of the row is r_{limit} = row * (row+1) units where r_{limit} is the maximum units of time taken for any number x in the row^{th} row of the sequence. Example, to reach to the end of 4^{th} row it takes (4)*(4+1)=20 units of time.
(Actually 19, but since we considered it takes 1 unit of time to reach the starting of the sequence ‘0’ so as it takes 20, however like I mentioned I would subtract in the finial answer) -
Similarly, for any given row the starting time it takes to reach start of the row is l_{limit} = (row-1)^2 + row. Again l_{limit} is the minimum units of time taken for any number x in the row^{th} row of the sequence. Example, to reach to the end of 4^{th} row it takes 3*3+4=13.
(Actually 12, but since we considered it takes 1 unit of time to reach the starting of the sequence ‘0’ so as it takes 13, however like I mentioned I would subtract in the finial answer). -
To calculate on which row our k^{th} occurrence of n when n = 0 is row = k and when n \ne 0, is calculated like
row = n + \Large (\frac {(k-1)}{2}) \normalsize + (k-1) - 2*\Large (\frac {(k-1)}{2}) (every division here is a integer division).
For example, n=3 and k=4 then
row = 3 + \large \frac 32 \normalsize + 3 - 2 *\large \frac 32
row = 3 + 1 + 3 - 2*1
row = 5 , which is true. -
Since, l_{limit} and r_{limit} are dependent on row, and now we got the row from given k. It’s easy from here to calculate the units of time. If k is even or n=0 then ans = l_{limit}+n - 1 if not then ans = l_{limit} + 2*row - n-1 (See, I subtracted the ‘-1’ from the answer because of the assumption that I took as it takes 1 unit of time to reach first number in the sequence which is 0).
Example, take n=4 and k=6 then
row = 4 + \large \frac 52 + \normalsize 5 - 2*\large \frac 52
row = 4+ 2 +5 - 2 *2
row = 7
r_{limit} = (7) *(7+1) =56
l_{limit} = (6)^2 + 7 = 36 + 7=43
Since, k\%2 =0 our answer is ans = 43+4-1=46
My Submission:-
https://www.codechef.com/viewsolution/32382129
My Code:-
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int t, n, k, row, l, r, ans;
cin >> t;
while( t-- )
{
cin >> n >> k;
if( !n ) { row = k; }
else { row = ((n + --k/2)%mod + (k - 2*(k/2)))%mod; }
r = (row * (row+1))%mod;
l = (((row-1) * (row-1))%mod + row)%mod;
if( k % 2 or !n )
{
ans = (l + n)%mod;
}
else
{
ans = (l + (row + (row-n))%mod)%mod;
}
cout << ans - 1;
if( t )
{
cout << '\n';
}
}
return 0;
}
