E869120's blog

By E869120, 7 years ago, In English

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!!!!!
  • Vote: I like it
  • +61
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Will there be english analysis?

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmmm there is no English Editorial ...

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

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

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

[Reminder] The contest will start in 3 hours.

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve problem "Lunch Menu"?

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

    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 years ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

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

Link to Editorial