Editorial for DMOPC '19 Contest 7 P2 - Dinner Party
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Consider the problem on a line instead of around a circle, so the -th family member is no longer adjacent to the
-th family member. Now, we serve the family members one-by-one. The
-th member must be served
dishes, and the only way to do so is to serve the
-th and
-st members simultaneously. If in doing so, we serve the
-st member too many dishes, there is no solution, because we cannot satisfy the
-th and
-st members simultaneously: we either have to feed the
-st member too many dishes, or otherwise not serve the
-th member enough. If we can satisfy the
-th family member, we then must satisfy the
-st member by feeding the
-st and
-nd member simultaneously, and the problem continues for each subsequent
-th and
-th member for each
.
Now, we return to the original problem: what if we have the option to serve the -th family member adjacent to the
-th family member
times before proceeding with the problem as if it were in a line? To do this, we can brute force all possible combinations of
in the range
for
complexity, which in the worst case takes
operations.
To achieve a better complexity, observe that the problem is the same given any cyclic shift of . If we can find the minimum element, and then shift
such that the minimum element resides at
, we can achieve
complexity. Although this is deceivingly similar to our previous complexity, we see that
is at most
, so
, meaning that our complexity is equivalent to
!
Alternatively, we can represent the problem as a system of equations with odd and even
cases to solve the problem in
, however printing the output costs an additional
and we see that in both the complexity is equivalent to
anyways.
Pseudocode:
(returns original index before shifting)
function shifted(i)
return (i + idx) mod n
(checks if there is answer for some k)
function possible(k)
tmp is copy of a
tmp[0] -= k
tmp[N - 1] -= k
for i in [0, N - 1)
tmp[i + 1] -= tmp[i]
if tmp[i + 1] < 0
return false
return tmp[N - 1] == 0
(prints answer for some k)
function print_answer(k)
print "YES"
print sum / 2
do k times
print shifted(0), shifted(n - 1)
for i in [0, N - 1)
do a[i] times
a[i + 1]--
print shifted(i), shifted(i + 1)
read N, a
sum = sum of all elements in a
idx is index of minimum element in a
shift a such that a[idx] is first element
for k in [0, min(a_0, a_(n-1))]
if possible(k):
print_answer(k)
terminate
print "NO"
Time complexity:
Comments