# Chef and Walk - RECNDNUM - WA

Problem:-

@crap_the_coder

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 sequence 2,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;
}


Yet another overflow issue

1
0 1000000000


The output is supposed to be 56, but your output goes negative.

Other than that, I think you solution is correct.

1 Like

-_- let me go get that AC now.

1 Like

besides that, don’t you think it’s like another editorial?

1 Like

Yeah

Changed it and yet still no AC

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

2 Likes

Bro, gg, respect++

I never had to deal with such ans \% something with such strict trest cases so far, thanks…