Questions Tagged With snckql19https://discuss.codechef.com/tags/snckql19/?type=rssquestions tagged <span class="tag">snckql19</span>enTue, 27 Nov 2018 00:02:36 +0530SPREAD2 sigsegv errorhttps://discuss.codechef.com/questions/137544/spread2-sigsegv-error<p><a href="https://www.codechef.com/viewsolution/20671922">https://www.codechef.com/viewsolution/20671922</a></p>
<p>why was this solution showing a sigsegv error when I used a prefix sum array to solve the problem?
Any help would be appreciated. Thanks in advance.</p>eaugeneWed, 17 Oct 2018 10:29:43 +0530https://discuss.codechef.com/questions/137544/spread2-sigsegv-errorspread2snckql19easy-mediumeasysnackdownprefix-sumCHEFPRMS - EDITORIALhttps://discuss.codechef.com/questions/137277/chefprms-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFPRMS">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/CHEFPRMS">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/sieve-of-eratosthenes/">Prime Sieve</a>, or even Square root factorization would suffix, Pre-computation. Number-theory (optional).</p>
<h1>PROBLEM:</h1>
<p>Answer the queries of form, Given a number $N$, can this number be represented as sum of two semi-primes. Semi-prime is a product of any two distinct prime numbers.</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Pre-compute all primes up to $MXN$ (MAX possible value of N) (or $MXN/2$ will also suffice). Calculate all Semi-primes by iterating over all pair of distinct primes.</li>
<li>Now, calculate all possible sums which can be represented as sum of two semi-primes, by taking each pair of semi-prime.</li>
<li>Answer queries in $O(1)$ time using pre-computed values.</li>
</ul>
<h1>EXPLANATION</h1>
<p>For this problem, I am explaining two solutions, Common approach as used by Setter and Tester as well as most teams. The other one is quite an overkill, strange way to solve this problem, used by editorialist only. :D</p>
<p><strong>Setter/Tester Approach</strong></p>
<p>Calculate all the primes in range $[2,MXN]$. This can be done using Sieve of Eratosthenes or we can just naively check each number whether it is a prime or not.</p>
<p>For those unaware of Sieve of Eratosthenes, Enter the secret box.</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>We create an array and initially, mark all numbers above 1 as prime. Then, we select number marked as prime which is not yet visited. For this prime, mark all its multiples as composite. We repeat this process until there are no prime left which are not visited yet. After this, only numbers not marked as composite are prime.</p>
</div></div>
<p>Now that we have the list of primes in an array, say $pr$. Now, we need to find the list fo semi-primes. we can iterate over all pairs of <strong>Distinct</strong> primes take their product and the values in range $[1, MXN]$ are marked as semi-prime. So, now we have the list of semi-primes in range$[1, MXN]$.</p>
<p>Now, Computing final answer is just doing once again, Iterating over all pairs of semi-primes and if their sum is in range $[1, MXN]$, mark the sum as reachable.</p>
<p>Answering queries become simple, as we just need to print whether the sum $N$ is marked reachable or not.</p>
<p><strong>Editorialist's Approach</strong> (Not recommended at all :P )</p>
<p>This solution differs from above solution at the computation of list of semi-primes. Give a try to compute list of semi-primes without computing primes. It relies on the formula of <a href="https://www.cut-the-knot.org/blue/NumberOfFactors.shtml">Number of factors of a number</a>.</p>
<p>The observation is, that all semi-primes have exactly four factors. (can also be proved eaisly) But, all numbers having four factors are of two types. Both semi-primes and perfect cubes will always have 4 factors. So, we iterate over all numbers, check if it has exactly four factors (including trivial factors) and is not perfect cube. If any number satisfy both criteria, it is marked as semi-prime.</p>
<p>After that, this solution is same as Author/Tester solution.</p>
<h1>Time Complexity</h1>
<p>Both Solutions have pre-computation time $O(MXN^2)$ for iterating over all pairs of semi-primes, which dominates everything.</p>
<p>For a fact, Sieve of Eratosthenes takes $O(N*log(logN))$ time while Square root factorization takes $O(N*\sqrt{N})$ time.</p>
<p>Queries are answered in $O(1)$ time, taking overall $O(T)$ time.</p>
<p>SO, overall complexity is $O(MXN^2)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/CHEFPRMS.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/CHEFPRMS.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/CHEFPRMS.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sun, 14 Oct 2018 14:25:55 +0530https://discuss.codechef.com/questions/137277/chefprms-editorialtaran_1407chefprmsnumber-theoryprecomputationsnckql19easysieveSPREAD2 - EDITORIALhttps://discuss.codechef.com/questions/137183/spread2-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SPREAD2">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/SPREAD2">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Prefix sums or anything similar.</p>
<h1>PROBLEM:</h1>
<p>Given a group of $N$ people. At day 0, only person 1 knows about Snackdown. Array $A$ is given, $A[i]$ means the number of people ith person will inform. This means, that if at day t, ith person knows about snackdown, exactly $A[i]$ more people will know about Snackdown on day t+1. Find minimum number of days to make sure all $N$ people know about Snackdown.</p>
<p>People spread information in increasing order of position. i.e. If person at position $p$ doesn't know about Snackdown, all people after position $p$ also won't know.</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Make prefix sum array, call it $pre$. If $x$ people know about Snackdown on day $T$, then $pre[x]$ more people will know about Snackdown on day $T+1$.</li>
</ul>
<h1>EXPLANATION</h1>
<p>First of all, I am explaining a brute force solution, then we'll optimise it using prefix arrays.</p>
<p>Let us consider naive solution. On day 0, only 1 person knows about snackdown. Next day, $X = 1+A[1]$ people will know. Next day, $X = X+A[1]+A[2] + \dots +A[X]$ people will know. So, we can just increase $X$ by $A[1]+A[2]+A[3]+ \dots +A[X]$. This process continues till $X < N$. Let call $S = A[1]+A[2]+ \dots +A[X]$. Every time, we can calculate $S$ by iterating from index $1$ to $X$.</p>
<p>This process leads to an $O(N^2)$ algorithm.</p>
<p>Now, The thing to speed up above is that, we can calculate $S$ faster than $O(N)$ time by noticing that $S$ is just sum of First $X$ numbers. We can precalculate prefix sum array of given array $A$, let's call it $pre$ and Notice that S is just $pre[x]$, thus, computing $S$ in $O(1)$ time, which results in overall $O(N)$ time, which easily fit the time limit.</p>
<p>Also, In case you are not in mood to compute prefix array, it can also be solved by a sum variable, the idea of which is left as an exercize for readers.</p>
<h1>BONUS</h1>
<ul>
<li>Problem statement states $A[1] \geq 1$. What happens if $A[1] ==0$.</li>
<li>Solve a modified problem. People are not notified in increasing order of position. People who know, can tell anyone. Find minimum as well as maximum number of days it takes for all $N$ people to know about Snackdown.</li>
</ul>
<h1>Time Complexity</h1>
<p>Since We iterate over all elements once, as well as prefix array construction takes linear time, Time complexity is $O(N)$.</p>
<p>Memory complexity is $O(N)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/SPREAD2.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/SPREAD2.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/SPREAD2.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sat, 13 Oct 2018 15:51:05 +0530https://discuss.codechef.com/questions/137183/spread2-editorialprefix-sumtaran_1407spread2snckql19easyQABC - EDITORIALhttps://discuss.codechef.com/questions/137173/qabc-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/QABC">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/QABC">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>Observations and simple Invariant would do the trick. Just a creative or experienced mind is sufficient. :D</p>
<h1>PROBLEM:</h1>
<p>Given two sequence $A$ and $B$ of length $N$ each, we need to apply operation on array $A$ to make it same as array $B$. The operation is decsribed as
<em> Choose any position $i$ in range $[1, N-2]$.
</em> Do $A[i] += 1$, $A[i+1]+=2$ and $A[i+2]+=3$. (Called as applying operation on position $i$.)</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Perform operations from left to right. If $A[i] > B[i]$ at any point, answer is $-1$. Also, If after applying operations till position position $N-2$, If last two elements differ in both arrays, answer is again impossible.</li>
<li>If $A[i] == B[i]$, we can directly move to next position without applying operation. If $A[i] < B[i]$, we apply operation $B[i]-A[i]$ times at position $i$ and move to next position.</li>
</ul>
<h1>EXPLANATION</h1>
<p>This problem require certain observations, which are stated below.</p>
<p>If $A[i]>B[i]$ after any number of operations (including zero), answer is impossible since we can never reduce $A[i]$ or increase $B[i]$, hence achieving $A[i]==B[i]$ is impossible now.</p>
<p>Second crucial thing is, that the order of applying operations is irrelevant. That is, Suppose we apply operation at position 2 first, followed by operation at position 1. It will give same results as applying operation at position 1 followed by operation at position 2.</p>
<p>Second observation allow us to apply operations from left to right, because, if a valid sequence of operations exist, there will also exist a perumtation of those operations which are arranged from left to right.</p>
<p>But you might be wondering why should we apply operations from left to right. So, here we go.</p>
<p>Since we know, that $A[i]$ can only be altered by operations applied at position $i$, $i-1$ and $i-2$. But, $A[1]$ can only be altered by operation at position 1. So, we have to apply operation at position 1 $B[i]-A[i]$ times. Now, We face same problem again. $A[2]$ can be altered by operation at position $1$ and $2$. But we cannot apply operation at position 1 anymore, since it will also increase $A[1]$ leading to impossible case.</p>
<p>Here, we have the <strong>invariant</strong>, that once we reach position i, we have made $A[j] == B[j] \forall j < i$, thus, we have to apply operation $B[i]-A[i]$ times, so that We achieve $A[i]==B[i]$. After applying operations, we can no longer apply operation at any position j, $j \leq i$. This continues till we reach $N-2$ position.</p>
<p>At the end, If after appling operation for all positions in range $[1, N-2]$, if elements at last two positions in both arrays do not match, we can never make array $A$ same as array $B$, thus, answer becomes impossible in this case too.</p>
<p>PS: A new term for today is <strong>Invariant</strong>, useful in proving correctness of an algorithm or process, which can be read about <a href="https://en.wikipedia.org/wiki/Invariant_(computer_science)">here</a>.</p>
<h1>Time Complexity</h1>
<p>Since we iterate from left to right across whole range, Time complexity is $O(N)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/QABC.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/QABC.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/QABC.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sat, 13 Oct 2018 13:03:57 +0530https://discuss.codechef.com/questions/137173/qabc-editorialsimpletaran_1407qabcsnckql19observationsQUALPREL - EDITORIALhttps://discuss.codechef.com/questions/137155/qualprel-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/QUALPREL">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/QUALPREL">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Sorting would be enough.</p>
<h1>PROBLEM:</h1>
<p>Given scores of $N$ teams, and an integer $K$, the number of teams from the top to qualify, Find out number of teams qualify if in case of tie at Kth position, All teams tying with Kth team will also qualify.</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Sort the scores, and count number of teams having score greater than or equal to Kth team. (Shortest explanation ever from my side :P)</li>
</ul>
<h1>EXPLANATION</h1>
<p>As the problem statement itself mentions, Teams will be sorted in descending order by their score and Top K teams will be selected. </p>
<p>First of all, Assume that all scores are distinct. Now, we are sure that there won't be any tie for Kth rank. Exactly $K$ teams will qualify.</p>
<p>Now, when two or more teams can score same, either all of them will qualify, or none of them. So, we just need to find the score $X$ such that all teams with score $s[i] /geq X$ will qualify, while teams with $s[i] < X$ will not.</p>
<p>We can see that $X$ is actually the score of Kth team, if all teams are sorted by their score.</p>
<p>So, we can just sort the scores, find $X$ and iterate over all elements, increasing answer by one whenever we see a team with $s[i] \geq X$.</p>
<p><strong>Problems for Practice can be found <a href="https://www.codechef.com/tags/problems/sorting">here</a>.</strong></p>
<h1>Time Complexity</h1>
<p>Time complexity is $O(N*logN)$ due to sorting. Iterating over the elements takes $O(N)$ time.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/QUALPREL.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/QUALPREL.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/QUALPREL.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sat, 13 Oct 2018 04:28:09 +0530https://discuss.codechef.com/questions/137155/qualprel-editorialtaran_1407sortingsnckql19qualprelcakewalk(HARD TO DETECT)What's wrong in my TEAMMATE submission?https://discuss.codechef.com/questions/137723/hard-to-detectwhats-wrong-in-my-teammate-submission<p><em>Link of codechef submission :</em>
<a href="https://www.codechef.com/viewsolution/20852630"><strong></strong></a><strong><a href="https://www.codechef.com/viewsolution/20852630">https://www.codechef.com/viewsolution/20852630</a></strong></p>
<p><em>Link if you directly want to fork in online compiler :</em>
<a href="https://ideone.com/NN1rqk"><strong></strong></a><strong><a href="https://ideone.com/NN1rqk">https://ideone.com/NN1rqk</a></strong></p>
<p>Please explain where are the things going wrong.</p>geek0Fri, 19 Oct 2018 17:29:35 +0530https://discuss.codechef.com/questions/137723/hard-to-detectwhats-wrong-in-my-teammate-submissionteammatesnckql19snackdownQUALPREL : Not understanding the reason for TLE,.https://discuss.codechef.com/questions/141179/qualprel-not-understanding-the-reason-for-tle<p>Why am I getting TLE when complexity is still O(nlogn) as mentioned in Editorial <a href="https://discuss.codechef.com/questions/137155/qualprel-editorial?page=1#141179">Solution</a> and I used binary search in increasingly sorted array which is O(logn) instead of traversing elements in O(n) </p>
<pre><code>#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int tests;
cin >> tests;
while(tests--){
int n, k;
cin >> n >> k;
int arr[n];
for(int i=0; i<n; i++){
cin >> arr[i];
}
sort(arr, arr+n);
int x = arr[n-(k-1)-1];
int low = 0, high = n-1, mid = (low+high)/2;
while(low<=mid){
if(arr[mid]<x)
low = mid+1;
else
high = mid-1;
mid = (low+high)/2;
}
cout << n-(high+1) << '\n';
}
return 0;
}
</code></pre>kishansairam9Tue, 27 Nov 2018 00:02:36 +0530https://discuss.codechef.com/questions/141179/qualprel-not-understanding-the-reason-for-tlekingofnumberssortingsnckql19cakewalktaran_1407TEAMMATE - EDITORIALhttps://discuss.codechef.com/questions/137271/teammate-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/TEAMMATE">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/TEAMMATE">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Combinatorics, <a href="https://en.wikipedia.org/wiki/Rule_of_product">Fundamental principle of Counting</a>.</p>
<h1>PROBLEM:</h1>
<p>Given skill $S$ of $N$ programmers ($N$ is even), we want to find number of ways to form teams such that There doesn't exist two teams $(A, B),(C,D)$ such that $S_D > S_B$ and $S_A > S_C$.</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Sort the scores in descending (or ascending) order. Try to make pair from left to right while handling programmers having same skill level combined.</li>
<li>If there are $X$ programmers with same skill, and $X$ is odd, We select the player which will be left out first, and then count the number of ways to make pairs out of remaining players.</li>
<li>In case we have a left over from higher (or lower) skill yet to be paired, We count first, the number of ways to select one player out of all players of immediately lower (or higher) skill. After that, we do what i mentioned in second point.</li>
</ul>
<h1>EXPLANATION</h1>
<p>First of all, As i usually do, consider constraint that no two players have same skill level. We can see that there will always exist exactly one valid team formation, which pairs players like, best with second best, third with fourth and so on till all players are paired. </p>
<p>So, we know, that the multiple valid team formulation arises only when there are multiple players with same skill level.</p>
<p>Now, since this problem involves combinatorics, which i like to explain by examples, so, here we begin examples.</p>
<p>Consider example scores $2,2,2,2$.</p>
<p>We can see that player at position 1 can pair with any of three, and remaining two players pair with each other, giving $3*1 = 3$ ways.</p>
<p>Consider example scores $2,2,2,2,2,2$.</p>
<p>Same idea, just that first player has 5 choices. Now, we have four players left. Let us assume, we pair the <strong>leftmost unpaired player</strong>, and count number of ways for him to form team. He has 3 choices. After removing him and his partner too, only two players left, which pair with each other, giving $5*3*1 = 15$ ways.</p>
<p>Consider example scores $2,2,2,2,2,2,2,2$.</p>
<p>Once again, Same idea, So i ask you to apply this idea to calculate it before seeing its explanation in secret box.</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>Number of choices for leftmost unused player is 7. Six players left. <br>
Number of choice for leftmost unused player is 5 now. Four players left. <br>
Number of choice for leftmost unused player is 3 now. Two players left. <br>
Number of choice for leftmost unused player is 1 now. No players left.<br>
Final number of ways is $7*5*3*1 = 105$ ways.</p>
</div></div>
<p>You all must be wondering why he's boring us with same test case. My point is to ask you all to notice the pattern.</p>
<p>Last example of this type. $2,2,2,2\dots 2$ N times.</p>
<p>Now, what did we learn from previous examples. First player has $(N-1)$ choices, next leftmost unused player has $(N-3)$ choice and so on.</p>
<p>Final Number of ways become $(N-1)*(N-3)* \dots *5*3*1$. This can also be calculated as $\frac{(2*m)!}{2^m*m!}$ where $m = n/2$.</p>
<p>Looking for a proof? Here you go.</p>
<p>When all skill levels are same, the problem is to count number of ways to divide $2*M$ elements into $M$ pairs. We can see, that every permutation of elements correspond to a team formation, where First player is paired with second, third player is paired with fourth and so on. Number of permutations is $(2*M)!$</p>
<p>For example, Take any permutation, say for $M = $ as 1234, this correspond to teams $(1,2),(3,4)$. But, we see, that permutation 1243 also correspond to same teams, as order of players in a team doesn't matter. Team $(1,2)$ is same as $(2,1)$. Since there are $M$ pairs, there are $2^M$ different permutations representing same teams, just having their players swapped. So, Number of ways of forming team without double counting these swaps is $\frac{(2*M)!}{2^M}$.</p>
<p>But, the ordering of teams is also double counted. Permutation 1234 represent teams $(1,2),(3,4)$ which is same as $(3,4),(1,2)$ represented by permutation 3412.</p>
<p>To avoid double counting, we need to see how many times each team formulation is being counted. It is easy to see that, we have $M$ unordered pairs. Each permutation of these $M$ pairs will be counted. This means that there are $M!$ permutations corresponding to each team, so, we just divide the Number of ways by $M!$.</p>
<p>Final Number of ways become $\frac{(2*M)!}{2^M*M!}$ which gives us correct number of ways to divide $2*M$ players into unordered pairs where permutation of teams doesn't matter. This is what we require.</p>
<p>Till now, we only considered all examples which had same skill level for all players.</p>
<p>Consider another example 1 1 2 2 2 2.</p>
<p>We can see, that players of skill level 1 will be paired among each other, while players of skill level 2 will be paired among each other. By Fundamental principle of counting, we see these are just product of above two. Number of ways for team with skill 1 is 1, while Number of ways to form teams with skill 2 are $3*1$. Total Number of ways is just $1*3 = 3$ ways.</p>
<p>Now, we know how to count number of teams <strong>When there are even number of players with same skill</strong>.</p>
<p>But when number of players of a skill level is odd, One player of that skill level has to be paired with a player of different skill. Now, <strong>A player cannot be paired with anyone having not immediately lower (or higher) skill.</strong> Player with skill 1 can never be paired with player having skill 3 as long as there exist even a single player having skill 2.</p>
<p>Suppose 1 2 2 3 is the skill levels. Player 1 can be paired with either player 2 or player 3. Other person can be paired with player 4, resulting in $2$ total ways.</p>
<p>Our second last example for today is 1 1 1 1 1 2 2 2 2 2 2 3 3 3.</p>
<p>We handle players of same skill together, in increasing (or decreasing, which you like) order of skill.</p>
<p>First we have 5 players of skill 1. We know, One of the player of skill 1 will be paired with player of skill 2. Number of ways to select that 1 player is 5. Remaining 4 players divided into unordered pairs in $3*1$ ways.</p>
<p>Then we have 6 players of skill 2 and one player of skill 1 left. Firstly, we can pair player with player 1 with any of the six, In six ways. Now, 5 players of skill level left. One chosen player will be left out, we can choose in 5 ways. 4 players left, which are divided into pairs in $3*1$ ways.</p>
<p>Lastly, we have 3 players of skill 3 and one player of skill 2 to be paired. Once again, we choose player to be paired with player of skill 2, which can be done in 3 ways. Two players of skill 3 left, which can be divided into teams in 1 way.</p>
<p>Since all these events have to be performed together, then by principle of counting, the final answer is just product of all these. that is. Required Number of ways is $5*3*6*5*3*3*1 = 4050$ ways which is the required answer.</p>
<p>This was all for today, though you can read more about the proof <a href="https://www.quora.com/How-many-ways-are-there-to-divide-m-people-into-pairs-assuming-there-are-an-even-number-of-people">here</a>, as well as, you can find proof by searching about "Dividin $N$ elements into pairs."</p>
<h1>Bonus Question</h1>
<p>Instead of SnackDown, Given skill of $N$ players, Make teams for ACM-ICPC regionals. It is given that $N$ is divisible by 3. Leave answer in comments.</p>
<h1>Time Complexity</h1>
<p>Time complexity is $O(N*LogN)$ due to sorting. Ordered Frequency map can also be used and is preferable.</p>
<p>PS: The solutions based on same idea, which tried to make a frequency array instead of frequency map, got TLE, because of the test file can have up to 1000 test cases of small size, in which case, your solution tried to complete $O(T*10^6)$ iterations which will surely time out.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/TEAMMATE.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/TEAMMATE.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/TEAMMATE.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sun, 14 Oct 2018 12:43:16 +0530https://discuss.codechef.com/questions/137271/teammate-editorialcombinatoricsteammatesnckql19easy-mediumtaran_1407