confusedman's blog

By confusedman, history, 6 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I guess a Naive approach is : write the medals in string format, like in this case : gggggssssbbb and the calculating the permutation of this string (by first sorting it using sort(s.begin(),s.end()) ), using the next_permutation method and pick each generated string in an unordered_set, so that duplicates will be removed, and in each iteration remove an element,prolly the index 0,

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

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this problem in Codeforces 478C - Украшение столов