Chef and Walk editorial (UNOFFICIAL)

Problem statement: https://www.codechef.com/RC122020/problems/RECNDNUM
My solution: https://www.codechef.com/viewsolution/32359646


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 :smiley:
And feel free to ask any doubts or give me any suggestion! :smile:

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! :slight_smile:

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

@crap_the_coder,

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

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;

}

Could you please provide a link to your submission?

Here is the GFG link of my submission :- https://ide.geeksforgeeks.org/vauNL7MTjh

#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 :confused:

Dude,

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

:rofl:

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";
}

}

Can you please send the submission link? Or please format your code properly.
Your code has been ruined by the markdown :confused:

#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";
}
}