ojuz's blog

2019 FunctionCup
By ojuz, 5 years ago, In English

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!

2019 FunctionCup Logo

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.

  • Vote: I like it
  • +196
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
5 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Cauchy_Function is the best Korean problemsetter. It must be fun for all participants!

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Reminder that the contest begins in 5.5 hours

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

will be there editorial ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to full score windows?

also, will the scoreboard be available again later?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

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!$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

My personal favorite is 1-2. Lol

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    $$$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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      This solution seems pretty neat.Could you sketch the main ideas?Or will there be an editorial?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        Spoiler
        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Alternatively to ko_osaga's solution, divide and conquer + minkowski sum solves the problem directly.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Could you elaborate a bit?I don't thinke I've seen things like Minkowski sum so far and seems interesting to learn/use.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it 
        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.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

there is an editorial for practice session problems ?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve Get Hundred Points! problem from the practice session ?

→ Reply