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
When I compile with checks for overflow it doesn’t report any.
Instead I think the issue is taking the modulo of a negative number. In C++ the modulo of a negative number remains negative; as an example:
-4 % 3 = -1
instead of
-4 % 3 = 2
Often when the modulus can be negative it is normal to do
((val % mod) + mod) % mod;
At the moment I don’t have time to look if there are other issues, but first try to change the modulo operator
hey, I came to this thread as I was unable to understand the logic of the coder in the main thread, however even here I am still unable to understand as to why you’ve taken 210^6 as the length for the golomb array in your code, I mean it makes sense for the other 2 arrays as they are storing the indices of first occurrence and the sum, however this array actually holds the real elements of the golomb sequence so shouldn’t this be of capacity ->10^10 (IK it would give a TLE then, but I am unable to understand why the logic with 210^6 works). Kindly help 
The important property of the golomb sequence is that \texttt{golomb}_i is the number of occurances of i in the golomb sequence. I generate the golomb sequence up to the point where what I have generated is enough to describe the whole sequence. As a result of the property we know that
\texttt{golomb}_i=k\iff\sum_{j=1}^{k-1}\texttt{golomb}_j<i\text{ and } \sum_{j=1}^k\texttt{golomb}_j\geq i
(I may have an off by one error in the above formula, but it’s the idea it represents that matters)
So for indexes up to 10^{10} we can use the cumulative golomb sequence to find the value of the golomb sequence there. And it turns out that the cumulative golomb sequence goes past 10^{10} somewhere before 2\cdot 10^6
By the way, if you want to know why half of your reply turned to italic, read this
alright I guess I got your point! however I implemented it and it works fine for known values however it’s giving WA. IDK where i’ve gone wrong, could you help me in solving this issue. thanks in advance! here is my solution giving WA :CodeChef: Practical coding for everyone
even if I could get for what value the wrong answer is being computed, that would be a big help as I’ve tried a lot of random numbers in the entire range and the value seems to be accurate ( I referred to @spaanse code for correct values).
Our programs give different output for
1
1 6
What I am unsure about is what is stored in v1. Your comment suggests that it is the golomb sequence (because it is self-describing), but then you start it with 0,1,2,4 instead of 0,1,2,2. In my algorithm I do the binary search for boundary over the cumulative golomb sequence, so that the index returned is golomb[boundary]. But v1 in your code also isn’t the cumulative golomb sequence as that starts 0,1,3,5.
v1[i] basically gives the indices of the 1st occurrence of i in the golomb.
v1[1]=1 … because 1 occurs at 1st place.
v1[2]=2. the first occurrence of 2 is at 2nd indices
v1[3]=4 and so on
hey! it finally worked 
… seriously more than happy… turns out the problem was in my mod calculation I tweaked the code a bit and it worked like magic…
I particularly liked the way you deal with MOD … could you tell me how to learn all of that ? I mean that style of coding it seriously is great. and thanks a ton again, this wouldn’t be possible without your help! . the working code: CodeChef: Practical coding for everyone
Mod struct
In the Mod blob there is actually not a lot of unique code. It mainly consists of operator overloading to enable me to use the Mod struct (mostly) as if it were an integer.
I will go trough the different sections
Mod(...) - These are constructors; they initialize the class.
Mod& operator=(...) - this defines what happens when you do Mod a = b
Mod& operator@=(...) - These define arithmetic operations, if you want you can reformat that to understand what I do there. For the operator/= I make use of Fermat’s little theorem
bool operator@(...) - These are comparisons. While only the == and != make sense for modular arithmetic, I added the other four to be able to sort Mod’s.
explicit operator type() - These define how to (explicitly) cast a Mod to a bool or long long.
friend Mod operator@(Mod lhs, ...) - These define the operations +,-,*,/; contrary to the +=,*=,-=,/= previously found these create a new Mod with the result of the operation
friend Mod operator@(ll lhs, ...) - This defines how to add a Mod to a long long. Note that I don’t have to define the same function for the arguments in reverse order; that is already done by one of the constructors and the operator between two Mods.
friend bool operator@@ - similarily allows comparison between long longs and Mod’s
friend Mod pow(Mod base, ll exp) - fast exponentiation
friend ostream& operator<<(...) Allow the object to be printed
friend istream& operator>>(...) Allow the object to be read in
A couple of things I want to point out:
- In the arguments you will often find an ampersand (&) after the type name. This means that the argument is passed by reference instead of by copy. This is faster, especially when calling with a more complex container (for example with a vector \mathcal{O}(1) instead of \mathcal{O}(n). In C/C++ arrays are always passed by reference so that is why you had no TLE issues from that in your code.
- the keyword
constoccurs a lot. This points out to the compiler that a given object doesn’t change. It is especially advised if you pass by reference to get the advantage of quick calls without the risk of introducing weird bugs.
Code quality
Contrary to most CP coders I don’t use macro’s. Macro’s are one compiler feature that really decreases the readability of code. Instead I use a feature in my editor (ST3) named snippets. Snippets are like tab-completions, but a little nicer. For example to make a for loop I only have to type for<tab><tab>n<tab> to create
for (int i = 0; i < n; i++) {
/* code */
}
The first tab indicates: execute the snippet for. This inserts the for loop and highlights the three occurances of i. If I want I could rename it but it is fine as it is.
The second tab goes on to highlight the variable count which I change to n.
The third tab is the last of the snippet and highlights the comment /* code */ so that that automatically disappears if I want some real code in there.
All of that is defined using the following bit of XML
<snippet>
<description>For Loop</description>
<content><![CDATA[for (int ${1:i} = 0; $1 < ${2:count}; $1++) {
${0:/* code */}
}]]></content>
<tabTrigger>for</tabTrigger>
<scope>source.c, source.objc, source.c++, source.objc++</scope>
</snippet>
Some of my own snippets:
-
init<tab>to create the main structure of the program (includes, typedefs and main). -
Mod<tab>to create the Modular arithmetic class -
UFDS<tab>to create a Union find class.
Furthermore I try to give everything understandable names. With that I am able to quickly program an algorithm in a contest that still remains readable. I have once heard that Competitive programmers, whilst more likely to score a job at a big company, often perform worse than their coworkers who did not do CP. One of the main reasons being poor code quality. I try my best to avoid that.
3 Likes
thanks a ton! this explanation was really crisp…I’ll try to keep my code readable too. I get the underlying idea of how CP people tend to shorten the code so much and/or use variable names making them hard to read and reducing code reusability as well as readability. That was quite informative! Thanks again!