Questions Tagged With 2-dhttps://discuss.codechef.com/tags/2-d/?type=rssquestions tagged <span class="tag">2-d</span>enSun, 23 Sep 2018 18:14:16 +05302-D array's kth largest elementhttps://discuss.codechef.com/questions/116254/2-d-arrays-kth-largest-element<p>Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.</p>
<p>Solution ::: All I could get is this </p>
<p>First of all, you only need to consider the left-top k*k matrix to find the k-th largest element. It's guaranteed to be in that smaller matrix. This helps especially when k << n. </p>
<p>Then extract the first element of each row and put it in the max-heap with size K. Building the heap takes time k*log(k). </p>
<p>Then remove the max element from the heap and put the next element in the same row into the heap. This step takes k*log(k) time. </p>
<p>So in total, 2k<em>log(k) = k</em>log(k) time.
It only requires O(k) space. </p>
<p>There may be better selection algorithm with better best-case performance. If you know of a better algorithm than mine, let me know!</p>
<p>I am also having some problem in it's implementation . Please someone help !!</p>
<p>How to solve this ?? Thanks in advance :)</p>harrypotter0Mon, 06 Nov 2017 17:14:16 +0530https://discuss.codechef.com/questions/116254/2-d-arrays-kth-largest-elementsorting2-dPlease help me in SPOONShttps://discuss.codechef.com/questions/122685/please-help-me-in-spoons<p><a href="https://ideone.com/gEwkxk">https://ideone.com/gEwkxk</a></p>
<p><a href="https://www.codechef.com/problems/SPOON">https://www.codechef.com/problems/SPOON</a> <--question</p>
<p>I have used straight forward approach- check rows then column. any idea? </p>llgokull_007Sun, 11 Feb 2018 18:03:39 +0530https://discuss.codechef.com/questions/122685/please-help-me-in-spoons2-darrayhelpwaCHEFZERO - Editorialhttps://discuss.codechef.com/questions/135859/chefzero-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/SEPT18A/problems/CHEFZERO">Div1</a><br>
<a href="https://www.codechef.com/SEPT18B/problems/CHEFZERO">Div2</a><br>
<a href="https://www.codechef.com/problems/CHEFZERO">Practice</a> </p>
<p><strong>Setter-</strong> <a href="https://www.codechef.com/users/mgch">Misha Chornyi</a> <br>
<strong>Tester-</strong> <a href="https://www.codechef.com/users/teja349">Teja Vardhan Reddy</a><br>
<strong>Editorialist-</strong> <a href="https://www.codechef.com/users/vijju123">Abhishek Pandey</a></p>
<h1>DIFFICULTY:</h1>
<p>CHALLENGE</p>
<h1>PRE-REQUISITES:</h1>
<p>General Programming. Knowledge of Probability and Expectations</p>
<h1>PROBLEM:</h1>
<p>Given a $N*M$ matrix, divide it into $K$ connected components such that $|Max-Min|$ is minimized, where $Max$ is the maximum valued component and $Min$ is minimum valued component.</p>
<h1>QUICK-EXPLANATION:</h1>
<p><strong>Key to AC-</strong> Notice that numbers are uniformly, randomly generated. Trying out various orderings and simulations was expected to give good score.</p>
<p>Note that the values are uniformly, randomly generated. Hence, if we divide the array into $\frac{N*M}{K}$ partitions, then it;d be a good start. Lets see what more we can do. Assign labels to array elements such that elements of same labels are in same connected component. Now, try to convert it into a $1-D$ array and see if we can do manipulations (eg- push another element into minimum district subarray). Trying out multiple such labellings/orderings/patterns and operating ideally on them was expected to give a good score. </p>
<h1>EXPLANATION:</h1>
<p>I will be sharing the expected solution of setter in the editorial. As usual, the editorial of challenge problem is never complete without contribution from community. So if you have any approach which is not yet covered, feel free to share it! :)</p>
<p>Setter's solution is quite simple and relies on the fact that numbers are randomly generated, so its very unlikely that theres a huge concentration of high or low values accumulated around a small area. </p>
<p>I tried to visualise the process in pic below, before beginning to explain it.</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/chefzero_lr6XXre.jpg"></p>
<p>The first step in the above algorithm would be, to try any random order. One property which must hold in that order is that, elements which are adjacent in the equivalent $1-D$ array must also be adjacent in the initial $2-D$ array as well. You can try multiple such orders, for example, in the picture above I followed the order/pattern of going from left to right, then 1 step down, then right to left ... and so on. </p>
<p>Now, for every order you try, assign the matrix elements "labels" or indices where they'd appear in $1-D$ array. Once done, convert the $2-D$ array into $1-D$ array. Now our problem reduces to "Partition a $1-D$ array into atmost $K$ partitions such that difference between highest and lowest valued partition is minimum.". Note that, following just $1$ or $2$ patterns may not give optimal answer, we simulate the process for multiple patterns/orderings. (Meaning, steps till now are simulated for multiple patterns).</p>
<p>One way of initially partitioning the array could be, find the array sum and partition whenever the size of partition is $\approx N*M/K$, other would be to partition when the partition sum is close to $\sum A_{ij}/K$. Another very good improvement is, once we get an initial partition, try "popping an element out of maximum partition" and/or "pushing an element into minimum partition" (since we made sure that elements adjacent in $1-D$ array are adjacent in $2-D$ matrix as well, its well possible). Do this as long as it helps. </p>
<p>However, note that our algorithm has an expensive step, determine and assign partition. That step takes $O(N*M)$ time, while manipulating the already partitioned array (pushing/popping as discussed before) takes significantly less time. So, its worthwhile to pay some extra attention in trying to improve manipulation techniques rather than blindly using thousands of orderings/patterns.</p>
<p>Thats it from setter's side XD. I tried to decode participants solutions but most of the top solutions are complex :( . I'd hence like to invite everybody to share their approach and how it ended up for them. Hope you guys enjoyed the problem. </p>
<h1>SOLUTION</h1>
<p><a href="https://ideone.com/uH9coT">Setter</a> </p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<pre><code>#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dbl;
typedef vector <int> vi;
typedef pair <int, int> pii;
int const N = 1002;
int const MD = 1000000007;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++(i))
#define RFOR(i, a, b) for (int (i) = (a); (i) >= (b); --(i))
#define REP(i, n) FOR(i, 0, n - 1)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define sz(v) int(v.size())
int res[N][N];
int main() {
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
vector <pii> parts;
FOR (i, 1, N) {
FOR (j, 1, M) {
if (i & 1) {
parts.pb(mp(i, j));
} else {
parts.pb(mp(i, M - j + 1));
}
}
}
int X = (N * M) / K;
int ptr = 0;
FOR (it, 1, (N * M) % K) {
FOR (i, 1, X + 1) {
res[parts[ptr].X][parts[ptr].Y] = it;
++ptr;
}
}
FOR (it, (N * M) % K + 1, K) {
FOR (i, 1, X) {
assert (ptr < sz(parts));
res[parts[ptr].X][parts[ptr].Y] = it;
++ptr;
}
}
assert (ptr == sz(parts));
FOR (i, 1, N) {
FOR (j, 1, M) {
printf("%d%c", res[i][j], j == M ? '\n' : ' ');
}
}
return 0;
}
</code></pre>
</div></div>
<p>Tester </p>
<p>Editorialist </p>
<p>$Time$ $Complexity=O(N*M)$<br>
$Space$ $Complexity=O(N*M)$ </p>
<h1>CHEF VIJJU'S CORNER :D</h1>
<p><strong>1.</strong> Setter's Notes-</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>I expected something like partition $N*M$ in components with approximately equal size $[N*M]/K$
Several times. As distribution is uniform it's <a href="http://OK.So">OK.So</a>, you can move some element from one district to another. When you find some partition Then let's try to increase the population in the minimal populated district Or decrease the population in the maximal populated district.</strong></p>
</div></div>
<p><strong>2. Hall of fame for noteworthy Solutions</strong></p>
<ul>
<li><a href="https://www.codechef.com/viewsolution/20095912"><strong>mcfx1</strong></a> - This bad boy made us change the scoring function during contest :(. Shoutout at his crisp $852$ line code! :D</li>
<li><a href="https://www.codechef.com/viewsolution/20160512"><strong>whzzt</strong></a> - Best solution in terms of score and memory. His code is $\approx 180$ lines.</li>
<li><a href="https://www.codechef.com/viewsolution/20212996"><strong>gorre_morre</strong></a> - GORRE MORRE STRIKES BACK!! :D XDD. This time with a crisp $629$ line code in python.</li>
<li><a href="https://www.codechef.com/viewsolution/20211504"><strong>algmyr</strong></a> - The guy in class who scores $99\%$ (Hint: Check his score).</li>
</ul>
<p><strong>3. A note on when questions have this random generation-</strong></p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>There are multiple times when you'll come across a question quoting "test data is randomly generated." Usually, for such problems, one thing to keep in mind is, that usually the worst case of an algorithm is HIGHLY unprobable. Like, in DARTSEGM, a problem which I shared below, the expected size of convex hull when points are randomly generated is $O(logN)$. This does not mean that for all arrangements it holds, we can make an arrangement when the size is $O(N)$, i.e. all points are part of hull, but what it means is that, since expected size is $O(LogN)$, then a huge deviation from it is NOT expected if test data is generated randomly. In other words, the worst case may (or usually will) not occur among the test data. With this in mind, you can try going forward to such questions from now on. Remember, "test data randomly generated" is the keyword, dont try this if this isnt guaranteed! XD</strong></p>
</div></div>
<p><strong>4. Related Problems-</strong></p>
<ul>
<li><a href="https://www.codechef.com/problems/DARTSEGM">DARTSEGM</a> - Randomly Generated. Enough said. XD</li>
</ul>vijju123Sun, 23 Sep 2018 18:14:16 +0530https://discuss.codechef.com/questions/135859/chefzero-editorialeditorialchallengepartitionexpectationsimulationsept182-d