# Unofficial Editorial Div 1 July lunchtime 2020

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;

}

Could you format as code?

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;

}


#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
-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 :https://www.codechef.com/viewsolution/36171400

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: https://www.codechef.com/viewsolution/36171800

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

1. 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.
2. the keyword const occurs 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