yosupo's blog

By yosupo, history, 2 months ago, In English,

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://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!

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

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

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

    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.

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

    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.

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

      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).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest page is now open and you can register!

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    Yes(And same as japan regional, you can use unlimited number of pages.)

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve G and I?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

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

    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

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

      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

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

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve B?