Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a problem statement in one of the online Judges for programming. I am looking for an algorithm that gives optimized solution, not the best solution.

I'm given a set of triplet of balls, each containing one each of colors red,blue and green. Each ball has a charge represented by an integer (it's different for individual balls). Now the energy of the triplet is calculated by multiplying the charges in the triplet.

I can exchange balls between two triplets (Of course of the same colours, a triplet is not supposed to have balls of same colour), but on exchanging the balls, the energy of the exchanged balls is increased by one.

There's one more addition to the statement, swapping balls between triplets also accumulates a constant energy E on the system for every swap (it's not counted in the energy due to charges of balls).

The purpose of the optimisation is to reduce the energy of the whole system by swapping balls between triplets and bring it to a minimum, ie the sum of the product of charges in all triplets has to be minimum. The program must log all the swaps and the output state.

share|cite|improve this question
Are the charges signed or unsigned (is each triplet in $\mathbb{N}^3$ or $\mathbb{Z}^3$)? And how does this accumulation of total system energy $E$ work, exactly? Do we simply have that this energy is $E=\sum_iR_iG_iB_i$, the sum of the energies of each triplet $(R_i,G_i,B_i)$, and that swapping the red balls in triplets $i,j$ results in the new triplets $(R_j+1,G_i,B_i)$ and $(R_i+1,G_j,B_j)$, or is there some other rule for how total energy accumulates? Finally, by "optimized not best", do you mean you are looking for any algorithm to find a local minimum? – bgins Jun 8 '12 at 12:22
Charges are unsigned . And yes E=∑iRiGiBi is what you've to minimize . On swapping apart from the balls getting extra charges , there's some energy getting accumulated on the system , so after n swaps , the energy of system would be E=∑iRiGiBi + nK,where i is used to represent the current system state and K is a constant – Malice Jun 8 '12 at 12:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.