Блог пользователя joisino

Автор joisino, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +148
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 7   Проголосовать: нравится -20 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +20 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      '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 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Where can I find results for Japanese students?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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