Water Sort Puzzle (Challenge) WTRSORT Solution

by

Water Sort Puzzle (Challenge) WTRSORT April Long Challenge 2021

Chef wants to study reactions between non-miscible reagent samples with different colours. There are N colours (numbered 1 through N). Chef has N+2 test tubes (numbered 1 through N+2), each of them can hold a volume M ml; initially, tubes N+1 and N+2 are empty, while for each i (1≤i≤N), the i-th tube is completely filled and contains M ml of reagents with some colours. Since reagents with different colours do not mix, we can describe the contents of the i-th tube from its bottom to its top by a sequence Bi,1,Bi,2,…,Bi,M, i.e. for each valid j, the j-th mililiter of volume of the i-th tube, measured from the bottom, is filled by a reagent with a colour Bi,j. The total initial volume of each reagent is equal to M ml.

To facilitate his study, Chef wants to redistribute the reagents into tubes according to their colours, i.e. at the end, for each colour i, there must be exactly one tube which contains all M ml of this reagent and no reagents with other colours. The specific positions of reagents or empty tubes in this final state do not matter.

In order to achieve this, you may first reverse the order of reagents in some (possibly none or all) tubes. Then, you may perform operations of two types:

Choose two test tubes P and Q and transfer the topmost 1 ml of reagent from the tube P to the top of the tube Q.
This is only allowed if P is non-empty and Q is not full.
If Q is empty, the cost of this operation is 0.
Otherwise, let’s denote the colour of the topmost reagent in tube P by U and the colour of the topmost reagent in Q (before this operation) by V. If DU,V=−1, this operation is not allowed. Otherwise, it is allowed and its cost is DU,V.
Choose a test tube P and increase its capacity by 1 ml. The cost of this operation is CP.
You are given the costs of pouring reagents on top of each other and information about which reagents react with each other and therefore cannot be poured on top of each other, i.e. the matrix D. It is guaranteed that Di,j=Dj,i for each valid i and j and Di,i=0 for each valid i.

You must separate the reagents (reach the state described above) using no more than 220=1,048,576 operations. The sum of costs of the operations you use to achieve this should be as small as possible.

Input
The first line of the input contains two space-separated integers N and M.
The second line contains N+2 space-separated integers C1,C2,…,CN+2.
N lines follow. For each valid i, the i-th of these lines contains N space-separated integers Di,1,Di,2,…,Di,N.
N more lines follow. For each valid i, the i-th of these lines contains M space-separated integers Bi,1,Bi,2,…,Bi,M.
Output
First, print a single line containing two space-separated integers X and Y (0≤X≤N, 0≤Y≤220) ― the number of test tubes whose contents you wish to initially reverse and the number of operations you wish to perform.
Then, print a single line containing X space-separated integers A1,A2,…,AX ― the numbers of the test tubes you wish to initially reverse (1≤Ai≤N for each valid i).
Then, print Y lines describing the operations in the order in which you wish to perform them.
To perform an operation of the first type, print a line containing three space-separated integers 1, P and Q (1≤P,Q≤N+2, P≠Q).
To perform an operation of the second type, print a line containing two space-separated integers 2 and P (1≤P≤N+2).
Constraints
N=512
M=16
1≤Ci≤1,000 for each valid i
−1≤Di,j≤100 for each valid i,j
Di,j=Dj,i for each valid i,j
Di,i=0 for each valid i
1≤Bi,j≤N for each valid i,j
Example Input
4 4
3 5 2 3 1 4
0 -1 2 -1
-1 0 1 7
2 1 0 -1
-1 7 -1 0
1 2 1 3
3 3 2 2
4 1 3 4
1 2 4 4
Example Output
2 19
1 3
1 4 5
1 4 5
1 3 5
1 2 4
1 2 4
1 1 2
2 4
1 1 4
1 2 6
1 3 6
1 1 6
1 1 2
1 3 2
1 4 1
1 4 1
1 4 1
1 4 1
1 4 6
1 3 5
Explanation
The initial arrangement of reagents in test tubes is
Image 0
After reversing the contents of the 1-st and 3-rd test tube, the arrangement becomes
Image 1
After the first 6 operations, the arrangement becomes
Image 2
After the first 8 operations:
Image 3
After the first 13 operations:
Image 4
After all 19 operations, the reagents get separated:
Image 5

The cost paid for the 6-th operation is 2 and the cost paid for the 7-th operation is 3. The cost paid for all other operations is 0. Thus, the reagents are separated with a total cost 5. Note that this is not necessarily an optimal way to separate the reagents.

In the actual test data, N is 512 and M is 16. Smaller values have been used in this example for clarity.

Test Generation
The generator used to generate the test cases can be found here.

N=512
M=16
Initially, for each i (1≤i≤N), the i-th test tube is completely filled with M ml of the reagent with colour i.
A parameter G∈{4096,16384,65536,1048576} is chosen and the following operation is performed G times: two different test tubes E and F such that E is not empty are chosen randomly and 1 ml of reagent is transferred from top of E to F. We consider the capacities of the tubes to be infinite here.
Then, for each test tube that contains more than M ml of reagents, the volume of reagents in it is decreased to M by transferring excess reagents (in whole mililiters) from the top into tubes that contain less than M ml of reagents randomly.
Then, the test tubes N+1 and N+2 are made empty by transferring their contents randomly to other test tubes that contain less than M ml of reagents.
The values of C1,C2,…,CN+2 are chosen uniformly randomly and independently between 1 and 1000 inclusive.
Then, another parameter K∈{1,4,16,64} is chosen.
Finally, N(N−1)2K distinct unordered pairs of distinct colours are chosen randomly. For each of these pairs (U,V) (1≤U<V≤N), DU,V=DV,U is chosen uniformly randomly and independently between 1 and 100 inclusive. For all other such pairs, DU,V=DV,U=−1.
There are 16 test files corresponding to all possible combinations of parameters G and K.

Scoring
The checker used to determine the score of your submission can be found here.

If you perform an invalid operation or the reagents are not separated after all the operations (particularly, if there is a test tube which contains reagents with more than one colour or there is a colour which appears in more than one test tube), then you will receive the Wrong Answer verdict.

Otherwise, the score for a test file is the total cost of all the operations. The score of a submission is the sum of scores of all test files. Your goal is to minimise this score.

There are 16 test files. During the contest, the displayed score will account for exactly 8 test files, i.e. your score reflects your submission’s performance on 50% (8/16) of the test files. However, if your program gets a non-AC verdict on any test file, your submission’s verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program’s scores over the other 8 test files.

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment