dreamoon_love_AA's blog

Invitation to Weekly Training Farm #14
By dreamoon_love_AA, history, 8 years ago, In English

Sorry for my bad English >__<

There is a small contest called "Weekly Training Farm #14" hosted in one hour latter.

Weekly Training Farm Contest Series are hosted in Codeforces group tw-icpc-blog

These problems are mixed by old problems in many judge and some original problem.

You can see the last contest Weekly Training Farm #13 to understand the style of problems.

The Series contest is hosted in order to spread programming contest in Taiwan. But there are only little participants :(

As problem setters, I hope there will be more people can see these problems. So I post the blog to invite everyone. Thanks~

UPD: If you can read Chinese(Traditional), you can find editorial Here.

UPD 2: The English editorial is here.

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

Comments Comments (12)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems in the previous contests seems quite interesting and some of them i have seen here on codeforces.

Can I know based on what criteria did you choose them?

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

    I'm the problem setter from #11 to #14. Previous rounds are set by other people.

    If I am the setter, most problems are my new ideas. But some of them are modified from problems of other contest. For example, problem D of today is modified from ARC063 pD and problem B of today is the initial version of AGC007 pA(the contest is hosted by me). Other problems of today is my new problems.

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

Nice problem D. How to solve E?

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

    I only describe the outline of solution(don't contain math proving.)

    Assume pi is given in non-decreasing order.

    We have following lemma:

    lemma 1: We call a subarray of p is 'good' iff for any positive integer i, the sum of any (i  +  1) numbers is always greater than the sum of any i numbers in this subarray. And we can check whether a subarray good or not by only checking whether the sum of left (m+1)/2 nubmers is larger than the sum of right (m-1) numbers.

    lemma 2: One of the optimized solution will be keeping all numbers in some subarray of p and changing all other numbers to the ((m + 2) / 2) -th number in this subarray.

    lemma 3: If a subarray of p is good, then any subarray of this good subarray is also good.

    By the three lemma, we can fix all possible of right endpoint of good subarray and using binarysearch to find the leftmost endpoint subarray with the right endpoint. The complexity will be O(n log n).

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

      Wrong answer on test case 1 following the above method.
      Isn't test case1 the sample1? Also, is there something equivalent to coach mode in groups contests?

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

        You shouldn't print a space after the last number in the output. (I also got WA on test 1 once)

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

          Thanks. Accepted. I wonder how you deduced the space thing :D

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

            Since I failed on test #1 it's clearly a formatting error, so the most obvious error is that an extra space is added. (though this should probably be mentioned in the statement)

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

    Can someone explain their solution of D? Thanks!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 21   Vote: I like it +10 Vote: I do not like it

      Code: http://ideone.com/Jstn8Z

      Let mx be the max(a[j]-a[i]). Then, you can notice that if for some j1>j2, there exist i1<j1 and i2<j2 such that a[j1]-a[i1] = mx and a[j2]-a[i2] = mx and a[j1]!=a[j2] then a[j2]>a[j1] and j2<i1. This means we can divide the affecting values as disjoint sub-arrays [m1..M1]..[m2..M2]...[mk..Mk] where Mi-mi = mx (also, Mi>Mj if i<j) and solve each sub-array separately. As an example, the sub-arrays are [30,40] and [10,20] in first sample and whole array in second sample.

      So, the problem reduces to a sub-array consisting of only two values m and M (M-m=mx) as other values will remain same. This can be solved by keeping all indices having m on one side of a graph, indices having M on the other side , edges from m to M if one index occurs before another and finding max-bipartite matching (by adding source and sink, you can see that it is equivalent to min-cut and hence max-flow). Since, the graph is too simple: each subsequent node on one side has super-set of edges of previous node — it can be solved naively, match each M (starting from highest index) to nearest earlier available m.

      The complexity will be O(nlogn) if map is used, which can be optimized to O(n) easily. Notice how simple and short the final code is oblivious to the actual insights needed to arrive at it.

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

Thanks for the nice problems! Hope there will be more of these contests in the future.

P.S. How to solve E? :)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

.

→ Reply