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

yutaka1999's blog

By yutaka1999, history, 5 years ago, In English

Hello Everyone!

Japanese Olympiad in Informatics Spring Camp 2019 will be held from Mar. 19 to Mar. 25.

There will be four online mirror contests during the camp.

The contest duration is 5 hours and there are 3 or 4 problems in each day. Problem statements will be provided both in Japanese and English.

There might be unusual tasks such as output-only tasks, optimization tasks, reactive tasks and communication tasks, just like International Olympiad in Informatics (IOI).

The contest site and registration form will be announced about 30 minutes before the contest.

Details are available in the contest information page.

We welcome all participants. Good luck and have fun!

UPD: The link to the contest page is added. Schedule is updated.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Will there be mirrors after contest? The timezone isn't good for European programmers :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    since ko_osaga will make virtual participation to day 1 or day 2 of JOI spring camp , so I think there will be a mirrors after the contest.

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

      I think it won't be a mirror but just an analysis mode of the contest with all problems available.

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

    Unfortunately, there won't. But you can upsolve after the contests.

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

    They traditionally opened judge servers, as far as my memory goes.

    And, as my name is called, I'll also advertise it here: https://codeforces.com/blog/entry/66014

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

Will the japanese team be selected based on these 4 contests?

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

    Definitely! The team will be selected practically just with the spring camp results.
    I will participate in it and very looking forward to it :)

    P.S. I, of course, want to compete even with open contestants, so I am really looking forward to seeing many open contest participants and I definitely recommend to participate. It's really a high-quality contest.

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

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

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

where is site and registration form?

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

    They will eventually be on https://contests.ioi-jp.org/joi-sp-2019/index-en.html.

    A link to the registration page will appear on this page about 30 minutes before the beginning of the contest.

    And the contest begins in about 35 minutes: March 20, 2019 to March 23, 2019 10:00-15:00 +0900 (JST) 01:00-06:00 (UTC/GMT)

    Edit: this is going by what is on the contest site, there is discrepancy with the blog...

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

      But the time is 00:30 in the blog..

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

        Sorry for the delay.

        Today's contest will start in 01:30 in UTC, one hour after the initial plan.

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Will the lecture materials be available?

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

I'm curious that how did people solve problem "Meetings"? I heard many (at least three types) solutions, so I expect that many people solved in different ways.

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

    Can you describe some solutions?

    I've solved this contest in analysis mode, and it was really hard to push my solution to get OK (because it makes ~$$$41\,000$$$ queries)

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

      I solved during contest, finally around 39100 queries (as I remember) in 17-ary tree worst case.

      First, if we ask $$$query(0, x, y)$$$, we get LCA of $$$x$$$ and $$$y$$$ when the root is $$$0$$$.
      The first sub-problem is that, assuming the graph is line graph and one edgepoint is $$$0$$$, find the graph in $$$O(V \log V)$$$. We can do it easily because we can simply sort by distance from zero because $$$LCA(x, y)$$$ will be $$$x$$$ iff $$$d(0, x) < d(0, y)$$$.
      Then, let's return to main problem. Supposing that we fix $$$x$$$ and we ask $$$query(0, x, i)$$$ for all $$$i$$$, the set $$$S$$$ of return value will be all vertices in path from $$$0$$$ to $$$x$$$. We can get the order of path by solving sub-problem. This routine takes $$$O(V + |S| \log |S|)$$$.
      Then, thinking about distinguishing return value of $$$query(0, x, i)$$$, we can separate into the same problem for sub-tree. It works well if we decide the value of $$$x$$$ randomly.

      I submitted this solution first and got 78 points with about 44000 queries, but doing somewhat optimization I got 100 points. E869120 has much more efficient algorithm (about 22000 queries, possibly more than expected solution), so I hope that he will write the solution there.

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

      My randomised solution which gets ~25k queries on worst case 17-ary tree:

      Pick a random vertex as root. We will solve the problem recursively. We will pick a random vertex and find all vertices that belong to the path from the root to this random vertex by simply iterating over all vertices in this recursive call and doing a $$$query(root, randv, w)$$$. If the result of this query is $$$w$$$ we know that $$$w$$$ belongs to the path. If that's not the case we will add $$$w$$$ to a temporary set $$$S_{result}$$$.

      After that we can find the order of the vertices on this path easily in expected $$$O(n \log n)$$$ with a "quick sort"-like approach (pick a random vertex and divide the path into to new paths — one to the left of the vertex and one to the right).

      Well finally we run the recursion with root equal to every vertex on the path and set of vertices equal to $$$S_v$$$, where $$$v$$$ is the vertex on the path.

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

      I solved it during online contest. My solution works in about ~22k queries on 17-ary tree(I'm not sure it is the worst case).

      At first, there are tree with two nodes, 0 and 1. and there is an edge between them. from 2 to n-1, we will add a node to tree. To add a node $$$u$$$, we can use centroid decomposition on current tree. Let the centroid of the tree is $$$m$$$. There are $$$k$$$ child of $$$m$$$, $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$. Assume that the size of subtree is nonincreasing order, $$$|Subtree(v_1)|> ... > |Subtree(v_k)|$$$. Ask query $$$(u, v_1, v_2)$$$. If the answer is $$$u$$$, then $$$u$$$ is on the path from $$$v_1$$$ to $$$v_2$$$ and we can find the location of $$$u$$$ by one more query: $$$(u, v_1, m)$$$. If the answer is $$$v_1$$$, we can restrict the range to $$$Subtree(v_1)$$$, so we can do centroid decomposition on $$$Subtree(v_1)$$$ recursively. The case of $$$v_2$$$ is similar. If the answer is $$$z$$$, a totally unknown node, then make an edge between $$$u$$$ and $$$z$$$. $$$z$$$ is on the path from $$$v_1$$$ to $$$v_2$$$, so we can handle it similarly. If the answer of the query is $$$m$$$, then just move to query $$$(u, v_3, v_4)$$$, .. and so on. If the process is finished and can't find the location of $$$u$$$, then add an edge $$$(u, m)$$$.

      18*18*8>2000, so I think 9+9+4 query is enough to last insertion. Also, former insertions needed smaller number of query.

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

After some hour struggling to solve Meetings problem, I suddenly realized that this problem is very similar to This Problem in CSAcademy, which I solved it before. The only difference between two problem is the constraints of input tree. (Meetings : max degree <= 18, CSAcademy problem : trees are generated with RNG) I copy-pasted my previous code and it gave me 100 points.

I'm not blaming the problem setters, (There are way too many problems in the world, and it is very hard to avoid the coincidence) but I just feel sad that I became more stupid than last year...

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i woke up 4:00 am because of this contest and the contest started after 1.5 hour. So can someone tell me when is the second contest exactly ?

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

    I don't know but I expect that it is 90 minutes after contest (10:30 — 15:30 UTC+9), because such information is written in contest information page.

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

How to solve day 1 naan?

I solve the small subtasks by a greedy approach but the numbers grow quickly and exceed the limit for the last subtask with the same solution.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    I've used some __int128 + hack that if you want to make a fraction (A, B) with $$$B > 10^9$$$, just convert it to fraction

    ((A * 10^9 + B — 1) / B, 10^9).

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +30 Vote: I do not like it

    Break the naan evenly(by happiness) into N pieces for each person.

    Call p(i,j) as the position of the jth cut for the ith person The B of p(i,j) should be N*v<=2e8

    Repeat j from 1 to N, take the smallest p(i,j) out of the remaining people and stop considering i afterwards

    It is easy to see that it works (its just a slight modification to the greedy)

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

Has Day2 started yet? Or is it delayed

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

how to solve day2 first problem antennas?

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

If it's not hard, could you please add all previous day's problems in the analysis session? yutaka1999

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

How to solve d2p1? To me, it seems the hardest problem in day 2..

BTW, p2 and p3 were interesting, too. Great contest!

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

    It was hard but I guess not the hardest. Though hard to explain.

    For each query $$$[L, R)$$$ I find $$$i, j$$$ $$$(L \leq i < j < R)$$$ which both can see each other and $$$H_i - H_j$$$ is maximum. (To solve the whole problem reverse the array and run this again)

    In this way $$$i$$$-th antenna can communicate with antennas in $$$[i+A_i, i+B_i+1)$$$ so make it two event. Add this antenna at $$$i + A_i$$$ and remove it at $$$i+B_i+1$$$. Set $$$c_i$$$ to $$$h_i$$$ if this antenna is present now and $$$-inf$$$ otherwise. Set $$$d_i$$$ to currently maximum difference value $$$H_j - H_i$$$.

    Now sweep from left to right and process events. After processing events till $$$j$$$, the answer for every queries $$$[l,j)$$$ is $$$min(d_l, d_{l+1}, .., d_{j-1})$$$. Also for the $$$j$$$-th antenna and every antenna $$$k$$$ which $$$j - B_j \le k \le j - A_j$$$ update $$$d_k$$$ to $$$max(d_k, c_k - H_j)$$$ (notice that if $$$k$$$-th antenna is not present then $$$c_k$$$ is $$$-inf$$$ and $$$d_k$$$ doesn't change).

    We can implement changes to array $$$c$$$ and $$$d$$$ using segment tree with lazy propagation. So it's done in $$$O(nlgn)$$$ time complexity.

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

      At "antenna k which j−Aj≤k≤j−Bj", shouldn't it be j−Bj≤k≤j−Aj ?

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

        Yup. My mistake, thanks!

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

      Hey, can you explain the segment tree part? How are you modifying dk to max(dk,ck-hj)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think it is max(dl, dl+1, ..., dj-1)

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

Will there be editorials in English after the camp has ended?

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

How to solve dishes from day 2?

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

    I got 74 points in contest, and there was a little typo. I upsolved it.

    Let $$$X[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[i]+B[1]+B[2]+...+B[j] \le S[i]$$$. Likewise, $$$Y[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[j]+B[1]+B[2]+...+B[i] \le T[i]$$$.

    Put a blue point in $$$(i, X[i])$$$ with score $$$P[i]$$$ and red point in $$$(Y[j], j)$$$ with score $$$Q[i]$$$.

    Order of steps can be represented by a path from $$$(0,0)$$$ to $$$(n,m)$$$ in lattice graph. $$$(i,j)$$$ means you already have done $$$i$$$ steps of IOI Donburi and $$$j$$$ steps of JOI curry.

    For a path, the whole score of process is (sum of scores of blue points above or on the path) + (sum of scores of red points below or on the path).

    It can solved directly with segment tree and lazy propagation in $$$O((N+M) log (N+M))$$$ time, but there are something to handle, so I tried to make it easier.

    For each red point in $$$(x,y)$$$ with score $$$q$$$, make it blue and change its location to $$$(x+1,y-1)$$$ and change its score with $$$-q$$$. After this process, only blue point remains and the problem becomes easier. After calculate answer, you should add $$$q$$$ for each red point. Then you can get the same answer with original problem.

    Only blue-point problem can be solved by segment tree. Time complexity : $$$O((N+M) log (N+M))$$$ .

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

Is there a way to solve task "examination" from day 1 without 2D binary indexed tree?

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

    use MO's algorithm

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

      Can you elaborate a little bit? I don't really see how MO's algorithm is related to this problem.

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

        you just put pointer 1 on A and pointer 2 on B, and maintain a BIT on a+b values

        Then you just do like how you do it on regular Mo's

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

    It can be solved by (CDQ) divide-and-conquer.

    Sort all students and queries together by one of the 3 parameters. Recursively divide them into halves according to that parameter.

    For each sub-problem obtained from above, consider only students in one half, only queries in another half. Re-sort them together by one of the two remaining parameters. Then handle each of them by operations on a segment tree based on the last parameter.

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

    you can use ordered_sets in segment tree.

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

    Interesting solutions. Thanks.

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

    Here is my method :

    Represent students as points $$$(x, y)$$$ where $$$x = S_i$$$ and $$$y = T_i$$$.

    In subtask 2, we want to know the number of such points in $$$Q$$$ infinite rectangles covering all points $$$(x, y)$$$ with $$$x \geq X_i$$$ and $$$y \geq Y_i$$$. Sort students/points by decreasing $$$S_i$$$. Sort rectangles by decreasing $$$X_i$$$ and process them in this order, adding step by step "new discovered points" in a 1D segment tree on ordinates.

    After adding all "new points discovered with $$$x \geq X_i$$$", do a Range Sum Query on $$$[Y_i ; +\infty[$$$ to know the answer for this rectangle. Final complexity is $$$O((N+Q+Y_{max}) \log Y_{max})$$$.

    Subtask 3 : Thinking on paper, we see that we're now querying the intersection of an infinite triangle and an infinite rectangle. I count the number of points in the "big triangle" and I substract the number of points in the "little triangle" below the rectangle. I use two segment trees, one on $$$T_i$$$ values, other one on $$$S_i + T_i$$$ values. It needs two different passes with different sorting. There are some rectangles which should be treated as in subtask 2 instead (when $$$Z_i$$$ is useless).

    Substask 4 : I used dynamic segment tree, it's slow but it pass the TL.

    Code : https://oj.uz/submission/102091

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

    I got a solution:

    Lets divide our queries into 2 types : a+b>=c and a+b<=c

    1. For type 1(a + b >= c) : we could only consider a and b, thus the answer could be easily found(use sweeping line and BIT or else).
    2. For type 2(a + b < c) : consider the image below

      \|
      \|
      \|"This area is what we want"
      \
      |\
      ----------------------------------------------- "limit A"
      |\
      |\"limit C"
      "limit B"

      and this is equal to area X — area Y
      \
      \
      \"Area X"
      \
      ----------------------------------------------- "limit A"
      \
      \
      \"limit C"
      \"Area Y"|
      \|
      \|
      \|
      |
      |\
      |\"limit C"
      "limit B"
      And it's easy to find Area X and Area Y(same technique as you find the answer for type 1)
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I did manage to approach the problem till this point but I don't know how to go further. So we need compressed 2-D BIT? Can you share your code so that I can learn from it?

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

        no just sweeping line and 1D-BIT( or treap or anything else)

        for example, to get the size of Area X, you put all points satisfying limit A into your data structure, and ask how many of them is above limit C.

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Someone asked me how to solve transportation. I'll leave it here.

53N+1 queries
31N+1 queries
29N queries
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Also, transportation is a cool innovation because now we can see, there can be a lot of problems like on distributed code jam at IOI format :)

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

      How?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it
        Spoiler
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Ohh... that’s a nice trick (and a good alternative to constant optimization)

»
5 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Hi everyone, let's raise my contribution please))

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

what is solution for problem 1 or problem 2?

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

    I assume you are talking about Day 3. Q1: Centroid Decomposition.

    Choose a centroid, and assume you pick nodes from subtress of at least 2 children from it, or you pick the node itself.

    Then you can do greedy, greedily pick the node that descreases the cost most. By some small-to-large, you can compute the costs in O(size*lg).You then update the answer of [1,size], so solving a subtree is O(size*lg), and overall complexity is O(N*lg^2)

    I think you need special handle for E=1, but shouldn't be trouble. For E>=2 we only pick leaves actually, but i don't see how to use that.

    Q2: Simple DP.

    Note that there exists a optimal solution that does all "set range" before "flip range". Also, all "set range" do not overlap itself, and same for all "flip range".

    Consider that you have x "set ranges" and you have to open/close range for y "flip ranges". Then the cost is x+ceil(y/2).

    Run DP from left to right, maintain dp[i][j], which is the minimum x+y you can do, for prefix i,

    j=0: no "set ranges" are opened

    j=1: You have opened a range for "set range to 0" and haven't closed it

    j=2: You have opened a range for "set range to 1" and haven't closed it

    Then you can do transition, as following:


    for(int i=1; i<=n ;i++){ for(int j=0; j<3 ;j++) dp[i][j]=1e9; for(int j=0; j<3 ;j++){ for(int k=0; k<3 ;k++){ int cur; if(k==0) cur=(a[i]-48)^(dp[i-1][j]&1); else cur=(k-1)^(dp[i-1][j]&1); dp[i][k]=min(dp[i][k],dp[i-1][j]+(k!=0 && k!=j)*2+(cur!=b[i]-48)); } } }

    I tried the best to explain :)

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

      i got it, Thanks.

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

      I have came up with solution of "Designated Cities" similar to you (greedy, with centroid decomposition $$$O(n \log^2 n)$$$), but there was more better solution explained by maroonrk in the editorial time of onsite contest. It was a genius-like solution.

      First, think about the query of $$$E = 2$$$. It can be solved by DP in $$$O(n)$$$. Then, realize that the designated cities of optimal solution for $$$E \geq 3$$$ completely includes the optimal solution for $$$E = 2$$$. Therefore, it means that greedy will work after we determined two vertices when $$$E = 2$$$. The time complexity is $$$O(n \log n)$$$.

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Problems from Day 3 are all available here: https://oj.uz/problems/source/378

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve Day4 Q1?

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

    Sort by $$$C$$$. Let $$$F(i, j)$$$ be a max. possible cost obtained from interval $$$i, j$$$ (paying exactly $$$2(C_j - C_i)$$$ for circular tour). Let $$$opt(i)$$$ be the maximum $$$j$$$ such that $$$F(i, j)$$$ becomes maximum.

    You can prove that $$$opt(i) \le opt(i+1)$$$, and you can calculate $$$F(i, j)$$$ in $$$O(\log N)$$$ using persistent segtree, thus you can use D&C optimization to solve the problem in $$$O(N\log^2 N)$$$.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      How to prove that opt(i) <= opt(i+1)?

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

      In fact you can solve it without persistent segtree. Using that fact, that if you will store two pointers at the current segement, and will move it during the D&C (and maintaining two sets, classic) it will be $$$O(n \log^2 n)$$$

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

      I realized that calculating $$$F(i, j)$$$ is just finding the sum of M-2 maximum elements in range $$$[i+1, j-1]$$$, how can we solve this in $$$O(\log N)$$$ per query?

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

        Construct persistent segment tree for every prefix, and for each query walk down the tree like binary search.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve day 4 Q3? My divide-and-conquer solution only gave me 40 points.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Erasing an element also provides your some information. So you don't need to erase everything in the set when you solved $$$[l, r]$$$ and want to solve $$$[l, mid]$$$ and $$$[mid+1, r]$$$.

    2. You want to split some set into two halves. If one of them is full, you don't need to make a query to know which set it belongs to. To avoid hacks, random shuffle the set before making queries.

    3. Do not set $$$mid = (l+r) / 2$$$, try something like this: $$$mid = l * ratio + r * (1 - ratio)$$$.

    My code

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

      What is the reason not using 0.5 as $$$ratio$$$?

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

        The real reason is $$$T(n) = T(x) + T(n-x) + n + \min(x, n-x)$$$.

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

    With some careful implementations and dirty optimizations, we can make it into about $$$9.705 * 10^5$$$ queries for $$$n=43000$$$ and $$$9.952 * 10^5$$$ queries for $$$n=44000$$$.

    My code

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm not sure what the cause is, but when I download https://cms.ioi-jp.org/dataset/day4-data.tar.gz and extract the file, the following error pops out:

gzip: stdin: unexpected end of file
tar: Unexpected EOF in archive
tar: Unexpected EOF in archive
tar: Error is not recoverable: exiting now
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe your download was corrupted? It is working fine for me. Try re-downloading.

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

      It works now, probably the files were fixed

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

        Please add them quickly. I am waiting for you to complete so that I can update OI Checklist :D

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

          It would take some time to complete, because there are too many unusual problems this year and they cannot be automatically uploaded. I expect 2-4 weeks.

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

            Its Ok. I just needed the links to update the list. Thanks. :)

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

Will there be editorial for all the problems?

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

What is the team that will go to IOI?

»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it

You can solve every problem of JOI Spring Camp 2019 here: https://oj.uz/problems/source/375

However there are two probable issues:

  • Checker of Naan: I implemented using __int128 believing that the happiness of the fractional part of both ends can be represented within 128-bit numerator/denominator, but maybe my calculations were wrong. This is the code, hope there are no bugs.
  • Transportations — this is the first Communication task, so maybe there could be some unpredicted bugs :)
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I make a submit for problem Road Service (day 2 B)?

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

Hi, I was trying to upload mergers from day 4 to my country's online judge, but when i downloaded the input there were a few input files like "0123.txt", does that mean that I should put this input file in multiple subtasks or something? Can someone help pls? Thanks :)

[Edit: Solved]

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

Hi, can anyone who have solved d3p3("Bitaro who leaps through time") please describe ur solution? Thank u.

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

Can somebody explain solution for Day 3 Problem 3 — Bitaro, Who Leaps Through Time? Thank you!