rng_58's blog

Yahoo Programming Contest 2019
By rng_58, history, 6 years ago, In English

Recently we noticed that the number of international participants to ARC-level contests are declining, so we decided to make announcements here.

When a contest is rated for ~2799, regardless of the name of the contest, the problems are prepared in the same way as ARC contests. We try to make the contest interesting even for reds (by the way, you can estimate the difficulty from point values). I think it's rather a div 1.5 contest rather than a div 2 contest (In this particular contest, since there are no divisions, the contest is like div 1.5 + div2 + div3 contest). We always have English editorials for ARCs these days.

Yahoo Programming Contest 2019 will be held on Saturday (time). The writer is DEGwer.

Contest Link

Contest Announcement

Contest duration: 120 minutes

The point values will be 100 — 200 — 400 — 600 — 800 — 900.

Let's discuss problems after the contest.

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

Comments Comments (23)
| Write comment?
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

What is the difficulty level of 600....900 in atcoder as compared to codeforces(like is it of div2 D/E) ?

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

    It's difficult to say, but generally, we try to make ARCs a bit harder than CF D2 (because it's rated up to oranges).

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Legit thought this was for Yahoo! the American website.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The time links says that event has passed.

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

Recently we noticed that the number of international participants to ARC-level contests are declining, so we decided to make announcements here.

And you didn't bump it. :/

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

How to solve E?

Also, is there a better solution to D than the standard interval-with-maximum-sum segment tree, but with three parts EVEN-ODD-EVEN? That solution was a nightmare to write :/

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Gauss

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    E : Treat the rows as a m-bit string, and find the number of subsets with xor 0 using Gaussian Elimination (answer is 2n - rank). Then, note that if you fix a subset of rows, the number of subsets of columns that work is 2m - 1 unless the xor of each row in the subset is 0, in which case the answer is 0.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    You can solve D with 2 arrays for prefix min path/cycle and 2 for suffix min path/cycle.

    For E, note that if we fix a number of columns and there's at least 1 row with odd sum in these columns, there will be 2^(n-1) ways to choose rows, otherwise 0. So for each row we can count the number of ways to choose other rows/columns so that it has odd sum. Now, we need to remove sets that we counted twice. We can uniquely remove these by fixing (i, j) as in i is the first row that has odd sum and j also has odd sum. To find the number of ways to choose columns for these, you can use xor gaussian elimination.

    Edit: Looks like it's simpler than what I thought. :P

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please explain briefly how you handled Even-Odd-Even case? Editorial has mentioned a different approach.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      We can pick a initial path that goes over some part of the values an even amount of times, then some part an odd amount of times, then some part an even amount of times again.

      Build a segment tree over the interval. For every segment i, find val[i][a][b]: How much we decrease the amount of needed operations, if we go over this interval, such that we start at part a, and end at part b, where part 0 is the initial even, part 1 is the odd, and part 2 is the last even.

      Also find left[i][a]: How much we decrease the amount of needed operations, if we go over some suffix of this interval, with the suffix ending at part a, and right[i][a]: How much we decrease the amount of needed operations, if we go over some prefix of this interval, with the prefix starting at part a.

      At every segment also find ans[i]: The maximum amount we can decrease the needed operations by by traveling over some segment in this interval.

      Updates are really laborious. For example,

      val[i][0][2] = max(val[2*i][0][0] + val[2*i+1][0][2], val[2*i][0][1] + val[2*i+1][1][2], val[2*i][0][2] + val[2*i+1][2][2])
opt[i] = max(opt[2*i], opt[2*i+1], left[2*i][0] + right[2*i+1][0], left[2*i][1] + right[2*i+1][1], left[2*i][2] + right[2*i+1][2])

      But there's no reason why you would ever want to do this when there are no change-queries, so that's my bad :P

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For D: you can just use dp with 3*n states representing the 3 even-odd-even states for each index. submission

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      amnesiac_dusk can you explain more ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Its clear as explained above that snuke will move first over a segment even, then odd, then even number of times. Now, let dp[i][j] be the maximum number that can be reduced if snuke has moved upto ith dot and in the jth kind of segment(0-first even, 1-odd, 2-even). Now, if we consider a even stone in odd segment or vice-versa, It cannot be completely removed and we can update dp by a[i]-1 otherwise by a[i]. See my submission for more clarity.

        → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

how to solve problem d , ears ?

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone tell what is wrong with following approach of D? I checked for all starting position of i. Now, if we fix starting position,I determine ending position by ternary search on cost values from (start+1,end) as it seems function of cost will be decreasing and then increasing. Then will take minimum cost among all i's. It is passing half of test case but failing on rest. Submission

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is about problem D .

how to formulate dp state from it :

Therefore, the problem can be solved by dynamic programming in OLtime, where DP[i][t]: (the minimum number of operations required considering up to thei-th ear when we already passedtof thefour pointsD; S; T; U)

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

It would be great if AtCoder has problem tags. It's DP problems are really very nice.

→ Reply