GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 31 July 2022

[Solution] Magical Array Codeforces Solution


D. Magical Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric has an array b of length m, then he generates n additional arrays c1,c2,,cn, each of length m, from the array b, by the following way:

Initially, ci=b for every 1in. Eric secretly chooses an integer k (1kn) and chooses ck to be the special array.

There are two operations that Eric can perform on an array ct:

  • Operation 1: Choose two integers i and j (2i<jm1), subtract 1 from both ct[i] and ct[j], and add 1 to both ct[i1] and ct[j+1]That operation can only be used on a non-special array, that is when tk.;
  • Operation 2: Choose two integers i and j (2i<jm2), subtract 1 from both ct[i] and ct[j], and add 1 to both ct[i1] and ct[j+2]That operation can only be used on a special array, that is when t=k.

    Note that Eric can't perform an operation if any element of the array will become less than 0 after that operation.


  • of 
Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Now, Eric does the following:

  • For every non-special array ci (ik), Eric uses only operation 1 on it at least once.
  • For the special array ck, Eric uses only operation 2 on it at least once.

Lastly, Eric discards the array b.

For given arrays c1,c2,,cn, your task is to find out the special array, i.e. the value k. Also, you need to find the number of times of operation 2 was used on it.

Input

The first line contains a single integer t (1t104) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers n and m (3n1057m3105) — the number of arrays given to you, and the length of each array.

The next n lines contains m integers each, ci,1,ci,2,,ci,m.

It is guaranteed that each element of the discarded array b is in the range [0,106], and therefore 0ci,j31011 for all possible pairs of (i,j).

It is guaranteed that the sum of nm over all test cases does not exceed 106.

It is guaranteed that the input is generated according to the procedure above.

Output

For each test case, output one line containing two integers — the index of the special array, and the number of times that Operation 2 was performed on it. It can be shown that under the constraints given in the problem, this value is unique and won't exceed 1018, so you can represent it as a 64-bit integer. It can also be shown that the index of the special array is uniquely determined.

In this problem, hacks are disabled.

No comments:

Post a Comment