Alex7's blog

Try my problem...
By Alex7, 10 years ago, In English

I made this problem please try to solve it..

Your comments/solutions will be helpful :D :D

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

Comments Comments (31)
| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How many testcases are there?

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

    10

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

      how many times can a city be robbed? once or infinite times?

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

        Sorry,my stupid question.seems to be dynamic programming dp[i][k]=max(dp[s][k-1]+sum_cost[i]-sum_cost[s1]+w*(sum_x[i]-sum_x[s1]) . we can use g[s1][k-1] record max(dp[s][k-1],s<=s1-1) use f[s1][k-1] record max(g[s1][k-1]-sum_cost[s1]-w*sum_x[s1])
        when doing transfer,then transfer is O(1).time complexity is O(n*k)

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

          Could you explain what each of your dp states mean? I'm guessing dp[i][k] is the maximum amount of money we can earn if we teleport to position i and have used k total teleports so far, but am unsure if there are any additional constraints. I'm also not understanding the transition statement.

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

            Yes,we can find we first teleport to a left most position and then walk right,then teleport to a right postion,walk right....

            it is a lot of non intersection segments then dynamic programming works.

            sum_cost[i] infact is sum_profit[i] and sum_x[i] is the position of x,then seems I forgot to minus T[i]..

            for transition: there are two transition point s,s1,s is the right end point of previous segment,and s1 is the left end point of current segment.

            when transition, we can record g[s1][k-1]=max(g[s1-1][k-1],dp[s1][k-1]). then dp function become dp[i][k]=g[s1][k-1]+sum_profit[i]-sum_profit[s1]+w*(sum_x[i]-sum_x[s1])-T[i].

            then we can record f[i][k-1]=max(f[i-1][k-1],g[i][k-1]-sum_profit[i]-w*sum_x[i]).

            then dp[i][k]=f[i-1][k-1]+sum_profit[i]+w*sum_x[i]-T[i].

            seems to be correct..

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

              If I am understanding your transition correctly, you seem to be teleporting into the right endpoint of the current segment, and then walking left until you reach the left endpoint. However, isn't it possible that you will walk right after teleporting? Also, shouldn't it be -w*(sum_x[i]-sum_x[s1])?

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

update: AC now: 12964529 2014-11-24 10:38:10 yangshenThe Hack accepted edit run 0.79 66M C++

btw: you say"teleport that can be used exactly K times before it self-destructs"

I have thought we must use exactly K times teleport,but in fact we can use less than K times. good problem,thank you...

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

    Your solution is the same as my original solution, however I'm curios: is there any other solutions???

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

      er,seems there is more efficient greedy approach: first for each point ,we can record v[i]=sum_profit[i]-w*x[i]. and for each i,determine index of min(v[j]) j<=i,and same as j>=i then O(n) complexity we can get some candidate optimal segments.for each segments,determine the optimal middle point m,then try to merge the segment one by one,if after merge we can get more optimal value,then merge it until we can't get more optimal value.

      seems it is O(N+K)...

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

        Can you prove it's correctness ??

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

          I couldn't understand him, but if this problem can be solved greedily then it would be the hardest greedy problem I've ever seen

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

            See here: http://cerc.tcs.uj.edu.pl/2013/data/g.pdf :P.

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

              I have read the problem you metion sevral times, but couldn't understand the task,but It seems it is a different problem we discuss..

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

                That was just an example of a hard greedy problem I think.

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

                Frankly saying I didn't even read the problem which this subject is about, but maybe it was not that clear, what I meant. Problem I posted was a response to "hardest greedy problem I've ever seen" — I think I provided a harder one, whatever that one discussed here is :P.

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

                  Don't take my words literally I just meant to say that I don't think Alex7's problem can be solved greedily.

                  anyway can you explain the greedy solution of your problem?

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

                  No, I can't ; p. Mainly because I simply don't have a slightest idea how to do this : p (though I know it's greedy).

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

                  er,I think the most hardest part of the problem you mention is reading comprehension,I have read this problem the wholeafternoon,but couldn't even guesswhat the task means....

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

                  Thats my understanding of problem:
                  You are given N intervals [a_i, b_i]. Two intervals are called 'related' if they share a common point.
                  You need to find minimal K and to reorder those intervals with two conditions to hold:
                  1. If two intervals [a, b] and [c, d] are unrelated, then [a, b] comes earlier than [c, d] iff b < c;
                  2. If two intervals are related, then they must appear in reordered list no more than K positions apart from each other.

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

                  can you explain what is apart from means? for example [2,3] comes before [1,6],how to compute k?

                  is it the intersection part of two adjacent intervals?

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

                  Consider such an input for problem:
                  N = 6
                  intervals = {A, B, X1, C, D, X2}, where X1 and X2 are related, and A, B, C, D are arbitrary intervals.
                  Suppose we've reordered them in such manner:
                  1. X1
                  2. B
                  3. A
                  4. C
                  5. X2
                  6. D
                  Then we say that X1 and X2 are 4 positions apart from each other (X1 is at position 1, X2 is at position 5, |1 — 5| = 4).

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

                  This seems to be only your problem. This task was posed on CERC and nobody got any problems with statement... It is written using fully correct English and at least for me whole statement is crystal clear.

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

I'm approaching the problem by first computing the best cost for each segment. So I have a DP array C[a][b] that gives the profit if we teleport into the segment and visit all banks [a...b] (inclusive). However, I can't find a way to use this with the final DP.

Right now I have DP[x][k] as the max profit if we use banks [0...x] and k segments. Transition is DP[x][k] = max(DP[x-1][k], C[0][x], DP[0][k-1]+C[1][x], DP[1][k-1]+C[2][x], ... DP[x-1][k-1]+C[x][x]) I don't see how we can speed this solution up. Is there a better way to approach this problem? Did I make some false assumptions?

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

    I did a similar approach but I did some pruning by only considering useful segments. I got accepted with a pathetic runtime of 8.53 seconds... I'm still scratching my head wondering how the other solutions ran under 1 second...

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

      other solutions ran under 1 second because its complexity is O(N*K) worst case

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

        Yeah, I know, but I've been thinking for hours and can't find a way to reduce it to O(N*K).

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

I got accepted with a O(N2 * K) solution with some pruning. The pruning is only considering useful segments. A segment [i, j] is useful if there is no other segments [i, k] with k < j whose profit is bigger or equal than that of segment [i, j].

Runtime was horrible (8.53).

How do you make it more efficient than O(N2 * K)?

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

    Time limit reduced to 1 second.. Solutions rejudged

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

      Great... now I have to find a better solution...

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

This is the tutorial (written by me as well)..

Please give me your opinions as well, is it well-written?

Or terrible and incomprehensible??

→ Reply