Try my problem... - Codeforces

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

9 years ago, # |

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

Alex7

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

Alex7

9 years ago, # ^ |

Can you prove it's correctness ??

→ Reply

kingofnumbers

9 years ago, # ^ |

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

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

kingofnumbers

9 years ago, # ^ |

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

9 years ago, # ^ |

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

9 years ago, # ^ |

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

ItsLastDay

9 years ago, # ^ |

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

9 years ago, # ^ |

← 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?

→ Reply

ItsLastDay

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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