Page Contents

## 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*

*April Long Challenge 2021 Solutions*

- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*February Long Challenge 2021*

*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

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

### November Challenge 2020 SOLUTION CodeChef

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

### October Lunchtime 2020 CodeChef SOLUTIONS

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP

*RELATED :*

- Top Best Keylogger in Python 3 Make One
*What is Hacking?**Secrets of the Deep Dark Web**CODECHEF September Lunchtime 2020 SOLUTIONS**August Lunchtime 2020 SOLUTIONS*

*Related :*

*A. Shandom Ruffle SOLUTION**B. Pear TreaP SOLUTION**C. Sneetches and Speeches 3 SOLUTION**D. The Grim Treaper SOLUTION**Y. Sneetches and Speeches 1 SOLUTION**Z. Trick or Treap SOLUTION**A. Floor Number SOLUTION CODE FORCES**B. Symmetric Matrix SOLUTION CODE FORCES**C. Increase and Copy SOLUTION CODE FORCES**D. Non-zero Segments SOLUTION CODE FORCES**E. Rock, Paper, Scissors SOLUTION CODE FORCES**F. Number of Subsequences SOLUTION CODE FORCES*

*Related :*

*Chef and Easy Queries SOLUTIONS CHEFEZQ**Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE**Positive AND SOLUTIONS POSAND**Replace for X SOLUTIONS REPLESX**Village Road Network SOLUTIONS VILLNET**Random Knapsack SOLUTIONS RANDKNAP**D-Dimensional MST SOLUTIONS DDIMMST**Compress all Subsegments SOLUTIONS SEGCOMPR**Adding Squares SOLUTIONS ADDSQURE**Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE**Rooted Minimum Spanning Tree SOLUTIONS ROOTMST*