## Editorial for CCC '17 S3 - Nailed It!

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Authors:

,For up to out of the available marks , a simple algorithm which iterates over each pair of the pieces of wood in the input suffices.

**Time Complexity:**

For the full marks, we make the observation . This means we can iterate over every (unordered) pair of **lengths** of pieces of wood available and add it to the corresponding total for a length of board made. Since each length of wood can be uniquely paired up with another length of wood to create a corresponding length of board, no pairs are over-counted this way. Finally, we can iterate over every possible board length to determine the length of the longest fence and the heights of all fences which have that length.

**Time Complexity:**

#### Sample Solution — D

```
import std.stdio;
alias ll = long;
int N;
ll ans1, ans2;
ll[2004] buckets;
ll[4004] sums;
void main() {
scanf("%d", &N);
for (int i=0, a; i<N; i++) {
scanf("%d", &a);
buckets[a]++;
}
for (int i=1; i<=2000; i++) {
if (buckets[i]) {
for (int j=i; j<=2000; j++) {
if (i == j) {
sums[i + j] += buckets[i] >> 1;
} else if (buckets[j]) {
sums[i + j] += min(buckets[i], buckets[j]);
}
}
}
}
for (int i=1; i<=4000; i++) {
if (sums[i] > ans1) {
ans1 = sums[i];
ans2 = 1;
} else if (sums[i] == ans1) {
ans2++;
}
}
printf("%ld %ld", ans1, ans2);
}
```

## Comments

Could you please explain the logic behind the last for loop?

I don't really understand how that works. I tried to draw it out:

And I walked through the for loop step by step, updating

`ans1`

and`ans2`

each time:But I can't figure out

whythat works.The sums array represents the longest fence that can be achieved for each possible height, and since you are trying to maximize the length of the fence, you want to pick the greatest value in the sum array (which is ans1), but you also need to determine how many heights will produce this length. This is done by incrementing a counter (ans2) each time the value in the sum array is equal to the best length so far. But once you find a better length, you reset this counter to 1 because you know the only value in the sum array with this new ans1 is the current one.

Oh okay, but for the

`sums`

array, why do you have to divide by 2 if`i`

and`j`

are equal?Think about the number of ways to pair up the pieces of wood.

If you are trying to pair up pieces with length and where , the number of fences you can make is bounded by the number of pieces with length and the number of pieces of length , so you take the smaller of the two.

If , then to form a fence, you are pairing up pieces of the same length. The number of fences you can make is bounded by the number of pairs, which is .

I'm having trouble working through the first algorithm (iterating over pairs). Can someone please help? I've tried using combinations through the itertools library in Python, but no success. Thanks.

I am kind of new to C++,can you expain what you mean by bucketp[i] >> 1?

`<<`

and`>>`

are bit shift operators. That means that when an number is expressed in binary, the bits are all shifted in the direction of the arrows (with 0 being placed on the ends).`>> 1`

can be thought of as dividing by 2 while`<< 1`

can be thought of as multiplying by 2.Also note that

`x >> 1`

is not the same as`x/2`

if`x`

is a negative number, but since the value of`buckets[i]`

will always be at least 0, the two are equivalent.I’m still confused

Here's an example.

if we have a number 11000 in base 2 (which converts into 24 in base 10) and we use the right bit shifter on it, all of the digits in the number will shift right. 11000 >> 1 = 1100, 1011 >> 1 = 101, 0 >> 1 = 0

Here's an article on bit shift operators in c++: https://www.geeksforgeeks.org/left-shift-right-shift-operators-c-cpp/