Hi everyone!
The third round of COCI will be held tomorrow, December 11th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.
The round was prepared by Bartol, pavkal5, ominikfistric, and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
Would you consider adding rust, while we are at it? :)
Sure, we'll try to get it up and running by next round.
I am currently solving round 2 on DMOJ, and I can send you my solutions afterwards if you need them
Reminder: the contest starts in less than one hour!
Why is this code WA for Akcija sub-tasks 1 and 2?
Consider this input:
Did you skip k? What is the expected output?
Oh sorry, forgot to include k — should be 1. The point is that your solution will buy only one of the products but they can both be bought.
If k = 1 expected output is 2 4
How to solve E?
We'll pick a point P and count the number of non-empty sets where it is OUTSIDE the convex hull. Consider one such set. Since P is not contained in the hull, one can unambiguously choose another point Q which is the "most clockwise" of the points in the set. The rest of the set can then be any subset of the points within the 180° arc running counter-clockwise from Q.
A naive implementation would require cubic time, but by sorting all the points except P by the angle they make with P and then using a rotating line sweep, it can be reduced to $$$O(n \log n)$$$.
Thanks, makes sense!
How to solve C?
This may be abit late :P
Because I want to compare subsets using c++ pair, I will define $$$w'_i=10^9-w_i$$$ so that if we put $$$(num,val)$$$ as a pair, we are taking the $$$K$$$ biggest ones.
The first observation you have to make is that you need to sort $$$d$$$. Then this is the claim. You can take a subset of items $$$i_1,i_2,\ldots,i_k$$$ if $$$d_{i_x} \leq i_x$$$ for all $$$x$$$. This is clearly necessary and it is also sufficient as we can assign item $$$i_x$$$ to be bought at time $$$x$$$.
From this, we can already solve a function $$$dp(i,j)$$$ that returns the maximal $$$(num,val)$$$ that we can make if we only consider after the $$$i$$$ items and we already took $$$j$$$ items.
Now, we will do a binary search over $$$(num,val)$$$. We want to check if there are less than $$$k$$$ subsets $$$(num',val')$$$ such that $$$(num',val')>(num,val)$$$.
We do a recursive function $$$search(i,j,num,val)$$$. Suppose that $$$dp(i,j)<(num,val)$$$, then we can return here, because we wont produce a child such that $$$(num',val')>(num,val)$$$. When we found $$$k$$$ children, we can return immediately. This way, we only use up to $$$O(n)$$$ time per child. Since we cut off our search after finding $$$k$$$ children, we only using $$$O(nk)$$$ time per search.
Combining this with binary search, we have a $$$O(nk \log)$$$ solution.
Code
Can you recommend other problems that require finding the first $$$k$$$ best answers but solvable with a DP that looks like this?
What are the specs on the judge computers? My solution to C runs in 2.6s on max-size data on my machine, but got TLE when submitting.
Intel Xeon E5-2640
Ok, I guess I shouldn't expect too much from a CPU that's almost 10 years old.
For problem C(Akcija), does this idea help for a full credit soluton: https://stackoverflow.com/questions/33219712/find-k-th-minimum-sum-of-every-possible-subset? If so, may anyone please elaborate it?
How task D (Ekoeko) can be solved?
I don't have a formal proof of correctness, but here's how I solved it. Go through the left half, left-to-right, and whenever you encounter a letter for which you've already seen 50% of them, flag it (it needs to move to the other half). Do the same with the right half, working right-to-left. The minimum number of swaps to get the balance correct is to move all the left flagged letters to the start of the right side (without changing their order), and vice versa. Once you've got the sides balanced, you can permute the right side to match the left side (or vice versa, or meet somewhere in the middle, but there is a triangle inequality that prevents meeting in the middle from being any better).
Rather than doing all the swaps, you can compute what the final string will look like. Then there are standard algorithms to determine the number of swaps required to implement a permutation in O(n log n) time.
That's interesting! Thanks for sharing your approach.
Can you Share your code please :)
What are the algorithms you are talking about?
You need to count the number of pairs of elements that are out of order ("inversions"). One option is to run mergesort and augment it to count the number of inversions between the two halves of each merge as you merge. Another is to run through the elements left-to-right, counting the number of previous elements that are larger than the current element, with a data structure such as a Fenwick tree to quickly count the number of values seen in a range.
Related blog
Can you please elaborate a bit more on the triangle inequality that prevents meeting in the middle from being any better? I am unable to understand this part. Thanks for your great explanation!
Let A and B be two permutations, and d(A, B) be the minimum number of swaps needed to transform A to B. Then d(A, B) ≤ d(A, C) + d(C, B) for any C, because the RHS is the cost to go from A to B via C. And if you want to make A and B match by transforming them both to some C, then the cost is d(A, C) + d(B, C) = d(A, C) + d(C, B) ≥ d(A, B) = d(A, B) + d(B, B). So it is always at least as good to just transform both to B.
The tasks, test data, and solutions are now published! You can find them here.
You can submit your solutions here (HONI).
Good morning sir(In Croatia it's about 9 o'clock I think), I want to see the PDF of all the tasks but when I clicked on
Tasks
just now, it showed me the status 403. Could you please take a look into it? Thanks in advance.