Блог пользователя confusedman

Автор confusedman, история, 4 года назад, По-английски

Found this HackerRank problem recently, very similar to the Div2 A problem in Educational Round 89 but a more general form.

It seems that these kinds of problems can be solved with something similar linear programming? at least for the Div2 A problem all we had to do was identify the constraints and output the minimum of them. Does anyone know exactly what topic these problems come under and how to find more like them?

Here's the statement for those who don't want to click the link:

HackerRank Problem Statement

Would appreciate if anyone can give ideas on how to solve specifically this problem and problems similar to it.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't think the problem can be formulated as an LP, but I might be wrong.

Does anyone know exactly what topic these problems come under and how to find more like them?

That Div2A can be formulated as an LP, and I solved it by drawing the shape of the feasible region and figuring out the optimum by cases, which (to me at least) I found more "systematic" than the editorial solution. I wish there were more problems that involve concepts from LP but don't require you to code up a generic LP solver (e.g. simplex) to solve them.

I've seen simplex solvers in some ICPC notebooks (Stanford, KTH) but I'm not familiar with the problems that require them.

I also remember this nice problem that is equivalent to counting the number of integer points in an LP feasible region defined by a small number of constraints :) https://codeforces.com/contest/1355/problem/C

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

It's the minimum of the sum divided by 3 and the sum of the two smaller elements.

The first constraint is obviously true, we take 3 elements every turn.

The second constraint is to avoid taking only one type of medal in a turn. It's only tempting to do this if we have a lot of a certain medal. If such a medal exists, it's optimal on every turn to take 2 of that medal, and 1 of any other medal. This is to make maximal usage of it. So we're constrained by how many of the other medals we have.

code
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is this problem in Codeforces 478C - Table Decorations