Unofficial Editorial Div 1 July lunchtime 2020

BINFUN - Binary concatenation - Submission

Finding the maximum difference between a pair of elements from an array is a classical problem. It comes down to finding the maximum value and the minimum value and taking the difference between the two.

But we need to adapt that approach to this problem; just finding the maximum and minimum doesn’t work, the other item of the pair influences the contribution made by the first item.

Suppose (A_i,A_j) is the optimal pair. let A_i have n bits and A_j have m bits. Then the BinaryConcatenation of them will be A_i(2^m-1)-A_j(2^n-1). The contribution of each element depends only on the number of bits in the others representation. Instead of looping over each pair of elements we can instead loop over each element and the number of bits in the other.

I used two arrays maxValues[60][60] and minValues[60][60] that in each cell at index [i][j] contains the maximum and minimum contribution for values with i bits and we assume the other value has j bits. Then I loop over all possible pairs (i,j) and find the maximum value of maxValues[i][j] - minValues[j][i].

GOLOMB - Golomb Sequence - Submission

I precalculate three arrays:

  1. The golomb sequence GB
  2. The cumulative golomb sequence GC. Due to how the golomb sequence is define GC[i] will be the index of the last occurance of i in the golomb sequnce
  3. The sum of squares of the golomb sequence for each range 1...GC[i]. I give a better definition of this array in a comment below

This can be done quite trivially. For (1) use the recursive definition from the statement. For (2) the standard approach for calculating the cumulative array. For (3) add golomb[i] * i * i to the previous value

Then answering queries becomes rather simple. For the range L...R calculate the answer for 1...R and 1...L-1, their difference is the answer. Now if we want to find the answer for 1...R we first use binary search on GC to find the value v at index R. We then observe that the difference for 1...R and 1...GC[v-1] is a sequence of only v's, of which it is trivial to calculate their sum of squares. The answer for 1...GC[v-1] was already calculated in (3)

PRT2 - Profitable Paths 2 - Submission

The main observation is that we want to find the shortest path between two leaf nodes. By doing so we can visit the large values as often as possible. We find the shortest leaf-leaf distance by running a BFS starting at all leafs. Whenever we encounter a node that was already visited we have our shortest path of length l.

Now we can think of the graph as a line graph with l nodes. On this graph we can only walk back and forward. We first calculate how often we can walk from the start to the end and back (\lfloor K/2l\rfloor). We also calculate twice the sum of the l largest values. The product of those gets us most of the way to finding the answer. We only need to figure out how to use the remaining K\mod 2l steps.

This is done by walking from a node somewhere in the middle, to an end and then back to the node we started (or one further). This way we can visit the largest values twice. Note that if the remaining K is greater than 2 we can visit the largest value twice, but if it is exactly 2 we can’t. Make sure to consider that edge case.

POPF - Pairs of Pairs

Not attempted

COPAIR - Coloured Pairs

Not attempted

Could you figure out what is wrong in this code
I tried a very similar approach to yours
I just need a counter case

Have you tried the example cases?
I think you should not do the l+1 and r+1 in lower_bound and you might need to look at cases where the range starts at one.

I too thought of that
and submitted another solution in which i have taken l and r instead of l+1 and r+1, rest same
So i think that is not the issue

Then I am not sure.
If you want to try random test cases, here is my submission

That big ugly block at the top is a self-made class Mod that takes care of all modular arithmetic. It makes it so that I can use modular arithmetic as if they are normal integers.

1 Like

OK :+1:

on test case
1 10000000000
my answer is 258479624 which is wrong as your answer is 123983151
God knows why

Found the issue.

From another discussion thread, place the following at the start of your code

#pragma GCC optimize "trapv"

and compile. This will instruct to fail whenever an integer overflow occurs.
Then running in GDB we find that it fails at line 31. This is because i is an integer and therefore too small to fit i*i, change to an long long an it will work.


oh fuck me fuck me fuck me fuck me

1 Like

Nice editorial. And 6 star! Congrats.


Now it gives AC
changing int to ll
Thanks for pointing it out :sob:

1 Like

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.


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.


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

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?