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.
Great contest, loved the food. Looking forward to next year!
ench orz
tysm for the contest it was so fun :3
ezraft orz
yahoo
Really enjoy the contest! Hope it becomes 5-hours contest next year
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.
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
Great contest! First time participating in an in-person contest in around four years and it was so much fun meeting people :)
One could even say the contest was LIT...
much fun
lemonade pog organizers orz
We had a lot of fun organizing and hope you enjoyed it!
very fun contest good food balloons are fun we need a smaller difficulty gap :notlikeblob:
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.
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!
Thanks
Just because you comment 1e9 times on the same blog does not mean your contribution will magically increase from -30 sir
T_T
Great job!
can you help me how to solve B
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.
thanks very much
As an organizer give me contribution.
can anyone help me B
I enjoyed eating 1e9+7 slices of pizza at BAPC.
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
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.
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.
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):
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
Thanks.
Is there any written solutions? I'm pretty curious about the solution to problem A and C.
Sorry for the wait! We've just uploaded the written solutions to Dropbox.
So great, thanks. Problem C is crazy.
Thanks
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.
да
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?
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