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.
Hello joisino, do you know if the contest is happening? According to the listed time, the first window starts in ten minutes.
The contest url is https://cms.ioi-jp.org/contest/
I will update the information page soon.
[Solved] I am able to register now
Will there also be a round with the same tasks at 10:00-15:00 (UTC/GMT) ?
I don't think it's good to have 3 data structure problems in a contest.
Three data structure problems. I think it's quite hard to get all of them accepted in a 5-hour contest :/
I found a typo of p3 5 minutes after the contest ended. What a pity! :(
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/)
Can you enable practice please? Also could you post the results of the first round as well?
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.
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.
Oh, thanks! I've found the ranking.
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.)
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.
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...
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.
Alright this is definitely nicer than what I had, thanks.
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.
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.
Interesting, I had a similar solution. How did you get rid of the ackermann(N) part?
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.
Can somebody post the problem statements? I forgot to register.
Try this:
statements
[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 butno 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.Will there be an editorial for the problems?
How to solve first problem? I had O(nsqrt(nlogn)) solution but it didn't pass.
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
Can you please explain more detailed?
There is already an editorial here.
Auto comment: topic has been updated by joisino (previous revision, new revision, compare).
?detaR tI sI
bubblesort2,catdogandxylophoneare available here: https://oj.uz/problems/source/351. We extended the time limit a lot because of our extremely slow server :pIt seems some tests of
catdogdon't have an output (the output file is empty). joisino, could you please take a look at this?There seemed to be a problem when I uploaded the dataset. I've fixed it.
Thank you for reporting the issue :)
I can't get the idea for subtask 3 in collapse from editorial. Maybe someone can help me?
Editorial says :
Can someone help prove why this works for Xylophone? https://github.com/T1duS/CompetitiveProgramming/blob/master/Olympiad/JOI/oc18-xylophone.cpp