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

Автор maroonrk, история, 3 года назад, По-английски

We will hold AtCoder Regular Contest 133.

The point values will be 300-500-500-700-800-1100.

We are looking forward to your participation!

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

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

Another maroonrk round!

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

someone who did Problem B using bipartite matching ?

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

    Is there a solution using bipartite matching?

    UPD: the answer is no, why downvotes?

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

      I was thinking of doing something using Hopcroft but was not able to implement, asking here if somehow someone was able to figure out how to cancel out alternating edges to find maximal matching

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

Problem B reduces to a previous atcoder problem called "cross-free matching" https://atcoder.jp/contests/arc126/tasks/arc126_b

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

Can anyone explain why we sorting as (i,-j) in B.

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

    Consider another defintion of the dp:

    If we go from left to right in p[], we want to pair the current element p[i] with one of the q[j]. We previously searched all indexes in q[] where we find multiples of p[i], let pos[i] be the list of indexes in q[] that are multiples of p[i]

    So, let dp[k]=max possible length of an common subsequence ending in q[k]. Then

    dp[pos[i][j]]=max(dp[0..pos[i][j]-1])+1 for all positions j and current i

    We can solve this with an extra structure like a segment tree. Or, we just sort all the indexes in pos[i] biggest first, and create the LIS on that list.

    Edit: Changed LCS to LIS

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

      What is LCS referred to? Can you explain by taking an example.

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

        Actually I wanted to write LIS here, as mentioned in the tutorial, the longest increasing subsequence.

        I think I mixed it because the problem is related to the LCS, the longest common subsequence, see LCS

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

I have a different approach for C.

If we write the sum as $$$\sum_{i=1}^nA_i+K*w_i$$$. I claim that $$$w_1,w_2,...w_{n-1}$$$ must be maximized, we can use adjustment to prove it. Under this constraint, we want to maximize $$$\sum_{j=1}^{m-1}a_{n,j}$$$, this is a simple greedy problem.

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

For problem F, how to compute $$$w$$$ that mentioned in the editorial?

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

    Now I know this. But I'm still confuse about how to compute it by divide and conquer. His code is too hard to understand.