Carnival Tickets SOLUTIONS IOI 2020

Page Contents

Carnival Tickets SOLUTION

2020 International Olympiad in Informatics Day 1 (Mirror)

Ringo is at a jubilee in Singapore. He has some prize tickets in his pack, which he might want to use at the prize game slow down. Each ticket comes in one of ~n~ hues and has a non-negative whole number imprinted on it. The whole numbers imprinted on various tickets may be the equivalent. Because of a characteristic in the festival rules, ~n~ is destined to be even.
Ringo has ~m~ tickets of each shading in his pack, that is a sum of ~n cdot m~ tickets. The ticket ~j~ of the shading ~i~ has the number ~x[i][j]~ imprinted on it ~(0 le I le n – 1~ and ~0 le j le m – 1)~.
The prize game is played in ~k~ adjusts, numbered from ~0~ to ~k – 1~. Each round is played in the accompanying request:
From his pack, Ringo chooses a lot of ~n~ tickets, one ticket from each shading. He at that point gives the set to the game ace.
The game ace notes down the whole numbers ~a[0], a[1] dots a[n – 1]~ imprinted on the tickets of the set. The request for these ~n~ whole numbers isn’t significant.
The game ace pulls out an exceptional card from a fortunate draw box and notes down the whole number ~b~ imprinted on that card.
The game ace computes the supreme contrasts among ~a[i]~ and ~b~ for each ~i~ from ~0~ to ~n – 1~. Let ~S~ be the whole of these outright contrasts.
For this round, the game ace gives Ringo a prize with a worth equivalent to ~S~.
The tickets in the set are disposed of and can’t be utilized in future rounds.
The rest of the tickets in Ringo’s sack after ~k~ rounds of the game are disposed of.
By observing intently, Ringo understood that the prize game is fixed! There is really a printer inside the fortunate draw box. In each round, the game ace finds a number ~b~ that limits the estimation of the prize of that round. The worth picked by the game ace is imprinted on the unique card for that round.
Having this data, Ringo might want to allot passes to the rounds of the game. That is, he needs to choose the ticket set to use in each round so as to amplify the all out estimation of the prizes.
Usage subtleties
You should execute the accompanying method:
Duplicate
int64 find_maximum(int k, int[][] x)
~k~: the quantity of rounds.
~x~ : a ~n times m~ cluster depicting the whole numbers on each ticket. Tickets of each shading are arranged in non-diminishing request of their whole numbers.
This system is called precisely once.
This methodology should settle on precisely one decision to allocate_tickets (see beneath), portraying ~k~ ticket sets, one for each round. The designation ought to amplify the all out estimation of the prizes.
This technique should restore the greatest absolute estimation of the prizes.
The methodology allocate_tickets is characterized as follows:
Duplicate
void allocate_tickets(int[][] s)
~s~ : a ~n times m~ exhibit. The estimation of ~s[i][j]~ ought to be ~r~ if the ticket ~j~ of the shading ~i~ is utilized in the arrangement of round ~r~ of the game, or ~-1~ in the event that it isn’t utilized in any way.
For each ~0 le I le n – 1~, among ~s[i][0], s[i][1], dots, s[i][m – 1]~ each worth ~0, 1, 2, dots, k – 1~ must happen precisely once, and all different sections must be ~-1~.
On the off chance that there are various designations bringing about the most extreme complete prize worth, it is permitted to report any of them.
Models
Model 1
Duplicate
find_maximum(2, [[0, 2, 5],[1, 1, 3]])
This implies:
there are ~k = 2~ adjusts;
the whole numbers imprinted on the tickets of shading ~0~ will be ~0~, ~2~ and ~5~, separately;
the whole numbers imprinted on the tickets of shading ~1~ will be ~1~, ~1~ and ~3~, separately.
A potential designation that gives the greatest all out prize worth is:
In round ~0~, Ringo picks ticket ~0~ of shading ~0~ (with the whole number ~0~) and ticket ~2~ of shading ~1~ (with the number ~3~). The most reduced conceivable estimation of the prize in this round is ~3~. E.g., the game ace may pick ~b = 1~: ~|1 – 0| + |1 – 3| = 1 + 2 = 3~.
In round ~1~, Ringo picks ticket ~2~ of shading ~0~ (with the number ~5~) and ticket ~1~ of shading ~1~ (with the number ~1~). The least conceivable estimation of the prize in this round is ~4~. E.g., the game ace may pick ~b = 3~: ~|3 – 1| + |3 – 5| = 2 + 2 = 4~.
Hence, the all out estimation of the prizes would be ~3 + 4 = 7~.
To report this distribution, the system find_maximum should settle on the accompanying decision to allocate_tickets:
Duplicate
allocate_tickets([[0, – 1, 1], [-1, 1, 0]])
At last, the system find_maximum should return ~7~.
Model 2
Duplicate
find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])
This implies:
there is just one round,
the numbers imprinted on the tickets of shading ~0~ are ~5~ and ~9~, individually;
the numbers imprinted on the tickets of shading ~1~ will be ~1~ and ~4~, individually;
the numbers imprinted on the tickets of shading ~2~ are ~3~ and ~6~, individually;
the numbers imprinted on the tickets of shading ~3~ are ~2~ and ~7~, individually.
A potential distribution that gives the most extreme complete prize worth is:
In round ~0~, Ringo picks ticket ~1~ of shading ~0~ (with the number ~9~), ticket ~0~ of shading ~1~ (with the whole number ~1~), ticket ~0~ of shading ~2~ (with the whole number ~3~), and ticket ~1~ of shading ~3~ (with the whole number ~7~). The most minimal conceivable estimation of the prize in this round is ~12~, when the game ace picks ~b = 3~: ~|3 – 9| + |3 – 1| + |3 – 3| + |3 – 7| = 6 + 2 + 0 + 4 = 12~.
To report this allotment, the methodology find_maximum should settle on the accompanying decision to allocate_tickets:
Duplicate
allocate_tickets([[-1, 0], [0, – 1], [0, – 1], [-1, 0]])
At long last, the strategy find_maximum should return ~12~.
Limitations
~2 le n le 1500~ and ~n~ is even.
~1 le k le m le 1500~
~0 le x[i][j] le 10^9~ ~(~for all ~0 le I le n – 1~ and ~0 le j le m – 1)~
~x[i][j – 1] le x[i][j]~ ~(~for all ~0 le I le n – 1~ and ~1 le j le m – 1)~
(~11~ focuses) ~m = 1~
(~16~ focuses) ~k = 1~
(~14~ focuses) ~0 le x[i][j] le 1~ ~(~for all ~0 le I le n – 1~ and ~1 le j le m – 1)~
(~14~ focuses) ~k = m~
(~12~ focuses) ~n, m le 80~
(~23~ focuses) ~n, m le 300~
(~10~ focuses) No extra limitations.