# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 158 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | Petr | 152 |

7 | Ashishgup | 152 |

9 | 300iq | 150 |

9 | PikMike | 150 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/20/2018 00:00:45 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve I and M?

I：There will be an optimal solution in which all the added numbers are in nonincreasing order. Use this to formulate an

O(n^{2}k) dynamic program and then optimize using divide and conquer trick or convex hull trick.M: I'm unsure about the solution, but apparently it can be proven that you spend all your money on at most two people. Then some sort of ternary search should work.

For M, my team's solution was to map the soldiers to (x, y) points (budget*potency/cost, budget*health/cost) and then the goal becomes to maximize x * y. So then you build the convex hull of those points.

That way, it's only ever optimal to combine soldiers that are adjacent along the convex hull. The reasoning behind that is if you tried to merge more than 2 soldiers, you'd effectively be drawing a line between two segments on the convex hull (and of course that segment lies strictly inside the hull) and the product of any (x, y) on that segment will never be greater than some (x, y) product along the outer segments of the hull.

So it's not really a proof but there's some intuition behind why you only combine 2 soldiers (also other solutions don't seem to use convex hull at all).

I'm having trouble convincing myself of this. Do you have any proof or good intuition on why it's true?

M: Transform (c, h, p) to (h * C / c, p * C / c). The answer is a combination x1 * v1 (vi is (hi, pi)) + x2 * v2 + ..., you take that vector and take x*y. But that combination has other constraint, x1 + x2 + ... + xn == 1 and xi is in [0, 1] so it's a convex combination (https://en.wikipedia.org/wiki/Convex_combination). This means that you can take the convex hull and solve the problem for the vertices and edges and it will have the greatest answer.

Is it possible to solve M with c++? It seems like there is a precision problem. My python code using (exactly) the same logic got AC.

We have reference solutions in C++ (and we also have some other AC in C++ from other contestants independently). I'm not sure why yours is failing.

Thanks. BTW, do you by any chance know why my solution to E got Idleness limit exceeded on test 11? Thanks for your help.

http://codeforces.com/gym/101982/submission/45508248 here is the code.

nvm solved. my n and m are the other way round...

how to solve d?

dp[number of digits filled in][this number is k modulo m] or dp[n][k] can transition to dp[n+1][2*k] and dp[n+1][2*k+1]. dp[n][k] = (number of ways to get to this state from [0][0], sum of 1's of these ways). answer is dp[bits][0].second

ty

How to solve K?