BucketPotato's blog

Bay Area Programming Contest 2024 Uploaded to Gym
By BucketPotato, 8 months ago, In English

Hi Codeforces!

Thanks to the 76 people who came in person to the Bay Area Programming Contest this year, and of course our 29 virtual teams!

The contest has been uploaded to the gym here, and is available for virtuals or upsolving.

We hoped you enjoyed the problems as much as we enjoyed organizing! Please let us know in the comments if you have any questions or concerns.

UPDATE: the model solutions (and some extras) to all problems are posted at this link.

UPDATE: written editorial is now available here.

  • Vote: I like it
  • +139
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Great contest, loved the food. Looking forward to next year!

→ Reply
»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

ench orz

→ Reply
»
8 months ago, # |
  Vote: I like it +41 Vote: I do not like it

tysm for the contest it was so fun :3

→ Reply
»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

ezraft orz

→ Reply
»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Really enjoy the contest! Hope it becomes 5-hours contest next year

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Thanks! We set it at 3 hours because we expected there to be many beginner teams that would have trouble working for a full 5 hours, but we'll see what feedback we get about this.

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Massive thanks to the organizers for a stellar event. The challenge was exhilarating, and we appreciate the opportunity for virtual participation and upsolving. Looking forward to more in the future

→ Reply
»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Great contest! First time participating in an in-person contest in around four years and it was so much fun meeting people :)

→ Reply
»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

much fun

lemonade pog organizers orz

→ Reply
»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

We had a lot of fun organizing and hope you enjoyed it!

→ Reply
»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

very fun contest good food balloons are fun we need a smaller difficulty gap :notlikeblob:

→ Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it +37 Vote: I do not like it

Very good problems, Especially B and J, recommend everyone to try.

I participated the contest all by myself, and ranked 13th finally. I solved 6 problems, almost 7 (finish E only 5 minutes after the contest end, and this solution get accepted at the gym). I am not sure if this result is good or not.

The only con of the contest is that it is too short. 3 hours is not enough, if we have 4 or 5 hours, this will be more close to real ICPC contest.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    As the author of J, you just validated my entire problemsetting career (after it was completely destroyed by Benq who solved G in 3 minutes 56 seconds in testing). Glad you liked the contest!

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thanks

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +42 Vote: I do not like it

        Just because you comment 1e9 times on the same blog does not mean your contribution will magically increase from -30 sir

        → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Great job!

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    can you help me how to solve B

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 3   Vote: I like it +25 Vote: I do not like it

      Use DP. Suppose the array B is 2,2,2,3,4,4, since the subarray in A may end at 0 or 1, so there the total states will be the product of each number frequency plus one in array B, and then times 2 for the last number (0 or 1). The example above shows the total number of states 4*2*3*2 = 48.

      Given the length of array A is at most 100, it can be approved that the number of states is very finite, since 100 can at most be formed by 13 distinct numbers. I don't know what is the maximum state possible, but my python solution O(nM) (M is the number of states) passed in 1300 ms.

      → Reply
»
8 months ago, # |
  Vote: I like it +62 Vote: I do not like it

As an organizer give me contribution.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me B

→ Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I enjoyed eating 1e9+7 slices of pizza at BAPC.

→ Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Grateful for the unforgettable Bay Area Programming Contest experience! Huge thanks to the organizers for seamlessly blending virtual participation with in-person excitement. Can't wait to tackle those problems again

→ Reply
»
8 months ago, # |
  Vote: I like it +40 Vote: I do not like it

I would like to say this contest is amazing.

As a non-precollege contestant, I really enjoyed the contest.

T-shirts, contest area, food, problems, problems analysis. Everything were great.

The only pity is that I didn't win it :(

Congrats to the winners.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah the problems were good, specifically i liked the B problem

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

more bapc prizes when??

→ Reply
»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

what's the worst-case time complexity of a DP solution for B? I got confused analyzing that but I guessed it may pass and it did.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    The number of states in our model solution is exponential, but writing a DP to count the worst-case number of states gets us around $$$2 \cdot 10^5$$$. Code included here (which we also used to generate some of the tests):

    Code
    → Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Actually I found the practice contest problems are interesting.

Is there a gym for trying the practice contest problems?

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Yo!

→ Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Is there any written solutions? I'm pretty curious about the solution to problem A and C.

→ Reply
»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

On Problem C's editorial:

"While slower solutions did not pass directly, some contestants managed to solve the problem by precomputing the answers with a slower algorithm, then hardcoding them.".

Is this possible on Codeforces? I thought on doing that but the file size I got precomputing pass by far the 64KB limit on codeforces. I would need around $$$P \times 2 \times 10^4$$$ bytes. Where P is the precision I set for the answer, which I believe is around $$$15$$$. Is there some trick to reduce the file size?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    first of all, you are not required to store all the anwsers, for example, $$$n \le 500$$$ can be calculated online.

    secondly, it only cares about relative errors, so maybe you just set the lower precisions i think

    → Reply