Hello, Codeforces!
I am happy to invite you to participate in Tishreen + SVU Collegiate Programming Contest 2023 which was held on Tuesday, June 20, 2023, at 11:00.
The problems were authored and prepared by LastDance_NotLastOfMe, ApraCadabra, CaMOUFlage, purp4ever, FzArK, Geo_Ghaffar, Nihad_Nabelsi, Tinky-Winky, Ali_ZaiBug, Experto_Besherunom, MaherSefo, and me.
I would like to thank our testers:
Vectors_Master, BabaVoss, Mohanad_Nahhal, Ayham_Dabah, Yousef-Elwan, Saleh_Nawar, Aasa-chan, little-fermat, KoKai, Shawerma, Miraculous_100, I_will_keep_trying, Shahed_Bawadekji.
And a special thanks to EleCursity, who helped us coordinate the contest onsite.
We would love to hear your feedback about the contest. Hope you enjoy solving the problems! wish you the best of luck!
As a problem-setter, give me Pringles.
As a problem-setter, I really recommend the problemset for any team who likes solving problems. :)
The moment we've been waiting for is finally here! Best of luck to all the participants.
orz
As a contestant in this contest, I would like to thank you all for this enjoyable contest.
Finally I can say "Siiiiiii" XD
Have fun and ENJOY solving
As a problem-setter , I can assure you that the problems are interesting and I encourage you to try solving them all. Have fun!
I'm not a contestant . I'm not a problem-setter . I'm not a Tester
Yet I still want to farm Contribution
It was a nice experience , I wish the best for all participants.
Will an editorial be published? Nice problems btw :)
We are currently working on the editorial, but it may take some time before we can publish it.
Thank you!
i will solve all of the problems soon :)
Nice problem set. Try to solve every problem.
How to solve K ?
my idea was ..say i have the answer of node 6 which is ( 6*1 + 1*2 )
and now i want to calculate the answer of node 10
then it will be ans[10]=(10*1 + ans[6])
but here ans[6] has to be ( 6*2 + 1*3 not 6*1 + 1*2 )
how to do this efficiently?
You can't find the answer of some node depending on the answer of its parent node (as far as I know).
I kindly ask you to wait until we prepare and publish the editorial.
Is there any tutorial coming soon ?
Yes, but this month is particularly hectic for us due to exams and graduation projects so it may take some time.
Finally solved all, thank you for this fantastic problemset!!
orz
104487I - Link into the Vrains was by far my favourite from the set. It blew my mind how all the observations tied together at the end, making for a very elegant reduction with a simple (and more powerful) solution.
There are $$$n$$$ points on the $$$x$$$-axis whose positions are known to you. Each point has a value $$$a_i$$$ (positive, negative or zero). There is an edge between $$$i$$$ and $$$j$$$ if $$$abs(x_i-x_j) \lt D$$$, where $$$D$$$ is given to you. You must pick some subset $$$S$$$ (possibly empty) of these points such that
What is the maximum possible answer assuming $$$k = \infty$$$?
$$$\sum\limits_{a_i \ge 0} a_i$$$
When should you take points with $$$a_i \lt 0$$$? Rather, when should you not take points with $$$a_i \lt 0$$$?
In all cases, removing such points will improve the answer without increasing the number of components.
Can you infer anything about pairs of non-negative points?
If a non-negative point is chosen, then any non-negative points connected to it by an edge should also be chosen. So if one such point is chosen, all non-negative points in its component must be chosen, otherwise none at all.
Why? Adding neighbouring non-negative points improves the answer without increasing the number of components.
So will you ever choose negative points between two non-negative points in the same component? Can you simplify the graph using Hints 2 and 3?
No. Ignore them. Replace each non-negative component with a single non-negative point equivalent to its sum and delete all the negative points that fall within any of these component.
Ok when should you take negative points then?
Consider two adjacent non-negative points not connected by an edge. Negative points between them can be chosen to connect them, i.e. reduce the number of connected components by $$$1$$$. Does this ring any bells?
How else can you reduce the number of components?
Delete (or un-choose) an entire connected component.
Is there a term in graph theory for something which reduces the number of components in a graph?
An edge.
Remodel this as another graph problem. What are the nodes? What are the edges? Do the edges have weights? What are the weights? What is the objective of the new problem?
You have some nodes (condensed non-negative components). There are two types of edges. Between every pair of these nodes adjacent by position in the original problem, you add an edge with weight equal to the cost of merging these two into the same component (minimum cost to pick some negative points between them such that they become connected). How do you calculate this value? And what about edges of the second type?
Lets see how to calculate these values first. Consider all the negative points between two adjacent nodes $$$l$$$ and $$$r$$$. Let $$$dp_j$$$ denote the absolute value of the sum of negative points chosen connecting $$$j$$$ with $$$l$$$ directly or indirectly. Then the weight of the edge between $$$l$$$ and $$$r$$$ will be the minimum value of $$$dp_j$$$ such that $$$j$$$ has a direct edge with $$$r$$$. This can be done in $$$\mathcal{O}(n)$$$ amortized using a stack or deque.
Next, think edges of the second type.
These edges correspond to deleting a component. Let's imagine there's a virtual $$$0$$$-th node. Add an edge between every node and the virtual node $$$0$$$ with weight equal to the total value of the component. Now what? How can you obtain the solution to the original problem from this setup?
As you might have guessed already, this is starting to look like an MST problem. Picking an edge reduces the number of components and the weights correspond to the cost of doing so. You want at most $$$k$$$ components. So in Kruskal fashion you can pick edges with the least cost until there are at most $$$k$$$ components.
But when you choose an edge, what changes in the rest of the graph?
What happens when you choose an edge of type $$$1$$$? You merge two nodes (components) into a single component. The new value of the component is the sum of the component values plus the edge weight. The two components' type $$$2$$$ edges are deleted and you add a new type $$$2$$$ edge for the merged component weighted with this value. The rest of the graph remains unchanged.
What happens when you choose an edge of type $$$2$$$? You are deleting a component $$$p_j$$$. If you want to merge components $$$p_{j-1}$$$ and $$$p_{j+1}$$$ (to its left and right) in the future, you'll have to add an edge of type $$$1$$$ between them. The weight of this edge is the sum of edge weights $$$(p_{j-1}, p_j)$$$ and $$$(p_j, p_{j+1})$$$ plus the value of the deleted component since picking these three will enable you to connect $$$p_{j-1}$$$ and $$$p_{j+1}$$$. This is also the minimum cost to connect them. Why?
So now you can handle the necessary updates to the graph every time you choose an edge. Just simulate Kruskal's algorithm until you have not more than $$$k+1$$$ components (accounting for the virtual node) and the final answer is $$$\sum\limits_{a_i \ge 0} a_i - \text{k-MST weight of the forest}$$$.
And there you have it! A solution to the original problem after some (imo) very cool reductions. In fact, this problem can be solved simultaneously for every $$$k$$$ from $$$1$$$ to $$$n$$$ with the current constraints (216906416).
If it is not possible to connect some non-negative adjacent nodes, add an edge of weight $$$\infty$$$ between them for ease of implementation. You will never choose this weight.
Further, consider an array where odd indices $$$(i=1, 3, \ldots)$$$ contain the type $$$2$$$ weights corresponding to node $$$\left\lceil \frac{i}{2} \right\rceil$$$ and even indices $$$(i=2, 4, \ldots)$$$ contain the type $$$1$$$ weights corresponding to nodes $$$\left\lceil \frac{(i-1)}{2} \right\rceil$$$ and $$$\left\lceil \frac{(i+1)}{2} \right\rceil$$$. Now an update operation on $$$i$$$ is simply merging $$$(i-1, i, i+1)$$$ with value $$$a_{i-1} + a_{i+1} - a_i$$$ regardless of type of edge, further simplifying implementation.
The time complexity is $$$\mathcal{O}(n)$$$ to compute the initial type $$$1$$$ edge weights and make the reduction to the new graph. It is $$$\mathcal{O}(nlogn)$$$ to simulate Kruskal's with a heap or set.
Now you might be wondering why this will give you the optimal answer even though we do not consider all edges right from the start and 'discover' new ones during the process? What if there is an edge which is discovered later, but should have been picked earlier (smaller weight)?
It turns out that this is impossible. This is because any new weight you discover is always greater than or equal to the weight that was just chosen. So the non-decreasing order of edges weights chosen via the algorithm is preserved!
If you've seen a similar problem or have come up with a different approach to this problem, do share!
on fire
Hi Da7doo7, thanks for the problemset, are there any updates on the editorial? at least publish the completed ones.
Hi .can anyone help me to solve A?