netman's blog

By netman, history, 9 months 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  

»
9 months 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)

»
9 months ago, # |
  Vote: I like it +123 Vote: I do not like it

The fastest editorial in 2017

»
9 months 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)?

  • »
    »
    9 months 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 :)

  • »
    »
    9 months 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.

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

      Nice :)) the best solution !

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is amazing. Thank you

  • »
    »
    9 months 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.

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Could you explain more about binary_search in D ?

»
9 months ago, # |
  Vote: I like it +29 Vote: I do not like it

thanks for realy good problems

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

wrong solution!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months 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.

»
9 months 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.

»
9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read problem description carefully.

»
9 months 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

»
9 months 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?

  • »
    »
    9 months 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?!

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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?!

        • »
          »
          »
          »
          »
          9 months 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".

          • »
            »
            »
            »
            »
            »
            9 months 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)!

            • »
              »
              »
              »
              »
              »
              »
              9 months 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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another greedy solution for D code.

»
9 months 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)).

»
9 months 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?

»
3 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Never mind. Solved it ;)