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

Автор E869120, 7 месяцев назад, По-английски,

Square869120Contest #5 will be held on Sunday, April 15th, 20:00 JST.

About Square869120Contest

  • This contest is unofficial.
  • Square869120Contest has been held 4 times before, and this is the 5-th contest of Square869120Contest.
  • From the 3-rd contest, both Engish and Japanese statements are prepared.

Contest Information
  • Time: Sunday, April 15th, 20:00 JST
  • Duration: 240 minutes
  • Tasks: 9 (Consists of 8 algorithm tasks, 1 marathon task)
  • Writer: E869120, square1001
  • Rated: No (unrated)
  • The first problem is as easy as Codeforces Div2 A, and the last problem is as hard as Codeforces Div1-D,E problems. In addition, there are many partial scores. I think all participants can enjoy the contest.

Scoring
Task ID Max Score Partial Scores
A 200 100+100
B 300 70+140+90
C 500 90+100+310
D 600 120+160+320
E 800 40+160+190+410
F 1000 60+60+250+630
G 1200 80+320+[0 ----- 800, 1-point unit]
H 1400 210+320+870
I 1500 Marathon Task, 1-point unit

Past Contests
Square869120Contest is one of the unrated contest which have a long history. There's 4 previous contest, so you can solve them to practice this kind of contest.



Updates
1. Some of the partial scores has changed. Please check.
2. Some of the partial scores has changed. We think the point values are determined.
3. The contest is over. Thank you for your participation!
4. English editorial will be published on Thursday, 4/19/2018.
5. English editorial uploaded. Link

We are looking forward to your participation! Let's participate and enjoy!!!!!
 
 
 
 
  • Проголосовать: нравится  
  • +61
  • Проголосовать: не нравится  

»
7 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Will there be english analysis?

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

    This time we'll put some effort to make an English editorial (at least brief full-score solution explanation of problems except problem I).

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

      Hmmm there is no English Editorial ...

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

        Look "Updates" in the announcement blog. The English editorial will be published on Thursday, 4/19/2018.

»
7 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

[Reminder] The contest will start in 3 hours.

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

How to solve problem "Lunch Menu"?

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

    I solved it with DP.

    Now we consider array a[1...n] and we know the position p such that a[p] = max(a[1...n]).

    We can:

    Not erase position p:

    In this case, every queries have l(i) <= p <= r(i) will pick p, so the total cost = "number of queries such that l(i) <= p <= r(i)" * a[p].

    After that, we can skip queries that have l(i) <= p <= r(i) so we can split array [1...n] to array [1...p-1] and [p+1...n].

    With that observation we can think about DP with f(l, r, ...).

    Erase position p:

    We can store variable lim so that next time we only consider position i such that a(i) < lim.

    We can compress array so lim <= n.

    After merging 2 cases, we can know which states we need to store.

    So DP will look like f(l, r, number of elements we can erase, limit).

    DP transtion tooks O(N). So total complexity is O(N ^ 5).

    My code: https://pastebin.com/iczqhRcZ.

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

The complete English editorial of this contest uploaded.
Thank you for your participation!

Link to Editorial