Bay Area Programming Contest 2024 Uploaded to Gym

Блог пользователя BucketPotato

Автор BucketPotato, 2 месяца назад, По-английски

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.

Анонс Bay Area Programming Contest 2024

+139

BucketPotato
2 месяца назад
45

Комментарии (45)

Написать комментарий?

hypeskynick

2 месяца назад, # |

+26

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

→ Ответить

fyan

2 месяца назад, # |

+21

ench orz

→ Ответить

wavelets

2 месяца назад, # |

+41

tysm for the contest it was so fun :3

→ Ответить

Ench_Lolz

2 месяца назад, # |

+27

ezraft orz

→ Ответить

scrg

2 месяца назад, # ^ |

+29

yahoo

→ Ответить

lxhgww

2 месяца назад, # |

+24

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

→ Ответить

BucketPotato

2 месяца назад, # ^ |

+37

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.

→ Ответить

tofael1104

2 месяца назад, # |

← Rev. 2 →

+26

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

→ Ответить

oursaco

2 месяца назад, # |

+29

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

→ Ответить

BucketPotato

2 месяца назад, # ^ |

+22

One could even say the contest was LIT...

→ Ответить

allusion

2 месяца назад, # |

+21

much fun

lemonade pog organizers orz

→ Ответить

ezraft

2 месяца назад, # |

+24

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

→ Ответить

maxrgby

2 месяца назад, # |

+26

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

→ Ответить

hxu10

2 месяца назад, # |

← Rev. 3 →

+37

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.

→ Ответить

ezraft

2 месяца назад, # ^ |

+35

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!

→ Ответить

tofael1104

2 месяца назад, # ^ |

+10

Thanks

→ Ответить

ezraft

2 месяца назад, # ^ |

+42

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

→ Ответить

tofael1104

2 месяца назад, # ^ |

T_T

→ Ответить

GusterGoose27

2 месяца назад, # ^ |

+16

Great job!

→ Ответить

thangdz2k7

2 месяца назад, # ^ |

+10

can you help me how to solve B

→ Ответить

hxu10

2 месяца назад, # ^ |

← Rev. 3 →

+25

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.

→ Ответить

sadboi2009

2 месяца назад, # ^ |

+20

thanks very much

→ Ответить

GusterGoose27

2 месяца назад, # |

+62

As an organizer give me contribution.

→ Ответить

tofael1104

2 месяца назад, # ^ |

Thank you so much

→ Ответить

thangdz2k7

2 месяца назад, # |

can anyone help me B

→ Ответить

eysbutno

2 месяца назад, # |

+15

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

→ Ответить

tofael1104

2 месяца назад, # |

+15

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

→ Ответить

liympanda

2 месяца назад, # |

+40

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.

→ Ответить

tofael1104

2 месяца назад, # ^ |

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

→ Ответить

tofael1104

2 месяца назад, # |

← Rev. 2 →

→ Ответить

allusion

2 месяца назад, # |

more bapc prizes when??

→ Ответить

Bucketsmith

2 месяца назад, # |

+25

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.

→ Ответить

BucketPotato

2 месяца назад, # ^ |

+18

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

#include "bits/stdc++.h"

using namespace std;

#define ll long long
const int M = 100;

// sum so far, last one
ll dp[M + 1][M + 1];
pair<int,int> pv[M + 1][M + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  dp[0][0] = 1;

  for (int i = 0; i <= M; i++) {
    for (int j = 0; j < M; j++) {
      for (int k = j + 1; k <= M; k++) {
        for (int l = 1; k * l + i <= M; l++) {
          ll nv = dp[i][j] * ((ll)(l + 1));
          if (nv > dp[i + k * l][k]) {
            dp[i + k * l][k] = nv;
            pv[i + k * l][k] = {i, j};
          }
        }
      }
    }
  }

  ll ans = 0;
  pair<int,int> st;
  for (int i = 0; i <= M; i++) {
    for (int j = 0; j <= M; j++) {
      if (dp[i][j] > ans) {
        ans = dp[i][j];
        st = {i, j};
      }
    }
  }

  cout << ans << "\n";

  vector<pair<int,int>> hv;
  while (st.first > 0) {

    int val = st.second;
    int diff = st.first;

    st = pv[st.first][st.second];

    diff -= st.first;

    hv.push_back({val, diff});

  }

  for (auto [x, y] : hv) {
    cout << x << " appears " << y / x << " times\n";
  }
  
}

→ Ответить

liympanda

2 месяца назад, # |

+15

Actually I found the practice contest problems are interesting.

Is there a gym for trying the practice contest problems?

→ Ответить

BucketPotato

2 месяца назад, # ^ |

+10

Yessir: https://codeforces.com/contestInvitation/7eaef6721133a047c0bd60a7ad9d97e41d81aa8c

→ Ответить

liympanda

2 месяца назад, # ^ |

+15

Thanks.

→ Ответить

XeF2

2 месяца назад, # |

-10

Yo!

→ Ответить

luanmenglei

2 месяца назад, # |

+15

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

→ Ответить

BucketPotato

2 месяца назад, # ^ |

+14

Sorry for the wait! We've just uploaded the written solutions to Dropbox.

→ Ответить

theRealChainman

2 месяца назад, # ^ |

+15

So great, thanks. Problem C is crazy.

→ Ответить

luanmenglei

2 месяца назад, # ^ |

+10

Thanks

→ Ответить

luanmenglei

2 месяца назад, # ^ |

+10

Is there any mathematical proof about the setting of $$$l$$$ in problem C?

This number seems like $$$\mathcal{O}(\sqrt{n})$$$ but I can't find out any reason about it.

→ Ответить

Chayannn

2 месяца назад, # |

да

→ Ответить

LipArcanjo

2 месяца назад, # |

+20

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?

→ Ответить