joisino's blog

JOI Open Contest 2018
By joisino, history, 6 years ago, In English

Hello everyone!

JOI Open Contest 2018 will be held on July 8. (04:00-09:00 GMT) and July 8. (10:00-15:00 GMT) .The tasks for Round 1 and Round 2 are the same. So you can choose the round you will participate in.

The main purpose of this contest is to give an opportunity to Japanese delegations and candidates of delegations for training and practice for IOI. But the contest itself is open to everybody. Everybody is welcome to attend JOI Open Contest 2018!

The contest duration is 5 hours and there will be 4 problems. Each submitted source program must be written in either C++, Pascal, or Java. Problem statements will be provided both in Japanese and English.

Details are available in contest information.

The past contest information is available in JOI Website.

Good luck and have fun!

UPD1 I uploaded the editorials, sample source codes, and input/output data in the contest information page.

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

Comments Comments (35)
| Write comment?
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hello joisino, do you know if the contest is happening? According to the listed time, the first window starts in ten minutes.

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

[Solved] I am able to register now

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

Will there also be a round with the same tasks at 10:00-15:00 (UTC/GMT) ?

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

I don't think it's good to have 3 data structure problems in a contest.

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

Three data structure problems. I think it's quite hard to get all of them accepted in a 5-hour contest :/

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

    I found a typo of p3 5 minutes after the contest ended. What a pity! :(

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Is it ok, that score for problem is not the sum of max score for every group?

The final score for each subtask will be the maximum score of this subtask across all submissions. The score for each task will be sum of scores for its subtasks. (http://ioi2017.org/contest/rules/)

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

Can you enable practice please? Also could you post the results of the first round as well?

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

Is it just me or there's someone else try to submit, see the judging verdict and wait forever for the score? It was just there, judging, and the contest ended. I still don't know whether my solution is correct or not.

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

    Near the end it did take some good amount of time to judge. It keeps judging though, if your solution wasn't judged during the round, and to know the result you can go to the ranking page and click on your name, then pick a specific problem and you can see the result of every submission. Once it gets judged, it will appear in that list.

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

It seems nobody asks for it... can the solvers of Catdog or Collapse share their solutions/ideas? (though I'm more interested in Catdog, since collapse is more general than dynamic connectivity (add edge, remove edge, connectivity query) which is already terrifying.)

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

    I ACed catdog with HLD. Dp for 30 points is easy, and then you can see that when you update a node in the tree, the only values of dp that change are on the path from that node to the root. So you can have a segtree in every hld chain. It's not very pretty.

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

      Dang, when I tried it during the round it turned out so ugly that I didn't dare to continue. Still, I'm not sure how can you update quickly inside the segment tree...

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

        My nodes contained four ints, named cc, cd, dc and dd. For example, dc contains the minimal number of blocks if this interval starts with a dog "area", and ends with a cat "area".

        And you can update leaves of the segment tree in less than O(E) by saving the sum of all dp_cat for their children, and the sum of all dp_dog, in short.

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

          Alright this is definitely nicer than what I had, thanks.

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

    Solution for p3: the answer of a query is components considering nodes with id ≤ pi + components considering nodes with id > pi. Consider the first problem. For each pi we make a graph. Then an edge (u, v)(u < v) will appear in graphs with id ≥ v. So let its value be v. If we can get the minimum spanning tree, We can easily get the answer. And dynamic MST is this problem.

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

    I solved Collapse in O(N * sqrt(N) * ackermann(N)) with DSU and Sqrt Decomposition.

    The idea is that if we consider the next K queries we will have 2 * K special nodes and 2 * K special segments.

    Link to my code: https://pastebin.com/hmgkEKMz.

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

      Interesting, I had a similar solution. How did you get rid of the ackermann(N) part?

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

        Actually i didn't get rid of it, i always think complexity of DSU ~ O(N) so I forgot to include ackermann(N) part when i commented.

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

Can somebody post the problem statements? I forgot to register.

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

[solved]In one of the announcements it is told The input/output data is now public. You can download it from: But when I downloaded test cases of problem xylophone even half of the test cases weren't available. I typed them my question but no answer yet... I need a couple of test cases from 81-107. Will that test cases appear later? How can I get them? Thanks in advance. I was confused because of Codename and testNumber.

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

Will there be an editorial for the problems?

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

How to solve first problem? I had O(nsqrt(nlogn)) solution but it didn't pass.

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

    find max(i — f(A[i]) + 1), f(x) is number of values in sequence A which is smaller or equal to x

    (n+q) log n with seqment tree

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

Auto comment: topic has been updated by joisino (previous revision, new revision, compare).

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

?detaR tI sI

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

bubblesort2, catdog and xylophone are available here: https://oj.uz/problems/source/351. We extended the time limit a lot because of our extremely slow server :p

It seems some tests of catdog don't have an output (the output file is empty). joisino, could you please take a look at this?

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

    There seemed to be a problem when I uploaded the dataset. I've fixed it.

    Thank you for reporting the issue :)

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

I can't get the idea for subtask 3 in collapse from editorial. Maybe someone can help me?

Editorial says :

Apply the Square Root Decomposition to the number of cities in the upstream side and the downstream side. For the operations for each block, using one Union Find, we handle the cables in the block for which collapse does not happen. For the cables for which collapse happens, using the information of the previous Union Find, we can calculate the number of connected components using another Union Find.

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

Can someone help prove why this works for Xylophone? https://github.com/T1duS/CompetitiveProgramming/blob/master/Olympiad/JOI/oc18-xylophone.cpp

→ Reply