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. 
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?
#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";
}
}
Can you please send the submission link? Or please format your code properly.
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";
}
}