Editorial for CCC '17 S3 - Nailed It! - DMOJ: Modern Online Judge

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: Phoenix1369, Kirito

For up to $9$ ~9~ out of the $15$ ~15~ available marks $(N \le 1000)$ ~(N \le 1000)~, a simple algorithm which iterates over each pair of the pieces of wood in the input suffices.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the full $15$ ~15~ marks, we make the observation $1 \le L_i \le 2000$ ~1 \le L_i \le 2000~. 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: $\mathcal O(N + {L_i}^2)$ ~\mathcal O(N + {L_i}^2)~

Comments

DynamicSquid commented on Dec. 21, 2020, 8:16 p.m. ← edit 3 →

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

for (int i = 1; i <= 4000; i++) {
    if (sums[i] > ans1) {
        ans1 = sums[i];
        ans2 = 1;
    } else if (sums[i] == ans1) {
        ans2++;
    }
}

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

Input:
4
1 2 3 4

Sum: [ 0, 0, 0, 1, 1, 2, 1, 1 ] // # of occurrences of each sum

And I walked through the for loop step by step, updating ans1 and ans2 each time:

i    = 1 2 3 4 5 6 7
ans1 = 0 0 1 1 2 2 2
ans2 = 1 2 1 2 1 1 1

But I can't figure out why that works.

4

ross_cleary commented on Dec. 21, 2020, 8:55 p.m. ← edited →

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.

2

DynamicSquid commented on Dec. 22, 2020, 6:32 p.m.

Oh okay, but for the sums array, why do you have to divide by 2 if i and j are equal?

3

Kirito commented on Dec. 22, 2020, 7:41 p.m.

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

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

If $i = j$ ~i = j~, 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 $\left\lfloor\frac{\#i}{2}\right\rfloor$ .

0

vishnus commented on Sept. 5, 2020, 1:17 p.m.

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.

12

h1369836197 commented on July 20, 2017, 1:45 a.m.

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

7

wleung_bvg commented on July 20, 2017, 7:14 a.m.

<< 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.

16

Kirito commented on July 20, 2017, 3:21 p.m.

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.

31

Dordor1218 commented on April 6, 2018, 12:49 a.m. ← edited →

I'm still confused

4

Evang commented on Sept. 4, 2020, 4:34 p.m. ← edit 2 →

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/