### ojuz's blog

By ojuz, 22 months ago,

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!

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.

• +196

 » 22 months ago, # |   +52 Cauchy_Function is the best Korean problemsetter. It must be fun for all participants!
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by ojuz (previous revision, new revision, compare).
 » 21 month(s) ago, # |   +3 Reminder that the contest begins in 5.5 hours
 » 21 month(s) ago, # |   +18 will be there editorial ?
•  » » 21 month(s) ago, # ^ |   0 You can find the solution sketches in the contest page here: https://oj.uz/contest/view/FUNCTIONCUP4
 » 21 month(s) ago, # |   0 How to full score windows?also, will the scoreboard be available again later?
•  » » 21 month(s) ago, # ^ |   0 The scoreboard is still available here: https://ranking.fxcup4.cms.oj.uz/
 » 21 month(s) ago, # | ← Rev. 3 →   +15 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!$.
•  » » 21 month(s) ago, # ^ |   0 I think Merge-insertion sort can achieve it!
•  » » » 21 month(s) ago, # ^ |   0 Well, turns out that's exactly the algorithm in my template :( Guess I got some details wrong.
 » 21 month(s) ago, # |   +28 My personal favorite is 1-2. Lol
 » 21 month(s) ago, # | ← Rev. 3 →   0 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.
•  » » 21 month(s) ago, # ^ |   +8 $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.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 This solution seems pretty neat.Could you sketch the main ideas?Or will there be an editorial?
•  » » » » 21 month(s) ago, # ^ |   +8 SpoilerYou 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.
•  » » » 21 month(s) ago, # ^ |   0 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.
•  » » 21 month(s) ago, # ^ |   +10 Alternatively to ko_osaga's solution, divide and conquer + minkowski sum solves the problem directly.
•  » » » 21 month(s) ago, # ^ |   +10 Could you elaborate a bit?I don't thinke I've seen things like Minkowski sum so far and seems interesting to learn/use.
•  » » » » 21 month(s) ago, # ^ |   +18 solve(l, r): // solves for range [l, r), returns the convex hull of optimal choices if(r - l == 1) return Polygon(0); mid = (l + r) / 2; hull = convexHull(solve(l, mid), solve(mid, r)) // convexHull(A, B) computes the convex hull of 2 hulls in O(N) A[i] = convexHull of points (A, P) in [l, mid) if i == 0 or [mid, r) if i == 1 D[i] = convexHull of points (D, P) in [l, mid) if i == 0 or [mid, r) if i == 1 hull = convexHull(hull, minkowskiSum(A[0], D[1])) hull = convexHull(hull, minkowskiSum(D[0], A[1])) return hull 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.
 » 21 month(s) ago, # | ← Rev. 2 →   0 there is an editorial for practice session problems ?
 » 21 month(s) ago, # | ← Rev. 2 →   0 How to solve Get Hundred Points! problem from the practice session ?