# Chef and Walk editorial (UNOFFICIAL)

Problem statement: CodeChef: Practical coding for everyone
My solution: CodeChef: Practical coding for everyone

To understand the solution, you need to know the size of each, let’s say ‘chunk’

``````Chunk 1 = 0 1: Size = 2
Chunk 2 = 0 1 2 1: Size = 4
Chunk 3 = 0 1 2 3 2 1: Size = 6
...
``````

Now, solving for:

N * N

The first time N occurs is during the time N*N. Here’s why:
A number N will first occur in the Nth chunk at the Nth index.
The index will be 2 + 4 + 6 + ... (for N-1 times) + N(we need to add the index as well)

Let’s distribute N to all the N-1 numbers.
Then, it’ll be 3 + 5 + 7 + ... (for N-1 times) + 1 since we have a leftover.

Now, the sum is 1 + 3 + 5 + ... (for N times).
The sum of the first N odd numbers = N*N

Floor(K/2) * 2*N

Notice the differences between the last index of any number in a chunk and the first index of the same element in the next chunk. It’s always 2*Number. And that will occur Floor(K/2) times when finding the Kth occurrence.

So, we have to add Floor(K/2)*2*N.

Ceil(K/2) * Ceil(K/2-1)

Note: We have to remove Floor(K/2) from K (since it was taken care of above), which would be Ceil(K/2).

We only have to add the differences of the first index of an element and the last index of an element in each chunks. Notice that the differences start at `0` and increase by 2 for every chunk after it. Therefore, the sum will be:

`0 + 2 + 4 + 6 ...` for Ceil(K/2) times

That is equal to Ceil(K/2) * Ceil(K/2-1)

And therefore, we get the formula N*N + Floor(K/2) * 2 * N + Ceil(K/2) * Ceil(K/2-1)

The only exception if for `0`, in which case you have to print K*(K-1)

Hope you understood my editorial!

Also, do rate this post, since it’s my first time writing an editorial
And feel free to ask any doubts or give me any suggestion!

11 Likes

Its unrelated to the editorial but can you find that for any given T (time) what will be the value of N?

1 Like

@crap_the_coder please explain more The first time N occurs is during the time
also next steps.

1 Like

It took me some time, but I finally figured it out.

First, find which chunk time is in. You have to use quadratic equations to do that.
chunk = (1 + sqrt(1 + 4 * t)) * 1/ 2

Now, to find the index of the chunk, use
index = time - chunk * (chunk - 1)

Make sure to reverse the direction once it reaches the middle
If index > chunk: index = 2 * chunk - index

Code (Python):

``````t = int(input())

chunk = (1 + int(sqrt(1 + 4 * t))) // 2

index = t - chunk * (chunk - 1)

if index > chunk:
index = 2 * chunk - index

print(index)
``````
1 Like

Done!

How did you get the formula for the chunk? By the way your solution is right.

Dude, Help me and I’ll be in your debt…

Sure, will check!

1 Like

Recall that the chunks are

``````0 1
0 1 2 1
0 1 2 3 2 1
...
``````

Let’s say we know the chunk a number is in, and it’s called chunk.
Now, the time taken to reach `0` in that chunk is chunk * (chunk-1) as the values increase by 2.

chunk * (chunk-1) = chunk^2 - chunk

Now, to reverse that, plug in the time in the quadratic formula, where
a = 1
b = -1
c = t

The only thing you have to do is floor the sqrt

Hope you understood!

1 Like

Understood

Can u check where did i do wrong ?

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const long long MOD = (long long)(1e9 + 7);

ll solve(ll t)
{
ll n,k,start;cin>>n>>k;
if(n==0)
start=1;
else if(n>0)start=n;
//k–;
if(k==1)cout<<(n*n)%MOD;
else
{k–;
while(k>0)
{start++;
k-=2;
//start%=MOD;
if(k<=0)break;
}
if(k<0)
cout<<(((start-1)*start)+n)%MOD;
else
cout<<(((start-1)*start)+start+(start-n))%MOD;
}

``````if(t>0)cout<<"\n";
``````

}

int32_t main()
{
#ifdef ONPC
freopen(“input.txt”, “r”, stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll t;cin>>t;while(t–)
{
solve(t);
}

``````return 0;
``````

}

Here is the GFG link of my submission :- Online Compiler and IDE - GeeksforGeeks

#include<bits/stdc++.h>
#define ll long long int
ll m=1000000007;
using namespace std;
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n,k;
cin>>n>>k;
ll sum=0;
ll temp;
if(n==0)
{
ll y=(k*(k-1))%m;
cout<<y<<endl;
continue;
}
if(k%2==0)
{

``````		 temp=(k-1)/2+1;
temp=(temp+n)%m;

sum=((temp-1)*temp)%m;
sum=(sum+n)%m;
cout<<sum<< endl;

}
else
{
temp=(k-1)/2;
temp=(temp+n)%m;
sum=((temp-1)*temp)%m;
sum=(sum+(temp+temp-n))%m;
cout<<sum<<endl;

}

}
``````

}

can you tell what is wrong in my code. i tested it for like 15-20 test cases and its working just fine

Your code fails for this testcase:

``````1
0 100000
``````

I think it’s overflowing again, but I’m yet to figure out where

Dude,

It was like your 5^{th} time dealing with overflow cases… , guess I’ll never forget about handling overflow again.

What is the mistake in my code? getting WA … somebody help.

I have found the solution like … difference between two 0 appears at an AP of common difference 2 starting from 1 like 1,3,5…
or we can say the position of 0 to be 1,1+3,1+3+5…

and k element appears for the first time before k+1th 0…
and after that, it appears twice between two 0…

I wrote the solution based on this fact… first I calculated the 0 positions then subtract or add the k depend upon which side it will lie

Here is my code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 1000000007

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;cin>>t;
while(t–)
{
ll a,b;cin>>a>>b;a=a%m;b=b%m;
ll pos=a%m+1;
if(a==0)
{
ll a2=b%m-1;
ll h=((a2)*(a2+1))%m;
cout<<h%m;

``````	}
else
{
pos+=(b%m-1)/2;ll a1=pos%m-1;
pos=((a1)*(a1+1))%m;
if((b-1)%2==0)
cout<<((pos)-a)%m;
else
cout<<((pos)+a)%m;
}
cout<<"\n";
}
``````

}

Your code has been ruined by the markdown

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;cin>>t;
while(t–)
{
ll a,b;cin>>a>>b;a=a%m;b=b%m;
ll pos=a%m+1;
if(a==0)
{
ll a2=b%m-1;
ll h=((a2)(a2+1))%m;
cout<<h%m;
}
else
{
pos+=(b%m-1)/2;ll a1=pos%m-1;
pos=((a1)
(a1+1))%m;
if((b-1)%2==0)
cout<<((pos)-a)%m;
else
cout<<((pos)+a)%m;
}
cout<<"\n";
}
}