Chef and Walk editorial (UNOFFICIAL)

[crap_the_coder]

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!

[ash432]

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

[wigglebuggy123]

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

[crap_the_coder]

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)

[crap_the_coder]

Done!

[ash432]

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

[eddie_code5]

@crap_the_coder,

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

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…:pray: I spent hours and …

[crap_the_coder]

Sure, will check!

[crap_the_coder]

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!

[ash432]

Understood

[sps100]

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;

}

[crap_the_coder]

Could you please provide a link to your submission?

[sps100]

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

[das_rohan4]

#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

[crap_the_coder]

Your code fails for this testcase:

1
0 100000

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

[eddie_code5]

Dude,

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

[crap_the_coder]

[al_ankit007]

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

}

[crap_the_coder]

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

[al_ankit007]

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