ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2025. Line Fighting

Can you help me!? Why this approach is correct?
Posted by Alibi 13 Nov 2015 13:36
You have to divide the participants into equal teams (rounded)
For example, for "15 10" test - (1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
Good luck :)
Re: Can you help me!? Why this approach is correct?
Posted by dustbite 7 Nov 2016 22:50
Well I don't understand this topic CLEARLY but I can trace some steps towards the final solution.

Let's fix a possible team distribution i.e. number of teams
Then, we need to find the best possible distribution to maximize the product
For eg for 4 teams a1,a2,a3,a4 will be the team distribution
a1+a2+a3+a4=n
now we need to maximize the function f(a1,a2,a3,a4)=a1a2+a1a3+a1a4+a2a3+a2a4+a3a4
under the constraint a1+a2+a3+a4=n, which can be done using lagrangian multiplier.
g(a1,a2,a3,a4)=f(a1,a2,a3,a4)+p(n-a1-a2-a3-a4)
lets take derivative of the function g at a1
g'(a1) = a2+a3+a4 -p
g'(a2) = a1+a3+a4 -p
g'(a3) = a1+a2+a4 - p
g'(a4) = a1+a2+a3 - p
Equate all of them to zero
a1+a2+a3=a2+a3+a4=a1+a3+a4=a1+a2+a4=p
from 1st and second we find a1=a4
from 2nd and 3rd a2=a1
similarly we find a1=a2=a3=a4, all a's must be equal
so a1+a2+a3+a4=n
a1=n/4
In general
a1=n/p, where p is the number of teams.
When p is not divisible, we need to make all of them as equal as possible by distributing n % p.

I don't understand lagrangian multiplier by heart(I have not tried to). But the tool works here.

We can try bruteforcing all possible team numbers from 2 to k and find which is best.

Edited by author 07.11.2016 22:51