UPD Aug/23/2019 05:59:46 UTC: You are not allowed to use C11.
UPD Aug/24/2019 07:41:50 UTC: Your score on each task is computed as the same way as IOI 2019 (use sum of best subtasks)
UPD Aug/27/2019 01:48:35 UTC: Each member of the team can use their own computer (just like in IPSCs)
UPD Aug/29/2019 12:56:37 UTC: Practice contest starts at Aug 30th 10:00:00 (UTC).
UPD Aug/30/2019 10:37:19 UTC: Practice contest began at 10 am: Link Scoreboard
UPD Sep/01/2019 06:21:19 UTC: Maincontest began at 4 AM UTC: Link Scoreboard
UPD Sep/01/2019 09:39:18 UTC: The contest is over, thanks for participating! Problemset link
2019 FunctionCup will be held on September 1st!
- URL: https://oj.uz/contest/view/FUNCTIONCUP4
- Time: September 1st 13:00 KST — 18:00 KST (5 hours)
- Statement Language: English, Korean
- Contest System: oj.uz wrapped with CMS template
- Programming language: C11, C++17 (GCC 7.3)
- Number of tasks: 12
- Scoring system: Use the sum over each subtask of the best result for that subtask across all submissions (IOI 2017-)
- Penalty: ties broken with time (AtCoder format with no penalty for wrong submissions)
- Scoreboard: Public, not frozen during the whole contest
- Practice Contest: https://oj.uz/contest/view/FUNCTIONCUP4PRACTICE (starts at Aug 30th 10:00:00 (UTC))
- Max team size: 3, each member can use their own computer
FunctionCup is an annual contest written by Cauchy_Function, and is famous in South Korea for having innovative and quality problems. Some of the problems were proposed in last year's GP of Korea. (example here, example there)
Registration is available right now, and will close 5 minutes before the contest starts. Visit the URL for details.
There will be a practice contest to make you familiar with the contest system. Go to the link for details.
There are prizes for people who live in South Korea. This is because we don't afford to pay transportation cost outside of South Korea, so sorry for that.
You can solve previous year's problems here and there, although they are not translated in English.
We invite everyone to join in the contest. After the contest, you will be able to solve all problems in oj.uz.
Cauchy_Function is the best Korean problemsetter. It must be fun for all participants!
Reminder that the contest begins in 5.5 hours
will be there editorial ?
How to full score windows?
also, will the scoreboard be available again later?
On problem wine, is there some easy way to sort 12 elements with the lowerbound 30 comparisons? I thought my randomized solution would work until I found out there are 120 tests in the subtask. (upd: just realized there aren't that many cases with K=7 so maybe it would pass)
My idea: give the smallest 12 elements 1 or 2, give the rest 3 to 7, $$$2^{12} \times 5^{18} > 18!$$$.
I think Merge-insertion sort can achieve it!
Well, turns out that's exactly the algorithm in my template :( Guess I got some details wrong.
My personal favorite is 1-2. Lol
What was the intended solution for Squad?Coded two solutions, one with $$$O(Nlog^2N)$$$ time complexity and $$$O(NlogN)$$$ space complexity (but pretty good memory constant) that couldn't fit in time and one with $$$O(NlogN)$$$ time and space complexity (a merge-sort tree of some linear functions optimized with fractional cascading) but maybe because the bad memory constant (had a lot of arrays) it didn't seem to pass memory limit.
$$$O(N\log N)$$$ time, $$$O(N)$$$ space complexity. Model solution passes in <1.3s. However I used about 3 hours to optimize constant with $$$O(N\log N)$$$ algorithm.
This solution seems pretty neat.Could you sketch the main ideas?Or will there be an editorial?
You can solve if you maintain convex hull without one point. Let $$$H[1], \cdots, H[k]$$$ be the points in convex hull (sorted in angular order). If you remove $$$H[i]$$$, there may appear some new points that were "hidden" because of that point. They are in an angular range between $$$H[i-1], H[i+1]$$$. So simply enumerating them is OK. Save those "partial hull without $$$H[i]$$$", and binary search in every query.
I also had the solution of same complexity. First I created the upper Hull and then marked the lines that appeared in the first Hull. Then I built second upper Hull. The top 2 answer to a query is either on the first Hull or second Hull or one of the adjacent lines (at most 2) in the first Hull, giving 4 candidates.
Alternatively to ko_osaga's solution, divide and conquer + minkowski sum solves the problem directly.
Could you elaborate a bit?I don't thinke I've seen things like Minkowski sum so far and seems interesting to learn/use.
You can do this all in F(N) = O(N) + 2 * F(N/2), or O(N*logN), by merging the points instead of reordering to do the convex hulls in O(N). Minkowski sum simply put takes the hull of the area that you can get by adding every pair of vectors a+b from A and B, since the vertices are the addition of points in the borders it's exactly what we want.
there is an editorial for practice session problems ?
How to solve Get Hundred Points! problem from the practice session ?