vjudge28's blog

By vjudge28, history, 7 weeks ago, In English

Given a list of values arr, you are allowed to reduce two distinct elements by one, or reduce any element by 3 unless or until after operation element should be non negative. You can perform any operation any number of times. Determine the minimum value of (a1+1)*(a2+1)*(a3+1).....(an+1) (1-indexed) after applying operations optimally.

N = 10; 1<=ai<=20;

Can anyone figure out a decent approach on how to solve this?

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Consider all possible states of the array. If state a1, a2, ... a10 is a permutation of b1, b2, ... b10, then they have the same answer. So at each step, we can sort the arrays.

If we do this, there are 30 choose 10 possible states, which is about 3*10^7 total states. You can probably run this DP offline. I suspect you can get that to finish in about 30 seconds without submitting.

Then, you can make some greedy guesses, for instance: anytime you have a number bigger than 12, subtract 6 from it to get to a simpler state. This will cut WAY down on the number of states your DP needs to handle (now only 22 choose 10, which is easily small enough to submit), but there is a chance that that observation is wrong, since I didn't prove it. You can either spam submits if you are at the end of contest to check, or you can run against your 30 second brute forcer and see if the answer to any of the original 10^7 states changes. You will probably be able to find something like that (or maybe, something like if any two numbers are both greater than 10, subtract 1 from both of them, if subtracting 6 from anything over 12 doesn't work)

Also, the answer is always going to be 1, or 2, since you will always end up with either 1 number that is a 1, or everything is a 0, otherwise you can somehow simplify it. So if you try random moves, you can probably make your DP run pretty quickly and do some pruning that way too.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Please provide the problem source.