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 out of the 15 available marks (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)

For the full 15 marks, we make the observation 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)

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


  • 2
    DynamicSquid  commented on Dec. 21, 2020, 3:16 p.m. edited

    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.


    • 5
      ross_cleary  commented on Dec. 21, 2020, 3: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, 1: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, 2: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 and j where i\neq j, the number of fences you can make is bounded by the number of pieces with length i and the number of pieces of length j, so you take the smaller of the two.

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


  • 2
    vishnus  commented on Sept. 5, 2020, 9:17 a.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.


  • 11
    h1369836197  commented on July 19, 2017, 9:45 p.m.

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


    • 9
      wleung_bvg  commented on July 20, 2017, 3: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.


      • 18
        Kirito  commented on July 20, 2017, 11:21 a.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.


        • 24
          Dordor1218  commented on April 5, 2018, 8:49 p.m.

          I’m still confused