netman's blog

By netman, history, 8 years ago, translation, In English
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
C++ code
Java code
  • Vote: I like it
  • +108
  • Vote: I do not like it

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

Auto comment: topic has been translated by netman (original revision, translated revision, compare)

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

The fastest editorial in 2017

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

Another solution of problem D. We use sweep line with events {segment_start, segment_end}. When segment starts we increase arr[pos_l]++, and when segment ends we decrease arr[pos_l]--. To find the answer, we need to check the k-th left-started segment in our array, each time for every event. If we are in pos and have segments_cnt >= k, we know that each of them has end-point >= pos, so our goal is to find k longest segments and answer is pos — po_l[k-th segment]+1. To implement arr[] we can use sparse segment tree. Code
Complexity is O(NlogN + Nlog109)

PS. Is it right complexity in editorial? Should it be O(NlogN + NlogR)?

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

    Solution in editorial has such complexity, because I sort events in every iteration of binary search. I know how to improve complexity, but it's not so important :)

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +40 Vote: I do not like it

    better solution for D, which is too simpler and also much more straight to code. We know the period we want is min(ri)-max(li) between all of k periods we chose. So I sort all of the periods as {li,ri} and just for li I want k-1 periods before it which the min(ri) of them should be maximal possible. I have a set in which I keep k-1 maximum ri of previous periods. And the ans is for any i(1<i<=n) ans = max(ans, min(l[i].secon ,st.begin()->first ) — l[i].firs + 1); Complexity is O(NlogN) 23597706 thank you netman.

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

      Nice :)) the best solution !

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

      Can u elaborate on how are you going to save indexes of coupons after every iteration.

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

        As I coded, I apply the algorithm twice. At the first one, I save the maximum intersection and then at the second one, when the answer is equal to the maximum I output the i(we are at it, now) and the elements in the set.

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

          Wow,That was simple. I was trying to update the ans in one pass and that was giving TLE. Thanks for the answer. Good solution

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

      It is amazing. Thank you

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

    Can you elaborate your approach using seg. tree? I am unabble to get it.

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

Could you explain more about binary_search in D ?

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

thanks for realy good problems

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

wrong solution!

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

    How do you handle the wildcard character in the KMP algorithm?

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

    Can you explain it please, because I don't think you can do this with just a KMP.

    PS: Obviously one can solve the problem in O(n2 * C) where C is the cost of solving the 1D version of the problem. So it's enough if you tell your solution for the 1D problem.

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

      so do you find the answer!? or I explain it?!

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

Loved the first problem, had to think a bit out of the box.

»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I don't wanna be a hater, but at problem A, by "dividing" I understood that the array should be divided in 2 or more arrays. "1.Array sum is not zero. In this case we can divide array into one subarray A[1... n]." That's not called dividing, because you are left with one single array. If I'm wrong, please correct me. Thanks for reading this and I hope I didn't waste your time.

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

    Yes, you are wrong. As the problem statement point the dividing all of array into one array is correct.

»
8 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I had some trouble debugging my implementation of Div2E editorial's solution, so I'll give some hints.

  1. If you build a straightforward Gz, i, j representation of Ti, j using std::bitset, shifting is reversed! This means that shift(Gz, x, y) should be implemented with b>>y instead of b<<y. This makes sense, because the "left" shift defined in the solution brings elements from positions with larger y indexes to positions with smaller y indexes. Using std::bitset, or any native integral types, this is actually a right shift!
  2. The shift is actually a rotate. In other words, b>>y is not enough. Use (b<<(m-y))|(b>>y) instead.
  3. Pattern might be larger than text, so don't forget to take y modulo m.

My implementation: 23653130

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

How would one go about solving D if the question was the union of all of the segments instead of the intersection?

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

    I think a bit about it!!! And I don't think it can be solved better than O(nk). Anyone else have an idea?!

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

      Can you share your method? The best I could think of its an O(kn^2) solution.

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

        Sure! First, we sort segments and remove the segments that are inside another segments. We can simply prove they are useless. Now if li > lj then ri > rj. We arrange the segments with their li. Define dp[i][j] equal to the maximum union of j segments from 1 to ith! We consider two condition for ith segment to fill dp[i][j]: If the previous picked segment have any share range with this, then we choose the leftmost segment that have share range with this as k and simply dp[i][j] = dp[k][j-1]+(ri-li+1)-(rk-li+1). and If not we can update dp[i][j] from maximum of dp[k][j-1](k from 1 to k-1) and then dp[i][j] = mx[k-1][j-1]+(ri-li+1). Am I wrong?!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          Ah, I missed out the dp transit optimization part, that's a neat observation.

          Could persistent data structure help improve the algorithm? The dp transition is always going to be shift one step to the right and add the same variable if a segment is "profitable".

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

            To be honest, I don't know about persistent data structure well! As I was thinking about it, actually, the updating is good enough to be much more optimizer! I will think about it tonight and I'll share the result(if I have any results)!

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

              Now I think more about it I don't think persistent data structure is a feasible data structure, as there is no way to update the next state merely from the latest state. As we have to update from both the just overlapping position and the just not overlapping position it is very hard to maintain the data structure that supports update function at every version.

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

Another greedy solution for D code.

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

My O(nlog(n)) solution using Sort and Heap for problem D (div2). 23736804

Algorithm:
 0 Keep tree vars: max for intersection length, l, r for final left and right bounds, go 1
 1 Sort segments by their left borders, go to 2 
 2 Keep Min Heap of size k to store right bounds. go to 3
 3 Traversing the segments, if the heap's size is less than k just add the segment's right bound to it, then go to 3. Else go to 4 
 4 Compare current segment's right bound with heap's peek, then go to 5
 5 If it is greater than peek, then just remove peek of the heap and add the current segment's right bound to the heap, then go to 6. Else go to 7.
 6 Calculate count of goods by taking difference of heap.peek()-cur.left+1. Update max, l, r and go to 7.
 7 Repeat 3 - 6 until we pass all the segments, then go to 8.
 8 If heap size is equals to k, then go 9, else go 10
 9 Calculate count of goods by taking difference of heap.peek()-cur.left+1.Update max, l, r and go to 10
 10 List k segments that contains segments [l,r]

To sum up sorting takes O(nlog(n)) traversing with heap operations also O(nlog(n)). Total time complexity is also O(nlog(n)).

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

Problem E tags contains "fft". Could someone give me a hint about that approach?