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

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

Hello Codeforces!

On 16th September Japan Alumni Group Summer Camp 2018 Day 2 Contest will take place on AtCoder Contest link(You cannot view contest page yet). This contest is not an official AtCoder round, so it is not rated.

The contest is ICPC style practice contest, and you can take part in it as a team. But you cannot use more than one computers, browse the internet, or copy-paste your library. Since AtCoder does not support team participation, please make a new account and share it if you want to compete as a team.

The problems are prepared by maroonrk, sigma425, sugim48, and me. Some of the problems were used in Petrozavodsk camp last winter, so if you participated in it, please refrain from competing in this contest. Note that the problems are not used in AtCoder Petrozavodsk Contest (see https://mirror.codeforces.com/blog/entry/57395 ).

The contest starts at 10:00 (GMT+9:00) and lasts for 5 hours. The standings will be frozen 60 minutes before the end of the contest.

Hope you enjoy the contest!

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

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

Hi, all! I'm a staff of the summer camp. We also welcome Day 3 contest which is prepared by the Japanese Alumni Group of ICPC. However, Day 1 contest is limited to the participants in the summer camp because we will use a past ICPC contest.

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

    Well, we purposefully hid Day 3 contest, but since it was posted here, let me clarify.

    AtCoder is not involved in the preparation of these contests in any way. We just give the judge server.

    The writers of day 2 contests are good, I recommend it.

    However, to be honest, I don't recommend day 3 contest — it tries to imitate the style of Japan regional contest, which is quite implementation-oriented.

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

    I am not a staff, but participant of last year(I already retired).

    Contest in Day 3 is made in purpose to practice for ICPC Asia regional contests. It is easier than usual World Finals or Open Cups, so if you are aiming to get some medals in next World Final, the contest can be a bit too easy for you (and you might be able to solve all problems in 3 hours or some).

    But for those who are aiming to just join in next World Final, it should be good opportunity. The problem setter, Japanese Alumni Group, is experienced team. There should be well-prepared problems, and thanks to AtCoder, stable judge system.

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

      Yes, AtCoder just lends us the server, the problems are prepared by only JAG. We thank AtCoder for approval to use the excellent judge system.

      The purpose of the Day 3 contest is to practice for Japanese ICPC. The trend of the problems is different from the usual AtCoder's contest (ABC, ARC, and AGC).

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

The contest page is now open and you can register!

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

Is it allowed to use a 25-pages notebook (like in usual ACM ICPC contest)?

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

How to solve G and I?

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

    G : In the book "Looking for a Challenge" they have a detailed explanation on similar problem (Straight Lines)

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

    For Problem I: Consider a function f that consists of a sequence of division and addition. If there are >=30 divide operations (ignore divide 1) then f(3e8)-f(0)<=1. Also, f is monotonic. Therefore, we can construct a lazy tag that has two states: Either there are a sequence of length <30 of pairs of (div,add), or 3 integers split,v0 and vinf such that f(0) to (sp-1) = v0 and f(sp) to f(3e8) = vinf. Also, we save a tag for restore operation. Complexity is O(N+QlgNlg(3e8))

    https://beta.atcoder.jp/contests/jag2018summer-day2/submissions/3214104

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

      In fact there's a way to solve the problem in time.

      Consider a tag is a function like , you can merge two functions quickly. However, when b is too large, you can't store b but it's obviously that f(x) is either k or k + 1 when 0 ≤ x ≤ 3 × 108, so there's another form of f(x) : f(x) = k + (x ≥ something).

      https://beta.atcoder.jp/contests/jag2018summer-day2/submissions/3215973

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

        And we can convert to f(x) = ⌊ x + (BIG - something) / BIG⌋ + k, it decrease implementation, maybe.