Bay Area Programming Contest 2024 Uploaded to Gym

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

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

→ Ответить

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

← 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

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

+29

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

→ Ответить

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

+22

One could even say the contest was LIT...

→ Ответить

allusion

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

+21

much fun

lemonade pog organizers orz

→ Ответить

ezraft

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

+24

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

→ Ответить

maxrgby

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

+26

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

→ Ответить

hxu10

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

← 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

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

+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!

→ Ответить

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

+10

Thanks

→ Ответить

ezraft

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

+42

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

→ Ответить

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

T_T

→ Ответить

GusterGoose27

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

+16

Great job!

→ Ответить

thangdz2k7

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

+10

can you help me how to solve B

→ Ответить

hxu10

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

← 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

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

+20

thanks very much

→ Ответить

GusterGoose27

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

+62

As an organizer give me contribution.

→ Ответить

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

Thank you so much

→ Ответить

thangdz2k7

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

can anyone help me B

→ Ответить

eysbutno

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

+15

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

→ Ответить

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

+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

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

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

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

→ Ответить

allusion

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

more bapc prizes when??

→ Ответить

Bucketsmith

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

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

→ Ответить

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

+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

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

+15

Actually I found the practice contest problems are interesting.

Is there a gym for trying the practice contest problems?

→ Ответить

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

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

+10

→ Ответить

liympanda

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

+15

Thanks.

→ Ответить

XeF2

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

-10

Yo!

→ Ответить

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

+15

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

→ Ответить

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

+14

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

→ Ответить

theRealChainman

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

+15

So great, thanks. Problem C is crazy.

→ Ответить

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

+10

Thanks

→ Ответить

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

+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

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

да

→ Ответить

LipArcanjo

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

+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?

→ Ответить