USACO 2023 Bronze December Solutions

OwenChen · February 4, 2024, 9:02pm

USACO 2023 December Contest, Bronze

Problem 1. Candy Cane Feast

http://www.usaco.org/index.php?page=viewproblem2&cpid=1347

Dr. Chen’s C++ solution:

owenjchen/usaco/blob/main/bronze_2023Dec/usaco2023b_dec_p1.cpp

/*
    Author: Dr. Owen Chen
    Datetime: 2023-12-16 09:57
    USACO 2023 December Contest, Bronze
    Problem 1. Candy Cane Feast
    http://www.usaco.org/index.php?page=viewproblem2&cpid=1347

    Dr. Chen's Analysis:
        - Cow heights and candy heights are large numbers [1, 10^9].  Need long long numbers
        - Feed one candy for all cows.  Keep tracking of current candy height.
        - When a candy is finished, hang the next candy.  Cows will start in the same order from the first cow
          instead of the next cow to the last fed cow.
        - Algorithm:
            - Read N, M
            - Read N cows
            - Two loops M * N:
                - Loop over each candy of M:
                    - read candy cane height: cane
                    - set current candy lowest level at 0  (current_height)
                    - Loop over each cow j of N:

This file has been truncated. show original

Problem 2. Cowntact Tracing 2

http://www.usaco.org/index.php?page=viewproblem2&cpid=1348

Dr. Chen’s C++ solution:

github.com

owenjchen/usaco/blob/main/bronze_2023Dec/usaco2023b_dec_p2.cpp

/*
    Author: Dr. Owen Chen
    Datetime: 2023-12-16 09:57
    USACO 2023 December Contest, Bronze
    Problem 2. Cowntact Tracing 2
    http://www.usaco.org/index.php?page=viewproblem2&cpid=1348
    
    Dr. Chen's Analysis
    - Consider corner cases first
        - corner case 1: all infected
        - corner case 2: 0, 1 or 2 infected
    - General case: 3 or more infected:
        - bateria started from the left side
        - get cows infected from the left side:
            left = # of cows infected on the left
        - bateria started from the right side:
            right = # of cows infected on the right
        - bateria started in the middle:
                min_infected = 0;
                int growth = 2*min_nights + 1;

This file has been truncated. show original

Problem 3. Farmer John Actually Farms

http://www.usaco.org/index.php?page=viewproblem2&cpid=1349

Dr. Chen’s C++ solution:

github.com

owenjchen/usaco/blob/main/bronze_2023Dec/usaco2023b_dec_p3.cpp

/*
    Author: Dr. Owen Chen
    Datetime: 2023-12-16 09:57
    USACO 2023 December Contest, Bronze
    Problem 3. Farmer John Actually Farms
    http://www.usaco.org/index.php?page=viewproblem2&cpid=1349

    Dr. Chen's Analysis
    - Use long long for h & g since they involces a product of two integers (growth * days)
    - Define a data structure for Plant:
      struct Plant {
          ll h;
          ll g;
          int t;
        };
    - Consider corner case: N = 1 :
        output 0 if plants[0].t == 0
        else output -1
    - Consider corner case: N = 2:
      - sort two plants based on t

This file has been truncated. show original