DEGwer's blog

By DEGwer, history, 9 years ago, In English

Tomorrow, we have JOI Open Contest 2015 .

This is OI-like contest on CMS and prepared by Japan to practice IOI.

There are two rounds using same problems. You can participate whichever you want.

The first round is 04:00~09:00 GMT June 14, and second round is 10:00~15:00 GMT on same day. And since the server will be open until 14:00 GMT June 15, you can practice this round at any time until then.

Please don't talk about problems until second round will be over. I'm looking forward to see a lot of IOI-er and programming contest lovers at this contest!

UPD1: Contests has been over. It is free to talk about the problems from now. You can still practice until the server will be closed.

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

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Could you give links on timeanddate.com, It will be easier to check time.

UPD: Links: Round 1, Round 2

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

Expected difficulty?

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

Where is the Registration link?

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

Site seems to be down. Can anybody upload statements somewhere?

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I have submitted my output a few mintes ago but it's still evaluating :((

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

The evaluation is taking more than 20 minutes on the last problem... Is everything ok?

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

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

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

where is contest #1's results?

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

Good and hard contest, thanks a lot! Is there any editorial of the problems? :)

»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Could you please upload somewhere an archive with all tests for the tasks?

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

Anybody could submit the solutions and/or explanation? Because we can only test our solutions the next 19 hours and I think that I couldn't code them without reading them as I am still learning and very far away from this kind of contests

cheers!

»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Could you publish the final standings of the contest?

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

Anyone solved the last problem by converting given numbers. Into base k — except when k is one — and using a segment tree?

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

    Pretty much! My solution is technically very similar, although I reasoned differently: since every dish contains at most 109 cells, then, if we use the spray on it at least 32 times, it is guaranteed to become empty. Therefore, I could store answers to the question "what the sum on this segment would be after i applications of the spray" for 0 ≤ i ≤ 32 in every node of my segment tree.

    Alex_2oo8 proposed another interesting solution using a segment tree: using the same observation, we observe that, if we don't apply the spray to empty dishes, then, without any updates, we can have 32 × N applications of the spray at most, and each update adds at most 32 additional applications. Therefore, we can actually apply the spray to dishes one-by-one, and the only problem is finding the non-empty dishes quickly, which is easily accomplished by a segment tree. This solution wouldn't work if we were allowed to update the number of cells in a segment of dishes at once, but I imagine that it was easier to implement.

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

      I think our solutions r really close yeah but yours is so simpler and the second solution is interesting :DThnx for sharing

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

    I was using a sqrt decomposition. Each value can be mapped by using a map(in c++) or some other data structures.For each dividing query(spraying query), we spray to every dish which isn't empty(that is whose value is positive number). I think this solution is similar to Alex_2oo8's solution,but I was using a sqrt decomposition instead of a segment tree for finding the non-empty dishes and spraying to them.

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

What is the expected solution of the second task (Election Campaign)? I solved it in O((N+M) log N), but I'm curious to know whether there is a linear or simpler solution.

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

How could we reach the problem statements and practice with them? I logged in to the system and it said the contest has ended.

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

Could you upload the statements (if it's possible, test data as well) to somewhere?

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

How to solve election campaign ?