No problem.
The 6 star feels weird. I have gotten so used to 5 star that the orange feels out of place. Might take some getting used to it.
2 Likes
Hey, now you have learned about the trapv pragma. It was also the first time that I tried that pragma and I am amazed how quickly it spotted the error. And now you know that you could have solved this problem with what you already knew.
3 Likes
Yeah thanks
i am never using int again in my whole life
I made the same mistake. Not gonna use ints anymore XD
1 Like
Can you please explain 3rd case in Golomb Sequence. Why did you do i*i and what GB[i+1]!=GB[i] means?
1 Like
I have rephrased the definition of the third array a bit. It was indeed stated confusingly/incorrectly.
For naming let’s call that array preAns. Then
\texttt{preAns[i]}=\sum_{j \text{ for which } \texttt{golomb[j]}\leq i} \texttt{golomb[j]}^2=\sum_{j=1}^i\texttt{golomb[j]}\cdot j^2
This way if we want the ans for a range 1\ldots R, i.e. we want to calculate \sum_{i=1}^R\texttt{golomb[i]}^2, and we now that \texttt{golomb[R]}=v we can split this sum up:
\sum_{i=1}^{\texttt{GC[v-1]}}\texttt{golomb[i]}^2+\sum_{i=\texttt{GC[v-1]}+1}^R\texttt{golomb[i]}^2 = \texttt{PreAns[v-1]}+(R-\texttt{GC[v-1]})v^2
2 Likes
Can you please describe why you took array length to be 60 in the first problem? Thanks
That was left over when I tried saving it in the total length. I believe it could be 30/31.
The length could be 30/31 because Ai has maximum value of 2^30 right?
I believe so, try it.
Thanks for the beautiful explanations.
brother ,i am not able understand this equation
can you pls explain how you made the observation
If Ai has m bits and Aj has n bits, then the two possible binary concatenations of Ai and Aj will be Ai*2n + Aj and Aj*2m + Ai. Subtract the two and you’ll get the said result
2 Likes
How did you come up with this logic for BINFUN? I just could not think of any approach except brute force 
Lots of trial and error. Some other approaches that didn’t work:
- take the largest and smallest element → doesn’t work, as the second example case shows
- take the largest and smallest element when you remove the leftmost bit → again doesn’t work for the second example
That let me into looking into why the second example used the smallest element first, instead of a larger element. From there I got the approach to look at the contribution of each element for different shifts
i dont get why it shows time limit exceede:-
#include
#include
#include
#include
#include
using namespace std;
int main(){
long long t{},maxy{1000000007},maxs{-1},sum{1};
vector result{};
vector sums{1};
vector position{};
cin>>t;
for(long long i{};i<t;i++){
long long l{},r{};
cin>>l>>r;
position.push_back(l);
position.push_back®;}
for(long long i{1};i<position.size();i=i+2){
if(position[i]>maxs)
maxs = position[i];}
vector <long long> g{0,1};
for(long long j{2};j<=maxs;j++){
long long h{};
h = 1+g[j-g[g[j-1]]];
g.push_back(h);
sum = (sum + g[j]*g[j])%maxy;
sums.push_back(sum);}
for(long long i{0};i<position.size();i=i+2){
if(position[i]!=1)
sum = sums[position[i+1]-1]- sums[position[i]-2];
else
sum = sums[position[i+1]-1];
result.push_back(sum);}
for(long long c:g){
cout<<c<<" ";
}
cout<<endl;
for(long long c:result)
cout<<c<<endl;
}
here is the formatted code of golomb ,shows time limit exceeded:-
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
long long t{},maxy{1000000007},maxs{-1},sum{1};
vector <long long> result{};
vector <long long> sums{1};
vector<long long> position{};
cin>>t;
for(long long i{};i<t;i++){
long long l{},r{};
cin>>l>>r;
position.push_back(l);
position.push_back(r);}
for(long long i{1};i<position.size();i=i+2){
if(position[i]>maxs)
maxs = position[i];}
vector <long long> g{0,1};
for(long long j{2};j<=maxs;j++){
long long h{};
h = 1+g[j-g[g[j-1]]];
g.push_back(h);
sum = (sum + g[j]*g[j])%maxy;
sums.push_back(sum);}
for(long long i{0};i<position.size();i=i+2){
if(position[i]!=1)
sum = sums[position[i+1]-1]- sums[position[i]-2];
else
sum = sums[position[i+1]-1];
result.push_back(sum);}
for(long long c:g){
cout<<c<<" ";
}
cout<<endl;
for(long long c:result)
cout<<c<<endl;
}
The final answer comes out to be negative(overflow) if i take the value of R to be 10^6 and above.Please help.
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
vector <long long> result{};
long long T{},maxy{1000000007};
long long unsigned L{},R{};
cin>>T;
for(long long i{};i<T;i++){
cin>>L>>R;
long long sum1{1},sum2{1};
long long unsigned counts{1},j{2};
vector <long long> g{0,1};
while (counts<L-1){
long long h{};
h = 1+g[j-g[g[j-1]]];
g.push_back(h);
sum1=(sum1+(j*j*g[j]))%maxy;
counts=counts+h;
j+=1;}
if (L==1){
sum1=0;}
else if (counts%(L-1) != 0){
sum1=(sum1-((counts%(L-1))*((g.size()-1)*(g.size()-1))%maxy));}
else{
sum1=sum1;}
vector <long long> gs{0,1};
j=2;
counts=1;
while (counts<R){
long long h{};
h = 1+gs[j-gs[gs[j-1]]];
gs.push_back(h);
sum2=(sum2+(j*j*gs[j]))%maxy;
counts=counts+h;
j+=1;}
if (counts%R!=0){
sum2=(sum2 - ( (counts%R) * ( (gs.size()-1) * (gs.size()-1) )%maxy) );}
result.push_back(sum2-sum1);}
for (long long key : result){
cout<<key<<endl;
}
}
```I don’t think you need to output the golomb sequence itself
You don’t need to add {} after each variable. It is more common to do
long long l,r;
And if they need to have starting values
long long l=5, r=7;
But those are not the reason for TLE. As a rule of thumb a computer can perform 10^9 operations per second. In your approach you calculate the golomb sequence until the largest index requested. However this largest index can be up to 10^{10}, which would mean a runtime of roughly 10 seconds → TLE. Even for the first subtask it is going to be tight. For a feasable solution the calculated number of operations would lay around 2\cdot 10^8
1 Like