naevis's blog

By naevis, history, 6 years ago, In English

https://codeforces.net/problemset/problem/38/E . I solve with dp with 2 dimension where the first one is index and the second is 2 which is pin it or let it drop.. I compute current index result with previous result in this case index — 1 only, but I got wrong answer. Did anyone know why? here is my submission https://codeforces.net/contest/38/submission/50412221

Tags #dp
  • Vote: I like it
  • +6
  • Vote: I do not like it

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

It would be easier to help you if you'd explain you algorithm clearer, in steps. Else you force those willing to help you to read your code to try to understand your algorithm.

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

I wouldn't call your approach DP. It looks more like "greedy with 2 states" — for calculation of state of each marble you use only previous marble's states. And greedy doesn't look right in this problem.

Lets look at your algo: in first state you keep min of two previous states+price to pin current marble. In second you keep min of price of falling on the previous marble or on the one "pined" by second state.

Now lets assume some special input. Lets assume we have:

1). First marble with coordinate=0 and pin_price=0. We pin it and have our states s[0]=0 s[1]=inf.

2). Second marble coord=99 and pin_price=209. So we have states s[0]=209 s[1]=99.

3). Third marble coord=101 and pi_price=10_000 . So we have states s[0]=10_000 s[1]=99+101=200

...Now you can see where the problem is coming from: Third marble's states excluded (or shadowed) state of Second marble been pined, and if now we have more marbles in coordinates=102,103..110 with pin_price=10_000 we can't pin Second marble (in coord=99 for price of 209) and have all other marbles fall on it for total pay amount 209+2+3+...+11. Since starting from third marble pin_price is too high we'll have to land all the marbles on first marble and pay 99+101+102+...+110.

And yes for this input your code gives answer 1154. While it could be 274.