hogloid's blog

Announcement of JOI Open Contest 2014 (Re-post)
By hogloid, 10 years ago, In English

Inheriting JOI Open Contest 2013 last year,JOI(Japanese Olympiad in Informatics) will hold two contests mainly for high-school students who enter IOI 2014 to practice for IOI(of course, everyone can participate)

The site is here: http://cms.ioi-jp.org/open-2014/index.html

You can see details in the site. First contest will be held on Sunday, June 22, 2014. Second contest will be held on Sunday, June 29, 2014. The problem statements are in Japanese and in English.

Each contest has 2 rounds in different time(for those who are in different timezone from Japan;but you can participate in the round you like). 2 rounds have the same problemset. The contest has 3 tasks in 5 hours.

Last year, we used Facebook/Twitter authorization,but we use normal authorization this year. You can register for the contest from the time 30 minutes before the contest beginning(You can register even if it is after contest).

Good luck in IOI :))

(note that I won't enter IOI anymore)


I've made a mistake ; I put "Discard" to cancel the change. But this button is to delete all.

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

Comments Comments (28)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Will the rankings be merged? I noticed that there's only the first session's ranking present. (I'm not sure if it's a good idea to provide the ranking during contest, though. And not just because it tells people "If you've wasted a lot of time on problem 3, there's a good reason. Drop it and try solving something else.")

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

    Well, official ranking for both first & second round will be published, but it is not decided that they will be merged.

    We thought if you want to participate in IOI-like style, you don't see the ranking.

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

      It's tempting, way too tempting... basically being provided a way to procrastinate even during a contest :D And I briefly saw the ranking ("oh, problem 3 is hard to solve for full") of the 1st contest about an hour before its end.

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

Do anyone know how to solve Subtask 3 of Factories?

I used Shortest Path to solve Subtask 1 and LCA plus brute-force for Subtask 2.

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

    I have a solution in (V is the number of vertices in all queries). It passes just barely, in 5.5s max time.

    Do HLD on the tree (with an arbitrary root); for each vertex v in each query, traverse the paths from it to the root and remember triples (path, lowest vertex visited on that path, depth of v). That can be done quickly by jumping to the top of the path, and since there are just distinct HLD paths encountered from each vertex, there'll be just of them in total over all queries.

    Instead of trying all LCAs, we'll try just all paths that could contain an LCA and all vertices on them that could be an LCA, since the LCA of a, b must be one of the "lowest visited vertices". Suppose we chose 2 such triples (p, x, da) and (p, y, db), where x and y belong to different companies; then, the distance between a, b is at least (and exactly that if the higher of vertices x, y is the LCA). We just want to minimize it, so if we sort all triples on each path by depth, we can iterate over x by decreasing dx, remember the smallest db (from the other company) of all y with dy ≥ dx, and we can find the minimum for each a.

    Time complexity gets another due to sorting.

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

      what do u mean by HLD ??

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

      What does the lowest vertex visited on that path mean? Does it point to the path's endpoint?

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

        Suppose you went from some vertex v to the root, and noted for each vertex visited this way, which path (from HLD) it lies on. The "lowest visited vertex" of path p is just the first vertex visited this way, for which we note that it lied on path p.

        From the way the HLD paths are constructed (they only go up on the tree), we know that from this vertex, we go up that path until its topmost vertex, always noting the same path p, and afterwards, we won't note p ever again. That, and the fact that there are just distinct p which we could note this way, are very useful properties of HLD.

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

does anyone know fortune_telling solution ? i am badly stuck with it

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

    Notice that we consider each card separately, so we can sort them by . Now, we can try to find the answers for them in decreasing order. Let's denote the rotation in which ai > bi as 0, the other as 1 (if ai = bi, we don't have to care). We can say that the card has rotation 0 at the beginning; if it doesn't we just add a dummy operation with 109.

    Suppose you chose a card i in rotation 0 and write an array of: 0 for an operation with value  < bi, 1 for value  ≥ bi and  < ai, 2 for value  ≥ ai. Each operation with 2 always rotates the card; those with 0 do nothing and those with 1 rotate the card if it had rotation 1. This last bit actually means that after this operation, a card will always have rotation 0!

    What does it mean? Just find the last 0 and count the number of 2s after it; the resulting rotation is equal to this number of 2-s, mod 2. If there's no operation with 1, the situation's trivial — just count the number of 2-s in total.

    Since we're decreasing bi, we're just adding 2-s, so their number can be modified and calculated dynamically with a simple BIT. The largest position of an operation's value in a given range can be found by sorting the values and asking for maximum of a range, which is again just an interval tree (or RMQ, since there are no updates). Time: .

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

      Can you tell me your solution of Problem C: Space_Pirate ?

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

        I don't have a full solution (as you could notice from the rankings), but you can get 47 points just for bruteforcing all pairs (a, b). There are cases "you can get to a from b" and "you can't", which have different cycle lengths. You can just find all distances of pairs of vertices, the order in which we see vertices when starting from any vertex (until we start cycling) and cycle lengths related to them. Then, it reduces to a simple "which is the k-th vertex from a?", where you subtract the cycle length from k (smartly, using division) and when it's sufficiently small, just find the value from the order of visiting vertices from a.

        The special case of all components of this graph being cycles has some easy parts: if we can't reach a from 1, i is always the same; if we can't reach i, there's exactly 1 choice of b for each a, so the answer for that i is the size of the cycle containing 1. If a, b, i can all be reached from 1, (for simplicity, let's say that we just have 1 cycle with vertices 1..N on it in that order) the cycle length is N - (b - a - 1) and the distance to i from 1 (if i can be reached from b, e.g. i ≥ b or i ≤ a) is i - (b - a - 1), so we need to find the number of solutions (a, b) to . For that, trying all c = N - (b - a - 1) in the same way as Erathostenes's sieve should work.

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

          I do not know where the rankings are. Can you please give me the link ? and thanks for the solution :)

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

            Just click on the link from the blog post, there's another link saying "ranking" right at the top.

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

How do you solve the task Pinball?

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

    This was my key observation: it is sufficient that, if the ball appears in the leftmost and the rightmost column, it arrives in the same final column.

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

      Thanks, I got AC! I realized such "little" observations are very crucial to get AC!

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

      fram could you please elaborate. Thank you.

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

        Consider the devices starting from the top.
        You want to compute the answers to this question, for i = 1... M:
        "What is the minimal cost so that, if a ball appears in the leftmost column, it falls into device i?" Let's call the answer cL(i).
        We have a nice formula for cL(i): 
        - if A[i] = 0, then cL(i) = D[i]
        - otherwise cL(i) = min{cL(j)} + D[i] for j < i such that A[i] ≤ C[j] ≤ B[i]
        (that is, the ball falls from device j to device i)

        Using a range tree you can calculate minimum in time.

        Do the same for the right side and the final answer will be of the form cL(i) + cR(i) - D[i]

        It works because (at least in the optimal set-up) the devices chosen for the left and right side are different, otherwise taking device i would be useless.

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

          I figured this out after that hint of yours but thank you so much. great explanation. The problem is all so simple after that 1 crucial observation.

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

Does anyone know how to solve "Secret" for full points?

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

    I use divide and conquer approach, In Init, compute for a segment L..R, assume M = (L+R)/2, compute every Suffix of L..M and every Prefix of M+1..R to answer every query(FL,FR) where FL <= M and M+1 <= FR in one call then do the same for segment L..M and M+1..R, this approach use 7978 calls in Init when N = 1000

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

Hi, So, I am really Bad at the type of problem A of Day 2. Can everyone share their ideas ?

Thanks a lot :)

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

Could anyone upload&link the problem statements? (By PM is also ok, if we don't want to spam.)

UPD: I've got them now.

→ Reply