yutaka1999's blog

JOI Open Contest 2020
By yutaka1999, history, 4 years ago, In English

Hello everyone!

JOI Open Contest 2020 will be held from Sunday, September 6, 04:00 UTC to Monday, September 7, 04:00 UTC. You can start at any time and the duration is basically 5 hours. Note that the duration becomes shorter if you start after Sunday, September 6, 23:00 UTC, i.e. less than 5 hours before the contest ends.

There will be 3 tasks. Each submitted source program must be written only in C++. Problem statements will be provided both in Japanese and in English. You can find more details in the contest page.

Past contests are also available in this page. Since the judge server isn't available now, please download testcases when you want to test your code.

Good luck and have fun!

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

»
4 years ago, # |
  Vote: I like it +75 Vote: I do not like it

You can solve past problems here: https://oj.uz/problems/source/53

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

Can someone share proof of these claims of problem B.Monochrome ?

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

    Is claim 2 really correct?

    I didn't implement my solution but I think that claim 1 is correct and then we need to $$$O(n)$$$ times add a linear function $$$f(i)=i+const$$$ or $$$f(i)=-i+const$$$ to an interval of indices of white points. That's because for every black point the number of intersections of its segment is $$$min(pointsAbove, pointsBelow)$$$ like square1001 described below. If I'm correct, maybe this helps in proving your bitonicity claim.

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

      I asserted the claim 2 on the test data of the first 3 subtasks and the samples and it worked.So I coded it up efficiently and it got 100.I believe the test data is strong only.

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

        Would you please describe your 100 points solution?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it 
          after claim 1 there are only O(n) solutions.
Checking each of them can be done in O(nlogn) so total complexity will be O(n*n*logn) which gets 35 points

claim 2 means that the array c(with reference to first comment) is bitonic

there are 2 cases 
if c_0>=c_n-1:
     binary search for the last index i 
     such that c_i>=c_0
     and then to calculate the answer by
     ternary search in the range (0,i)
else:
     binary search for the first index i 
     such that c_i>=c_n-1
     and then to calculate the answer by 
     ternary search in the range (i,n-1)

          https://oj.uz/submission/293453

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

    Now you can find a proof in the editorial, though it is a bit long.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

Problem 2 "Monochrome Points" was superb. It was very difficult but interesting.
Maybe I solved with an approach which is very different from others.

First, think about maximizing the total length of arcs for each line, instead of maximizing the number of intersections of lines. Here, we define length of arc between point $$$x$$$ and $$$y$$$, the value of $$$\min(|x - y|, 2N - |x - y|)$$$.

If the maximum total length of arcs is $$$X$$$, always, the answer will then be $$$(X - N) \div 2$$$. Note that this formula is not necessarily true for all ways of matching, but it is always true for maximum pattern. The idea of proof is that, in maximum pattern, lines with arc length $$$L$$$ is always passed by other $$$L-1$$$ segments.

Proof

This means we need to calculate $$$X$$$ in a reasonable time. Since this problem is Maximum Weight Matching of bipartite graph, we can calculate in $$$O(N^3)$$$ time with Hungarian Algorithm. This solution yields 25 points by subtask 1 and 2.

However, to solve it more quickly, we need to devise more. Here, the maximization of total length is difficult. Let's think about minimization of total length instead! We can transform from "maximize-problem" to "minimize-problem" by transferring all $$$N$$$ white points to the opposite position in the circle.

The minimization problem is easier. If we cut one points in circumference in circle, then the circle is developed to "a segment" with length $$$2\pi r$$$. The "minimize-problem" for 1D line is a classic problem (the idea can be used in AtCoder Problem "1D Matching"), and can be solved in linear time. Since we brute-force cutting points of circumference, the total time is $$$O(N^2)$$$.

Using a data structure, this can be improved to $$$O(N \log N)$$$. Thank you for reading!

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

    Actually I just reduced the number of candidate solutions to $$$O(N)$$$ (each of which can be checked in $$$O(N\log N)$$$ or I think even $$$O(N)$$$ time but I was lazy to optimize). Then, I just printed out values for small $$$N$$$ and realized it was somehow bitonic so I just did a binary search and passed it without much effort hmm (though I didn't prove the property).

    → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

How to solve C (Power Plant)?

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

    Observe that there can only be one pair of turned on generators $$$x, y$$$ such that $$$y$$$ is a parent of $$$x$$$. If there is more than one pair, then there exists a triple $$$x, y, z$$$ such that $$$y$$$ is along the path from $$$x$$$ to $$$z$$$, and will be turned off.

    Then, let $$$dp[u]$$$ = max profit in the subtree of $$$u$$$ such that no generator that is turned on is a parent of another.

    The transitions are:

    $$$ dp[u] = \sum\limits_{v \in child[u]}dp[v] - gen(u) $$$

    where $$$gen(u)$$$ denotes whether $$$u$$$ is a generator (if it is, it will be turned off, giving $$$-1$$$ profit).

    The answer equals:

    $$$ \max\limits_{u = 1}^n(dp[u], \max\limits_{v \in child[u]}dp[v] + gen(u)) $$$

    because you can choose to have one generator to be the parent of another.

    Submission

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I think test cases for furniture are weak. My O(nm(n+m)) soln passes in 0.5s.

https://github.com/T1duS/CompetitiveProgramming/blob/master/Olympiad/JOI/oc20_furniture.cpp

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

When will the editorial be realeased?

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

    The editorial has already been released. See the Reviews section of the contest page.

    → Reply