By DeadPillow, history, 5 weeks ago, Hey everyone!

I'd like to invite you to participate in the ACPC 2021 Kickoff contest on the gym on 26.06.2021 11:00 (Московское время).

The problems were created by me, KhaledKEE, eagle93, and compiler_101. The contest will include 12 problems and 5 hours to solve them.

I'd like to thank Mostafa_ELbadawy, Amirnasr, and Mohammad_Yasser for testing our (Initially) Bug ridiculed contest.

While the setters didn't have fun creating the contest the participants at the official contest said it was good.

We hope you like the contest or don't doesn't really matter. Announcement of ACPC Kickoff 2021 Comments (16)
 » Auto comment: topic has been updated by DeadPillow (previous revision, new revision, compare).
 » We can't see the contest in the Gym. Can we get an invite link or is there some group that needs to be joined?
 » Will there be an editorial after the contest?
•  » » We made a cringe-worthy video editorial that was posted on Facebook. I'll try to find it and post it here.
•  » » The editorial video : https://www.facebook.com/AfricaArabCPC/videos/508052713861837
 » 4 weeks ago, # | ← Rev. 2 →   For N=0 Jury's answer in D is 2 but in J it's 0. The empty sum should be counted as 0.Also what exactly is the solution of D?Please add ghost participants as well.
•  » » J totally confused me. When N=0, it should returns -1, instead of the wrong 0.
•  » » » Empty sum is zero. https://en.m.wikipedia.org/wiki/Empty_sum Also https://en.m.wikipedia.org/wiki/Vacuous_truth
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   But the problem description doesn't mention anything about "sum". It only says "create expressions". For example, in Javascript, if expression is empty, "eval(expression)" returns "undefined", instead of 0.
 » How to solve H?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   Build a prefix sum array to find the sum of arbitrary subarrays in $O(1)$ time. Then for each possible $X$, find the answer. At first glance, this looks $O(N^2)$, but most values of $X$ have few intervals. Formally, either $X \leq \sqrt{N}$, which takes $O(N^{\frac{3}{2}})$ time, or $X > \sqrt{N}$, so there are $\leq \sqrt{N}$ intervals to consider. This branch also takes $O(N^{\frac{3}{2}})$ time. The overall runtime is $O(N^{\frac{3}{2}})$.
 » Good problems overall. Absolutely enjoyed solving problem D, thanks for that.
•  » » can u tell me the solution, I tried dp , but getting wrong ans, I have tested some numbers but they seems right
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   I can't prove it, but here's what I did.Assume we can use only multiplication and division. Then we can use a simple O(N2) DP to pre-process and solve each test case in O(1).We can optimize it to roughly O(N log N) if we notice that to do the multiplication, we only need to check the divisors of a number. Also, we don't need to check all possible candidates for addition. It suffices to check for less than 10 candidates, from 1 to N. Just try adding X and N-X for each X in {1, 2, 3, 4, 5, 6, 7, 8, 9}. It's pretty intuitive if you think about it. As because you also have multiplication, you don't need to do many additions.How to handle division and subtraction? We can't do DP naively with them, because we'll run into cycles. There are some other tricks you can use here, but the following works pretty nicely.Assume we won't ever need to use numbers greater than 4N in our expressions. Do the previous DP with additions and multiplications for all the numbers not exceeding 4N. Then do another DP with subtraction and division (same as in before, just in reverse). After this, do we have the optimal answer? Well only for some values, but not for all because we did the DP in a fixed order and it's not necessary for them to maintain this ordering in the expressions.What we can do though, is run this whole cycle over and over again until it converges. Each time, some new values will get updated and we can basically repeat this until all the DP values from 1 to N stops updating. This converges pretty fast, requires less than 10 iterations.How did we get these magic numbers like 4N and 10? Just intuition and some trial and error. Code#include #define MAX 800000 using namespace std; int dp[MAX]; vector divisors[MAX]; void init(){ dp = dp = 2, dp = 1; for (int n = 3; n < MAX; n++) dp[n] = 2 * n; for (int i = 2; i < MAX; i++){ for (int j = i + i; j < MAX; j += i){ divisors[j].push_back(i); } } } void gen(){ int n, k, l; for (n = 3; n < MAX; n++){ for (k = 1; (n - k) >= 1 && k < 10; k++){ dp[n] = min(dp[n], dp[k] + dp[n - k]); } } for (n = 3; n < MAX; n++){ for (auto d: divisors[n]){ dp[n] = min(dp[n], dp[d] + dp[n / d]); } } for (n = MAX - 1; n >= 3; n--){ for (k = 1; (n + k) < MAX && k < 10; k++){ dp[n] = min(dp[n], dp[k] + dp[n + k]); } } for (n = MAX - 1; n >= 3; n--){ for (k = 2; k < 10 && n * k < MAX; k++){ for (l = 0; l < k && (n * k + l) < MAX; l++){ dp[n] = min(dp[n], dp[n * k + l] + dp[k]); } } } } int main(){ freopen("two.in", "r", stdin); init(); int t, n; for (int i = 0; i < 8; i++) gen(); scanf("%d", &t); while (t--){ scanf("%d", &n); printf("%d\n", dp[n]); } return 0; } 
 » Where is the link to the problem set?
•  » »