When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

joisino's blog

By joisino, history, 7 years ago, In English

Hello everyone!

JOI Open Contest 2017 will be held on July 2. (04:00-09:00 GMT) and July 2. (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 2017!

The contest duration is 5 hours and there will be 3 problems. 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!

UPD: The round1 will start in 90 minutes. The contest site and registration form will be announced 30 minutes before the contest.

UPD2: The contest is over. Thank you for your participation! Now, you can get problem statements, editorials and test data from contest information . Also, we open judge for analysis for about 24 hours from now. contest page is here .

We are carrying out the questionnaire to improve our contests. Please tell me your impressions about the contest. You can access the questionnaire sheet here . Thank you for your cooperation.

UPD3: The judge program for amusement_park was wrong in the contest as mentioned in this blog comment. Now, you can use the correct judge in the analysis round. We extend the analysis round 24 hours (The end of the round is 7/5 01:00 GMT) . You can also get the correct judge program from the test data section. We are very sorry for this issue.

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

»
7 years ago, # |
Rev. 7   Vote: I like it -20 Vote: I do not like it

Thank you very much for announcing the JOI (Japan Orympiad in Informatics) open contest.
I'm looking forward to this contest very much.

By the way, good luck to 4 participants of IOI from Japan (yutaka1999, maroonrk, KeiyaSakabe, goto), and all IOI participants from the all over the world!

UPD: Sorry for my poor English.
UPD2: Thank you very much! It was interesting and fantastic!!!

»
7 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Will you please post a reminder or update the blog with something like "the site is now on" or "you have only a couple of hours until the beginning of the first round"? I always check the newest blogs and it'd help me, if not all of us, not to miss the competition. Thanks for announcing it. I really love the quality that Japanese contests have and the fact that now everybody can enjoy that quality

»
7 years ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

OJ to practice with JOI Open Contests from the past 4 years: https://oj.uz/problems/source

»
7 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

First slot starts in < 3 hours.

Also, contest site is still not announced afaik. (UPD : Nvm just realized this sentence in the contest page : "A link to the registration page will appear on this page about 30 minutes before the beginning of each contest.")

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It's 10 mins before the contest. Where to register?

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Did the site crash? I can't access it anymore...

»
7 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can we register for the second round right now? I've tried to register, but it seems I did so for round 1, so I was afraid to login:))

Nevermind, I see that now I can register for round 2, so I just made some other account. Good luck everybody!

»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

From our IOI2017 team, I heard that grader is very weak.

I suspect that the Move() function don't check next node's adjacency. So, even if the node is far away from current one, it don't give WA.

Can you investigate this issue?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    In my pc Ioi function was returning 0 (I didn't change anything), but grader accepted it correct for sample case..

    And one thing, I wrote Move(0) at beginning of Ioi function, grader gave me Wrong Answer[6], however, it is written when calling Move(x) x should be in range 0 to n-1 (inclusive).

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    Following code gives AC

    Joi.cpp

    #include "Joi.h"
    
    void Joi(int N, int M, int A[], int B[], long long X, int T) {
    	for(int i = 0; i < 60; i++) MessageBoard(i, !!(X&(1ll<<i)));
    	for(int i = 60; i < N; i++) MessageBoard(i, !!(i&1));
    }
    

    Ioi.cpp

    #include "Ioi.h"
    typedef long long ll;
    
    long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    	ll ret = 0;
    	for(int i = 0; i < 60; i++) ret += (ll)Move(i)<<i;
    	return ret;
    }
    
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn'tt know how to make less than 180 moves when depth is less then 60, so my code didn't get 100 but when I go to the root immediately it takes 100.

    // while(P != 1) {
        // Move(par[P] - 1);
        // P = par[P];
    // }
        Move(0);
    

    That's really a issue :(

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    kriii figured out why. This is the official grader code.

    static bool HasEdge(int u, int v)
    {
        if (u > v) swap(u, v);
        return lower_bound(edges, edges + M, make_pair(u, v));
    }
    

    That is a code which g++ might optimize to return true....

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess we can discuss now since contest is over? What are the solutions to B and C?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    A slow solution to B: (I hope this makes sense)

    Let L1 and L2 be the lines between which the bulldozer will dig. Given a line k, how do we find the optimal choice of L1, L2, such that L1, L2 are parallel to k? Note that k orders the n points (if k is parallel to some line between two points, then these points will occupy the same spot in the ordering, but we don't need to consider such lines k), and that the points between L1 and L2 will occupy a contiguous subsegment in this order. So we just need to find the maximal segment-sum a[l]+...+a[r] in the array a[0],...,a[n-1] where a[i] is the value of the i:th rock in the ordering induced by k.

    Now imagine rotating k: Usually, the order of the points does not change. In fact, the order changes precisely when k is parallel to a line between two or more points; then the order of all the points on that line is reversed. So if we can precompute these lines, (and order them by angle), we can simulate the rotation of k and update the order.

    Now we just need to find the maximum segment-sum after each update of the order. We can actually handle arbitary changes to a[i] using a segment tree: Let each node keep track of the sum of its segment, the maximum and minimum prefix sums of the segment, and the maximum segment-sum contained in its segment.

    Anyway, the complexity is O(n^2*log n), which is pretty slow: I got TLE on all subtasks except the first 2 :(. But I think this might have passed if I optimized it more.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 4   Vote: I like it +20 Vote: I do not like it

      This exact solution worked for me. The only optimizations I made were using no floating point operations (which might have been necessary anyway to deal with parallel lines and collinearity), and looping through only N(N - 1) / 2 lines rather than N(N - 1) lines (though that this works might have been obvious to other people, at first it wasn't to me).

      Also, it's not necessary to figure out the list of points on a line and reverse them. If we sort the lines (i.e. pairs of points) properly, at each time-step we can just swap the two points which define the current line. After all pairs of points with a certain slope are processed, the points on one line will be reversed.

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

        Ah. I thought about reversing them pair-by-pair, but didn't figure out how to sort the pairs properly. (I guess we want to sort pairs of points lexicographically, where points are sorted lexicographically as well?) This seems to have been the main problem with my solution, although my recursive segment tree might have contributed as well.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          These are the steps I used to compare two pairs (of a base point + a vector):

          1. Compare the angles of the vectors

          2. If those are equal, the lines are parallel; now compare their projections onto a line perpendicular to them

          3. If those are equal, the lines coincide; now check which pair has a base point "further along" the line (and break ties by comparing the second points in the same fashion)

          To check which point is "further along" we can just check if the dot product of their difference with the line vector is positive or negative.

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Where can we upsolve problems?
it's said that judging server should be open but I can't find a way to submit.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    You can submit 'Bulldozer' and 'Golf' here. 'Amusement Park' will be available in 12 hours, I think.

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

      'Amusement Park' is also uploaded too: https://oj.uz/problem/view/JOI17_amusement_park

      However, our server seems to be too slow. The model solution for 'Golf' runs in 3 sec in the contest server, but 4.6- sec in our server (which is quite close to the time limit) Sometimes we encounter situations like this: the official time limit is T sec, but the official solution needs T - ε sec. In such cases, should we increase the time limit, or leave the limit as it is?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I think it's better to scale the time limit so that the ratio between the official solution's needed time and the time limit is the same as in the contest

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Where can I find results for Japanese students?

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
7 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).

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry,but how can I

'get problem statements, editorials and test data from contest information'

I can't find some links in this page,thank you!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    OK OK,this page has been updated and we can get Problem Statements,Reviews and Test Data.