Thank you for participating!
2024A - Profitable Interest Rate was authored and prepared by Helen Andreeva with Artyom123
2024B - Buying Lemonade was authored by Endagorion and prepared by sevlll777
2023A - Concatenation of Arrays was authored and prepared by Mangooste
2023B - Skipping was authored and prepared by adepteXiao
2023C - C+K+S was authored and prepared by yunetive29
2023D - Many Games was authored and prepared by Tikhon228
2023E - Tree of Life idea by isaf27, solution and preparation by Ormlis
2023F - Hills and Pits was authored and prepared by glebustim with vaaven
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Ormlis when will hidden test case and source code of others be visible?
Only administrators can do this, not me.
Oh sorry I didn't know. Btw great contest Thank you
Hi, I cannot prove my solution for div1D nor hack it I hope someone can hack or prove it.
287108342
The idea behind my solution is to have $$$dp[\sum w]$$$ store the maximum probability that we can achieve.
As with the editorial, for a fixed $$$p$$$, we should only take a prefix of the weights (when we sort from biggest to smallest weights). So we will also store that information (in the code it is
signed dp[400005][100];
, for statedp[x]
, we take the biggestdp[x][y]
elements with p=y.When we transition, we will try for all y to do
dp[x][y]++
.This doesn't seem right because it is possible for the optimal answer to be killed early when there is another state with a bigger probability for the same $$$\sum w$$$ but is worse at extending to larger $$$\sum w$$$
i swear i can't figure out for the life of me why my solution to B isn't correct, and i'm not allowed to look at the failing test case either.
I dont know about the formulas, but you should use long long instead of int.
Bro your code won't return any output if k is equal to sum of all elements of the array.
Try
1
3 6
1 2 3
Comment if you want me to fix it
then $$$c_p \cdot q^{c_p} > (c_p - 1) \cdot q^{c_p - 1}$$$; otherwise, the smallest element can definitely be removed.
why?
C is a piece of dogShit,i mean why it had to be based on some crap observation.It could have been improved by giving a formal proof of why does that always work. Disappointed...
What's wrong with the proof provided?
Another solution is to sort the arrays by comparing pairs $$$(min(a_{i,1}, a_{i,2}), max(a_{i,1},a_{i,2}))$$$. We can observe that if we move the array with minimal element to the left (and among these with the least maximum), the number of inversions cannot increase, so that's optimal order
lol yeah that was my method
Ormlis In D2C, how can we solve the problem for arrays of sizes three or more? I tried to solve it by comparing inversions of ab and ba for sorting but it seems this condition is not transitive and thus doesn't work for arrays of twos either, so I had to use some other min/max technique, which doesn't seem to generalise for sizes more than 2.
got IGM but still cannot solve A during contest, isn't weird?
A simpler solution for 1E:
When you choose a node as the root node, our answer is at least $$$\sum_{i=1}^n \frac12 s_i(s_i-1)$$$, where $$$s_i$$$ is the number of children of node $$$i$$$.
However, such a construction may not be able to satisfy some edges that pass through both the son and father at the same time. Let's consider the contribution of this situation to increasing the answer.
We set a dp state $$$f_i$$$ to represent the number of residual paths that can be uploaded through the parent when the node $$$i$$$ calculates the necessary contribution internally (i.e., the above equation).
Transfer as follows:
$$$f_u = \sum_{v\in son_u} \max(1 - [u\text{ is root}], f_v - (s_u - 1))$$$
After calculating $$$f_ {root}$$$, we must pair the extra paths pairwise, and when we choose the node with the highest degree as the root, we can prove that there must be a match to make the scheme valid:
[tbd, prove is hard]
So we can calculate $$$f_ {root}$$$ and add it to the equation at the beginning.
using translator.
287001804