Try my problem... - Codeforces

11 лет назад, скрыть # ^ |

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 4 →

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)

→ Ответить

11 лет назад, скрыть # ^ |

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.

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 2 →

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..

→ Ответить

11 лет назад, скрыть # ^ |

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])?

→ Ответить

11 лет назад, скрыть # |

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...

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

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)...

→ Ответить

11 лет назад, скрыть # ^ |

Can you prove it's correctness ??

→ Ответить

kingofnumbers

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

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..

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

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.

→ Ответить

kingofnumbers

11 лет назад, скрыть # ^ |

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?

→ Ответить

11 лет назад, скрыть # ^ |

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).

→ Ответить

11 лет назад, скрыть # ^ |

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....

→ Ответить

ItsLastDay

11 лет назад, скрыть # ^ |

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.

→ Ответить

11 лет назад, скрыть # ^ |

← Rev. 2 →

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?

→ Ответить

ItsLastDay

11 лет назад, скрыть # ^ |

← Rev. 2 →

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).

→ Ответить

11 лет назад, скрыть # ^ |

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.

→ Ответить

11 лет назад, скрыть # |

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?

→ Ответить

11 лет назад, скрыть # ^ |

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...

→ Ответить

kingofnumbers

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить

11 лет назад, скрыть # |

I got accepted with a O(N² * 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(N² * K)?

→ Ответить

11 лет назад, скрыть # ^ |

Time limit reduced to 1 second.. Solutions rejudged

→ Ответить

11 лет назад, скрыть # ^ |

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

→ Ответить