Questions Tagged With setshttps://discuss.codechef.com/tags/sets/?type=rssquestions tagged <span class="tag">sets</span>enSun, 28 Jan 2018 05:02:04 +0530Sorting sets as per a return valuehttps://discuss.codechef.com/questions/7569/sorting-sets-as-per-a-return-value<p>i have the following problem
We have a set S of n potential investments, each given by a pair of floating point numbers (amount, estimated return) There is a total amount A to invest; we want to select investments to maximise the return on this amount.</p>
<p>please explain how do i order the investments using the ratio estimated return/amount, in nlogn. is this using quick sort? i can calculate the ratios in O(n) then how do i keep an index as to which ratio belongs to which investment?</p>
<p>am trying to solve it using the following algo</p>
<p>1.order the investments according to the decreasing ratio r/a
2.allocate available money to the investments in such order. I.e. buy all the first investment, then use available money to buy the second investment, then the third, etc, until the money is finished.</p>karanahluwaliaTue, 19 Mar 2013 14:00:36 +0530https://discuss.codechef.com/questions/7569/sorting-sets-as-per-a-return-valuesortingsetsCodechef setshttps://discuss.codechef.com/questions/51379/codechef-sets<p>How to access already created set without directly typing the url in the address bar?</p>gtm93singhSat, 20 Sep 2014 20:02:54 +0530https://discuss.codechef.com/questions/51379/codechef-setssetscode chef setshttps://discuss.codechef.com/questions/56032/code-chef-sets<p>just a quick question, i havent explored this but i want to ask what does this sets mean?
<br>
<a href="http://www.codechef.com/sets">http://www.codechef.com/sets</a>
<br> thanks :)</p>ramher237Fri, 21 Nov 2014 14:49:29 +0530https://discuss.codechef.com/questions/56032/code-chef-setssetswhat are setshttps://discuss.codechef.com/questions/56797/what-are-sets<p>What is sets in codechef and how to use it?</p>hellobrotherSat, 29 Nov 2014 21:44:50 +0530https://discuss.codechef.com/questions/56797/what-are-setswhataresetsTLE using setshttps://discuss.codechef.com/questions/62811/tle-using-sets<p><a href="http://www.codechef.com/RCSN2015/problems/RECREP">This</a> is a very simple question, I tried <a href="http://www.codechef.com/viewsolution/6003855">this</a> because I thought searching in the set takes logarithmic time, thinking it'll pass easily. Why it is giving TLE?</p>damn_meMon, 26 Jan 2015 00:39:10 +0530https://discuss.codechef.com/questions/62811/tle-using-setsc++setsSets in codechefhttps://discuss.codechef.com/questions/51273/sets-in-codechef<p>What are sets in codechef. I mean I found a new icon in my profile.On hovering mouse onto that it displays 'create new set'. So what are sets ?</p>achaitanyasaiThu, 18 Sep 2014 20:25:50 +0530https://discuss.codechef.com/questions/51273/sets-in-codechefsetsGenerate all the k-element subsets from a n-element set (n>k).https://discuss.codechef.com/questions/28080/generate-all-the-k-element-subsets-from-a-n-element-set-nk<p>To generate all the k-element subsets from a n-element set (n>k), there is a recursive solution - add a particular element to all the (k-1) element subsets.Follow the same step to get all (k-1) element subsets.
I have been unable to put the above idea to code.Could someone help?</p>piyukrWed, 30 Oct 2013 23:34:25 +0530https://discuss.codechef.com/questions/28080/generate-all-the-k-element-subsets-from-a-n-element-set-nksubsetcalgorithmsetsmathematicsbacktrackingPAINTBOX - editorialhttps://discuss.codechef.com/questions/66952/paintbox-editorial<p><b>PROBLEM LINK:</b><br>
<a href="http://www.codechef.com/problems/PAINTBOX">Practice</a><br>
<a href="http://www.codechef.com/LTIME22/problems/PAINTBOX">Contest</a><br></p>
<p><b>Author:</b> <a href="http://www.codechef.com/users/pankaj%20jindal">Pankaj Jindal</a>, <a href="http://www.codechef.com/users/piyushkumar">Piyush Kumar</a> <br>
<b>Tester: </b><a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br>
<b>Editorialist:</b> <a href="http://www.codechef.com/users/amanjain110893">Aman jain</a><br></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Set, Segment Tree</p>
<h1>PROBLEM:</h1>
<p>Given a array $A$ of size N each filled with a color with value $A_i$. There are $Q$ queries, each query update color of box at position $Pos_i$ with color $Col_i$. For each query you need to find number of ways to select $W$ adjacent boxes of same color from total of $N$ boxes.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Maintain a set of starting indices of color segments. Now on each query there are three possibilities, either we assign the same color, so no change to the array, or we have an update that breaks a continuous segment of colors, or an update that joins two continuous segments, each of which can be done in $O(log(N))$. Update your answer for the query and correspondingly update set of starting indices of color segments.</p>
<h1>EXPLANATION:</h1>
<p>Let's start with easy constraints. Let say you have a color segment of length $L$, then number of ways to select $W$ adjacent boxes from this segment would be $max(0,(L-W+1))$. Now if you have sequence of segments say, $s1s2s3s4$, then number of ways to select $W$ boxes would be sum of number of ways for each segment i.e. $\sum{max(0,L_i-W+1)}$. Complexity of this solution would be $O(N*Q)$, this works within time-limit for first sub-task but will fail on main task.<br><br>
To solve hard part efficiently, we can store the result of the query for the input string in $ans$ and maintain set that store starting indices of color segments. After each query operation we need to insert or erase indices from set accordingly.<br>
If you analyse closely you will find that each update operation looks like:<br>
a) if update operation, does not change the state of boxes from current state, then there will be no change in answer to this query. <br>
b) state change can be described as, $......s_a c1 s_b......$ to $......s_a c2 s_b......$, where $s_a$ is segment to the left and $s_b$ segment to the right of update position $pos_i$, with box color changed from $c1$ to $c2$.<br><br> Following cases possible (assuming 0 based indexing):<br>
1) $pos_i$ is 0 and $c1$ lies in $s_b$ i.e. same in color to $s_b$, after the operation splitting takes place and $ans = ans - ways(len(s_b)+1) + ways(len(1)) + ways(len(s_b))$, here ways(l) means number of ways to get $W$ adjacent boxes from segment of length $l$.<br>
2) $pos_i$ is 0 and $c1$ does not lies in $s_b$, after updation $c2$ lies in $s_b$, so merging takes place. $ans = ans - ways(1) - ways(len(s_b)) + ways(len(s_b)+1)$.<br>
3) $pos_i$ is 0 and $c1$ and $c2$ both does not lie in $s_b$, no change in answer.<br>
4) $pos_i$ is $N-1$ and $c1$ lies in $s_a$, after the operation splitting takes place and $ans = ans - ways(len(s_a)+1) + ways(len(1)) + ways(len(s_a)).$<br>
5) $pos_i$ is $N-1$ and $c1$ does not lies in $s_a$, after updation $c2$ lies in $s_a$, so merging takes place. $ans = ans - ways(1) - ways(len(s_a)) + ways(len(s_a)+1).$<br>
6) $pos_i$ is $N-1$ and $c1$ and $c2$ both does not lie in $s_a$, no change in answer.<br>
7) for rest of the cases $pos_i$ lies in between 0 and $N-1$, $s_a = s_b$, i.e. same in color and $c1$ lies in $s_a$, now splitting takes place, $ans = ans - ways(len(s_a)+1+len(s_b)) + ways(len(s_a)) + ways(1) + ways(len(s_b))$.<br>
8) $s_a = s_b$, $c1$ does not lies in $s_a$, $c2$ lies in $s_a$, $ans = ans - + ways(len(s_a)) - ways(1) - ways(len(s_b)) + ways(len(s_a)+1+len(s_b)).$<br>
9) $s_a = s_b$, $c1$ and $c2$ does not lies in $s_a$, no change in answer.<br>
10) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ lies in $s_b$, $ans = ans - ways(len(s_a)+1)+ways(len(s_a))-ways(len(s_b))+ways(len(s_b)+1)$.<br>
11) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ does not lie in both, $ans = ans - ways(len(s_a)+1) + ways(1) + ways((len(s_a))$.<br>
12) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ lies in $s_a$, $ans = ans - ways(len(s_b)+1)+ways(len(s_b))-ways(len(s_a))+ways(len(s_a)+1)$.<br>
13) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ does not lie in both, $ans = ans - ways(len(s_b)+1) + ways(1) + ways((len(s_b))$.<br>
14) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_a$, $ans = ans - ways(1)-ways(len(s_a))+ways(len(s_a)+1)$.<br>
15) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_b$, $ans = ans - ways(1)-ways(len(s_b))+ways(len(s_b)+1)$.<br>
16) $s_a != s_b$, $c1$ and $c2$ does not lies in both $s_a$ and $s_b$, no change in answer.<br></p>
<h1>COMPLEXITY:</h1>
<p>Each query operation requires insertion, deletion of elements from set and answer update, all can be done in $O(log(N))$. For $Q$ queries, overall complexity would be $O(Q*log(N))$.</p>
<h1>ALITER:</h1>
<p>Tester <a href="http://www.codechef.com/users/xcwgf666">Sergey</a> also suggested that above problem can be solved using Segment Tree, which would be much modular approach than handling many cases. <b>HINT:</b> For each node of segment tree stores length of color segment from left and length of color segment from right, color of left and right segment and ans for query for segment range. Update these values accordingly on each query operation.<br>
If you are not able to solve the problem using Segment Tree, go through <a href="http://www.codechef.com/users/xcwgf666">Sergey</a> code in refernces.<br>
</p><p>
<b>AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:</b>
<br><a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Setter/PAINTBOX.cpp">author</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Tester/PAINTBOX.cpp">tester</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Editorialist/PAINTBOX.cpp">editorialist</a><br></p>amanjain110893Thu, 26 Mar 2015 20:47:02 +0530https://discuss.codechef.com/questions/66952/paintbox-editorialsegment-treeltime22mediumsetsCOVERING - Editorialhttps://discuss.codechef.com/questions/56243/covering-editorial<p><strong>Problem Link:</strong> <a href="http://www.codechef.com/COOK52/problems/COVERING">contest</a>, <a href="http://www.codechef.com/problems/COVERING">practice</a></p>
<p><strong>Difficulty:</strong> Medium-Hard</p>
<p><strong>Pre-requisites:</strong> Set Theory, Divide-and-Conquer, Inclusion-Exclusion Principle</p>
<p><strong>Problem:</strong></p>
<p>Given a set <strong>S</strong> of <strong>N</strong> different elements numbered from <strong>0</strong> to <strong>N - 1</strong>. A triple (<strong>A</strong>, <strong>B</strong>, <strong>C</strong>) of subsets of S covers a subset <strong>D</strong> of <strong>S</strong>, if <strong>D</strong> is a subset of the union of subsets <strong>A</strong>, <strong>B</strong> and <strong>C</strong>. In other words, every element of <strong>D</strong> is an element of at least one of <strong>A</strong>, <strong>B</strong>, or <strong>C</strong>.</p>
<p>Given three functions <strong>F</strong>, <strong>G</strong> and <strong>H</strong>, each takes a subset of <strong>S</strong> as the only parameter and returns a non-negative integer. You are given the values of <strong>F(i)</strong>, <strong>G(i)</strong>, and <strong>H(i)</strong> for each 0 ≤ <strong>i</strong> < 2<strong><sup>N</sup></strong>.</p>
<p>The value of a function <strong>R</strong> of a subset <strong>X</strong> of <strong>S</strong> is equal to the sum of <strong>F(A) × G(B) × H(C)</strong> for all triples (<strong>A</strong>, <strong>B</strong>, <strong>C</strong>) of subsets of <strong>S</strong> that cover <strong>X</strong>.</p>
<p>Your task is to calculate <strong>R(0) + R(1) + ... + R(2<sup>N</sup> - 1)</strong>.</p>
<p><strong>Explanation:</strong></p>
<p>This problem is the hardest one, it was supposed to be solved by a very few number of contestants.</p>
<p>First of all, I want you to get familiar with <a href="http://codeforces.com/contest/449/problem/D">this problem</a> and <a href="http://codeforces.com/blog/entry/13112">its editorial</a>. It would be rather helpful for you to understand my editorial. <a href="http://codeforces.com/blog/entry/10476">The "solution fount by contestants"</a> of <a href="http://codeforces.com/contest/383/problem/E">this problem</a> may also help you to understand one of the keypoints of the following solution.</p>
<hr>
<p>It seems like some of the contestants came up with quite easier solutions, I will be grateful if you, guys, share your approaches in the comments.</p>
<hr>
<p>Let's consider a function <strong>P(A, B, C)</strong> that is equal to <strong>F(A) × G(B) × H(C) × 2<sup>the number of elements in the union of A, B and C</sup></strong>. </p>
<p>The first observation: <strong>R(0) + R(1) + ... + R(2<sup>N</sup> - 1)</strong> equals to <strong>P(0, 0, 0) + P(0, 0, 1) + ... + P(2<sup>N</sup> - 1, 2<sup>N</sup> - 1, 2<sup>N</sup> - 1)</strong>, i.e. the answer equals to the sum of all possible <strong>P</strong>'s. So, from now we are interested only in calculating the second sum. </p>
<p>The second observation is based on <a href="http://en.wikipedia.org/wiki/De_Morgan%27s_laws">De Morgan's laws</a>: if <strong>D</strong> is a subset of the union of subsets <strong>A</strong>, <strong>B</strong> and <strong>C</strong>, then the intersection of <strong>~A</strong>, <strong>~B</strong> and <strong>~C</strong> is a subset of <strong>~D</strong>, where <strong>~X</strong> is equal to <strong>S \ X</strong>. So, after that observation we can say that the function <strong>P(A, B, C)</strong> equal to <strong>F(A) × G(B) × H(C) × 2<sup>N - (the number of elements in the intersection of ~A, ~B and ~C)</sup></strong>. </p>
<p>Let's reverse the arrays of the functions <strong>F</strong>, <strong>G</strong> and <strong>H</strong>, i.e. assign the following:</p>
<ul>
<li><strong>F(i) := F(2<sup>N</sup> - 1 - i)</strong>;</li>
<li><strong>G(i) := G(2<sup>N</sup> - 1 - i)</strong>;</li>
<li><strong>H(i) := H(2<sup>N</sup> - 1 - i)</strong>.</li>
</ul>
<p>This can be done in <strong>O(N)</strong> time by simply reversing each of the arrays.</p>
<p>After doing that we can consider another function <strong>Q(A, B, C)</strong> that is equal to <strong>F(A) × G(B) × H(C) × 2<sup>N - (the number of elements in the intersection of A, B and C)</sup></strong>.</p>
<p>The third observation: <strong>P(0, 0, 0) + P(0, 0, 1) + ... + P(2<sup>N</sup> - 1, 2<sup>N</sup> - 1, 2<sup>N</sup> - 1)</strong> before reversing equals to <strong>Q(0, 0, 0) + Q(0, 0, 1) + ... + Q(2<sup>N</sup> - 1, 2<sup>N</sup> - 1, 2<sup>N</sup> - 1)</strong> after reversing.</p>
<p>Now, let's make another transformation of the arrays of the functions <strong>F</strong>, <strong>G</strong> and <strong>H</strong>:</p>
<ul>
<li><strong>F(i) := F(s<sub>1</sub>) + F(s<sub>2</sub>) + ... + F(s<sub>K</sub>)</strong>, where each <strong>s<sub>j</sub></strong> is a superset of <strong>i</strong>;</li>
<li><strong>G(i) := G(s<sub>1</sub>) + G(s<sub>2</sub>) + ... + G(s<sub>K</sub>)</strong>, where each <strong>s<sub>j</sub></strong> is a superset of <strong>i</strong>;</li>
<li><strong>H(i) := H(s<sub>1</sub>) + H(s<sub>2</sub>) + ... + H(s<sub>K</sub>)</strong>, where each <strong>s<sub>j</sub></strong> is a superset of <strong>i</strong>.</li>
</ul>
<p>This part can be done in <strong>O(N × 2<sup>N</sup>)</strong> time by a divide-and-conquer approach on each of the arrays. The approach is described <a href="http://codeforces.com/blog/entry/13112">here</a>(problem 449D - Jzzhu and Numbers).</p>
<p>Here's a part of Setter's solution that does this transformations:</p>
<pre>void rec( int l, int r )
{
if ( l == r ) return;
int x = ( l + r ) / 2, len = ( r - l + 1 ) / 2;
rec( l, x );
rec( x + 1, r );
for ( int i = l; i <= x; i++ )
{
f[i] += f[ i + len ];
g[i] += g[ i + len ];
h[i] += h[ i + len ];
}
}
</pre>
<p>Let's consider another function <strong>T(X)</strong> that is equal to the <strong>F(X) × G(X) × H(X)</strong>. In other words, it's the sum of <strong>F(A) × G(B) × H(C)</strong> for all triples(<strong>A</strong>, <strong>B</strong>, <strong>C</strong>) such that <strong>X</strong> is a subset of the intersection of <strong>A</strong>, <strong>B</strong> and <strong>C</strong>. </p>
<p>At the same time, we can say, that the sum of <strong>F(A) × G(B) × H(C)</strong> for all triples(<strong>A</strong>, <strong>B</strong>, <strong>C</strong>) such that <strong>X</strong> is equal to the intersection of <strong>A</strong>, <strong>B</strong> and <strong>C</strong> can be simply calculated with a help of the inclusion-exclusion principle. For example, if <strong>X</strong> = 0 then it's equal to <strong>T(0)</strong> - <strong>T(1)</strong> - <strong>T(2)</strong> + <strong>T(3)</strong> - <strong>T(4)</strong> + <strong>T(5)</strong> + ... + (-1)<sup>the number of elements in <strong>X</strong></sup> × <strong>T(X)</strong>. For arbitrary set <strong>X</strong> the sum equals to the similar linear combination of supersets of <strong>X</strong>. </p>
<p>The answer is equal to the sum of the following values: <strong>2<sup>N - (the number of elements in X)</sup></strong>
× (the sum of <strong>F(A) × G(B) × H(C)</strong> for all triples(<strong>A</strong>, <strong>B</strong>, <strong>C</strong>) such that <strong>X</strong> is equal to the intersection of <strong>A</strong>, <strong>B</strong> and <strong>C</strong>) for all <strong>X</strong> from 0 to <strong>2<sup>N</sup> - 1</strong>. As we have just discussed, the second multiplier is a linear combination of <strong>T</strong>'s, so the answer is also a linear combination of <strong>T</strong>'s. The question is how to find the coefficients of that linear combination.</p>
<p>Let's first assign <strong>coefficient<sub>X<sub></sub></sub></strong> := <strong>2<sup>N - (the number of elements in X)<sup></sup></sup></strong>. Then, we can do a similar divide-and-conquer approach as we did while transforming the arrays of the functions of <strong>F</strong>, <strong>G</strong> and <strong>H</strong>:</p>
<pre>void rec( int l, int r )
{
if ( l == r ) return;
int x = ( l + r ) / 2, len = ( r - l + 1 ) / 2;
rec( l, x );
rec( x + 1, r );
for ( int i = l; i <= x; i++ )
{
coefficient[ i + len ] -= coefficient[ i ];
}
}
</pre>
<p>We are doing exactly what the inclusion-exclusion principle tells us: since the sets <strong>X</strong> and <strong>X + {a}</strong> differ in exactly one element, then we should increase <strong>coefficient<sub>X + {a}</sub></strong> by (-1) × <strong>coefficient<sub>X</sub></strong>, because if two sets differ in the odd number of elements, then the coeffient is -1.</p>
<p>The only thing that is left to do is to calculate the answer:</p>
<pre>for ( int x = 0; x < 2<sup>N</sup>; x++ ) answer += coefficient[x] × t[x];
</pre>
<p>The total complexity of the solution is <strong>O(N × 2<sup>N</sup>)</strong>.</p>
<p>Please, check out Setter's and Tester's solutions for your better understanding.</p>
<p><strong>Setter's Solution:</strong> <a href="http://www.codechef.com/download/Solutions/COOK52/Setter/COVERING.cpp">link</a></p>
<p><strong>Tester's Solution:</strong> <a href="http://www.codechef.com/download/Solutions/COOK52/Tester/COVERING.cpp">link</a></p>kostya_byMon, 24 Nov 2014 00:08:17 +0530https://discuss.codechef.com/questions/56243/covering-editorialinclusn-exclusnmedium-hardsetseditorialcook52divide-and-conqMANYLIST - Editorialhttps://discuss.codechef.com/questions/75482/manylist-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/PATTMATC">Practice</a> <br>
<a href="http://www.codechef.com/LTIME28/problems/PATTMATC">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/angrybacon">Yanpei Liu</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> </p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Segment tree, sets</p>
<h1>PROBLEM:</h1>
<p><br>
Your task is to maintain a list of sets of integers numbered from $1$ to $N$. All sets are initially empty. You have to handle $M$ operations, each of one of the following two types:</p>
<ol>
<li>$\texttt{INSERT(L, R, X)}$: inserts integer $X$ to all sets numbered from $L$ to $R$</li>
<li>$\texttt{QUERY(Q)}$: outputs the size of the set numbered $Q$</li>
</ol>
<h1>QUICK EXPLANATION:</h1>
<p><br>
For a partial credit, you can pretty easy use the most straightforward approach by just following the process described in the statement. In order to get full credit, for each inserted element $e$, you can use set data structure to store the ranges of sets having $e$. In order to get the number of elements in each set, you can use segment / interval tree to maintain these values.</p>
<h1>EXPLANATION:</h1>
<p><br></p>
<h2>Simple solution</h2>
<p><br>
If $N$ and $M$ are quite small, like in the first two subtasks, where $N, M \leq 1000$, the problem is very easy to solve. </p>
<p>We can store an array $A$ of $N$ sets, where $A[i]$ represents a set numbered $i$. Since all integers, which can be inserted to sets are within the range $[1..N]$, we can store each set as an array, i.e. $A[i][j] = 1$ if and only if integer $j$ is in the set numbered $i$. </p>
<p>In order to handle a single insert operation, we can iterate through sets numbered from $L$ to $R$, and insert the requested $X$ into all of them. This operation takes $O(N)$ time. </p>
<p>Handling a query operation is obvious, we just count the number of $1$'s in the array representation of the requested set. </p>
<p>Since there are $M$ operations to perform, we can achieve $O(N \cdot M)$ time complexity to handle all of them.</p>
<p>The total time complexity of this method is $O(N^2 + N \cdot M)$.</p>
<h2>Faster solution</h2>
<p><br>
However the above method is sufficient for small inputs, we need a better one to get a full credit here.</p>
<p>Rather than storying, for a fixed set, the information what elements are in this set, we can think the other way around.</p>
<p>Let $S[e]$ be the ordered list of <strong>disjoint</strong> ranges of sets having element $e$. For example, if a range $[L, R]$ is in $S[e]$, it means that $e$ belongs to all sets numbered from $L$ to $R$. We say that a range $[A, B]$ is before a range $[C, D$] in our order if and only if $A < C$ or $A = C$ and $B < D$. The disjoint property is very important in the definition, we will use it as the <strong>invariant</strong>. We are going to implement $S[e]$ as a <strong>balanced binary tree</strong> in order to be able to handle insert queries. If you are using for example $\texttt{C++}$ you can use $\texttt{std::set< pair < int, int > >}$ to implement a single $S[e]$.</p>
<p>The second data structure that we are going to use is a segment tree $T$. In this tree, we will store the information on how many elements are in sets numbered from some $L$ to $R$. We will use it to update the number of elements in a range of sets and to get the number of elements in a particular set.</p>
<p>Initially, both structures are empty. This means that $S[e]$ is empty for all valid $e$ and all nodes in $T$ are initialized to have $0$ elements.</p>
<p>Now, we are going to describe, how we handle both operations. We will start with insert, because it exposes the nature of the problem in a great manner.</p>
<h3>Insert operation</h3>
<p><br>
Suppose that we are going to insert element $X$ to all sets numbered from $L$ to $R$. The idea of the solution is to find in $S[X]$ the set $Y$ of all overlaping ranges with $[L, R]$. After inserting $X$ to sets numbered from $L$ to $R$, all sets in a range $Y \bigcup [L, R]$ will have element $X$. What we are going to do, is to replace all ranges from $Y$ in $S[X]$ with a single range representing the just mentioned sum of ranges. </p>
<p>In order to do that, for which range $A \in Y$, we decrease the number of elements in a range $A \bigcap [L, R]$ by one, and delete $A$ from $S[X]$. At the end, we increase the number of elements in $[L, R]$ by one, and we insert the range $Y \bigcup [L, R]$ to $S[X]$. Notice that we maintain the number of elements of sets in a range using our segment tree $T$.</p>
<p>Let's now explain some details on how to implement the logic described above. </p>
<p>In order to get the set $Y$, first we find in $S[X]$ the leftmost range of sets which overlaps with $[L, R]$. Do you remember that we implemented $S[X]$ as a balanced binary tree and that all ranges in that tree are disjoint? Based on these two facts, we can quickly find the leftmost range which overlaps with $[L, R]$, in $\texttt{C++}$ you can use $\texttt{lower\_bound}$ method of $\texttt{std::set}$ to achieve that. After that, we can iterate over all ranges overlapping with $[L, R]$ using $\texttt{successor}$ operation on $S[X]$. </p>
<p>All operations of increasing and decreasing the number of elements in sets of a given range are implemented on segment tree in a standard way.</p>
<p>You may wonder what is the complexity of the insert operation. Well, you can notice that each segment is inserted exactly once and erased at most once. Since a single insert / delete / lower_bound / successor operation on $S[X]$ takes $O(\log(n))$ time and update operation on $T$ also takes $O(\log(N))$ time, a single insert operation has $O(\log(N))$ time complexity.</p>
<h3>Query operation</h3>
<p><br>
Now, the easier operation, we want to know, how many elements are in the set numbered $Q$. Because we maintain our segment tree $T$, we can answer each such query in $O(\log(N))$ time easily by summing up accumulated values at the path form a leaf corresponding to the set $Q$ to the root of $T$.</p>
<h3>Time complexity</h3>
<p>The total time complexity of this solution is $O(N + M \cdot \log(N))$ and this is a very nice speed up over the simple solution.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME28/Setter/PATTMATC.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME28/Tester/PATTMATC.cpp">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>pkacprzakSun, 27 Sep 2015 07:37:13 +0530https://discuss.codechef.com/questions/75482/manylist-editorialsegment-treeltime28hardeditorialsetsHow many subsets have the sum of x?https://discuss.codechef.com/questions/76240/how-many-subsets-have-the-sum-of-x<p>Consider we have a set of n numbers, and we want to calculate the number of subsets in which the addition of all elements equal to x.</p>
<p>Input first line has n, x and the next line contains n numbers of our set. In the output we have to calculate the number of subsets that have total sum of elements equal to x.</p>
<pre><code>INPUT
4 3
-1 2 4 2
OUTPUT
2
</code></pre>melotfiMon, 19 Oct 2015 03:22:44 +0530https://discuss.codechef.com/questions/76240/how-many-subsets-have-the-sum-of-xsortsortingeasysetsPLANEDIV - getting WAhttps://discuss.codechef.com/questions/77795/planediv-getting-wa<p>Hi,</p>
<p>I've submitted the solution for the problem PLANEDIV, but am unable to figure out the problem in my code as it is getting rejected. I've created a set object and have stored all the line coefficients in the set. I've also overloaded the < and > operators of the set, such that if there is a repeated line with different a,b and c, it will not be added to the set. Then I use a map to count the maximum number of lines in the set with the same slope. But still getting wrong answer. Any help would be appreciated.</p>
<p>Here is the link to my solution:<br>
<a href="https://ideone.com/sfoJ0T">https://ideone.com/sfoJ0T</a></p>
<p>Here is a link for the problem statement:<br>
<a href="https://www.codechef.com/problems/PLANEDIV">https://www.codechef.com/problems/PLANEDIV</a></p>
<p>Thanks in Advance</p>pranjvasFri, 18 Dec 2015 00:34:31 +0530https://discuss.codechef.com/questions/77795/planediv-getting-wamaphash-mapc++planedivsetsdec15gcdDeveloping the test caseshttps://discuss.codechef.com/questions/78199/developing-the-test-cases<p>How to derive test cases for problems like <a href="https://www.codechef.com/LTIME31/problems/ABROADS">this</a></p>
<p>Can anyone derive possible test cases for this problem, I am getting wrong answer for its solution, my code is working fine with all the test cases, which I have developed.</p>arpit728Thu, 31 Dec 2015 22:17:34 +0530https://discuss.codechef.com/questions/78199/developing-the-test-casesdisjoint-setabroadsgraphdsusetstest-casesDijkstra's algorithm using STL sethttps://discuss.codechef.com/questions/78215/dijkstras-algorithm-using-stl-set<p><code>void dijkstra(int v){
fill(d,d + n, inf);
d[v] = 0;
int u;
set<pair<int,int> > s;
s.insert({d[v], v});
while(!s.empty()){
u = s.begin() -> second;
s.erase(s.begin());
for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight)
if(d[p.first] > d[u] + p.second){
s.erase({d[p.first], p.first});
d[p.first] = d[u] + p.second;
s.insert({d[p.first], p.first});
}
}
}</code></p>
<p>I managed to implement Dijkstra's algorithm using heaps but it was extremely long, so I decided to try implementing using sets. However, in the above implementation (source: CF), I was unable to understand the part for(auto p: adj[u]) and the stuff in the loop. I haven't manipulated a set of pairs or priority queue of pairs before, I understand this is c++11 usage, but now how it works. Could someone please explain, and if possible, provide an equivalent non c++11 statement?</p>sandy999Fri, 01 Jan 2016 18:42:34 +0530https://discuss.codechef.com/questions/78215/dijkstras-algorithm-using-stl-setstldijkstrasetsPLANEDIV - Editorialhttps://discuss.codechef.com/questions/77627/planediv-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/DEC15/problems/PLANEDIV">Contest</a><br>
<a href="http://www.codechef.com/problems/PLANEDIV">Practice</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/cenadar">Maksym Bevza</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a></p>
<h1>PREREQUISITES:</h1>
<p>Cartesian coordinates, parallel lines, sets, GCD, Euclidean algorithm, sorting</p>
<h1>PROBLEM:</h1>
<p>A set of lines is called <em>perfect</em> if there's no point that belongs to two distinct lines of the set.</p>
<p>Given a set of $N$ lines, each determined by three coefficients $(A,B,C)$ (representing the line $Ax + By + C = 0$), what is the size of the largest perfect subset?</p>
<h1>QUICK EXPLANATION:</h1>
<p>The answer is simply the largest set of distinct lines that are all parallel to one another. To get the answer, group the lines according to slope, being careful to not count coinciding lines twice. (e.g. $x + y + 1 = 0$ coincides with $2x + 2y + 2 = 0$ so should only be counted once.) The answer is the size of the largest group.</p>
<p>One way to group the lines is to add them to a <a href="https://en.wikipedia.org/wiki/Set_(abstract_data_type)">set data structure</a>. Another is to sort them according to slope, so that lines with the same slope are found consecutively. </p>
<h1>EXPLANATION:</h1>
<p>A set containing just one line is clearly perfect, so let's investigate perfect sets of size at least two. Let $a$ and $b$ be two lines in a perfect set. Since $a$ and $b$ must not intersect (and definitely must not coincide), then they must be <a href="https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection">parallel</a>. In other words, they must have the same slope. Since this argument applies to any pair of lines in the perfect set, we can say that a perfect set is just a set of <em>distinct</em> lines all having a common slope. </p>
<p>Our goal now is to find the largest perfect set. Naturally, we want to group the lines according to slope, and take the largest group as the answer. In fact, this is basically the algorithm to solve this problem! However, there are at least two problems that might come up when implementing this: </p>
<ul>
<li>First, we must be able to represent the slope <em>exactly</em>, and not just a floating point number, otherwise you risk getting wrong answer due to bad rounding. (Remember that <a href="https://en.wikipedia.org/wiki/Round-off_error">many numbers cannot be represented exactly in floating point</a>.)</li>
<li>Second, we must be able to detect whether two lines coincide, because we should only count coinciding lines once.</li>
</ul>
<p>We'll deal with these problems one by one. </p>
<h1>Representing the slope</h1>
<p>First, note that it's actually possible to get accepted while using floating point slopes (especially if the data isn't strong enough or the bounds of the problem prevents rounding errors from being a problem), but it's still important to know an error-free way to represent slopes, in other words, a way that can be shown to always work. Also, representing a slope exactly has many applications even outside of this problem. So how do we represent the slope of a line exactly? </p>
<h2>Representation 1</h2>
<p>Well, one way to represent the slope exactly is to simply represent it as an exact fraction. For example, the slope of $Ax + By + C = 0$ is $-A / B$. But we must be able to detect the same fractions! (For example, $1 / 2 = 2 / 4 = 3 / 6$.) One way to do it is to <em>reduce the fraction to lowest terms</em>, by dividing the numerator and denominator by the greatest common divisor (gcd). This works because rational numbers have a unique representation in lowest terms.</p>
<p>We need to represent negative slopes as well! To make the "lowest term representation" unique, simply ensure that the denominator is always positive. Another problem that will arise is how to represent the slope of <em>vertical lines</em>. Their slope can't be represented by a rational number (because it's "infinite"). However, since there is a unique slope for vertical lines, we can simply use a unique object to represent the "vertical slope". (or just handle vertical lines separately)</p>
<h2>Representation 2</h2>
<p>There's actually a way to represent the slopes without needing any special handling for the vertical slope. Instead of representing the <em>slope</em> of the line as a rational number, we represent it as the <em>vector</em> pointing to the direction of the line. Remember that a <em>vector</em> is an ordered pair $\langle x, y \rangle$, which represents the <em>direction</em> pointing from $(0,0)$ towards $(x,y)$. (In a vector, the distance between these points are also important, but since we're only talking about the "direction" of the line, it doesn't matter for our purposes.)</p>
<p>What is the direction vector of the line $Ax + By + C = 0$? Suppose $(x_1,y_1)$ and $(x_2,y_2)$ are points on this line. Then $\langle x_d, y_d \rangle = \langle x_2-x_1, y_2-y_1\rangle$ is one possible direction vector. But these points satisfy the equation of the line, so:
$$Ax_1 + By_1 + C = 0$$
$$Ax_2 + By_2 + C = 0$$
Subtracting these two, we get:
$$A(x_2-x_1) + B(y_2-y_1) = 0$$
or
$$Ax_d + By_d = 0$$
But one solution to this equation is simply $x_d = B$ and $y_d = -A$, thus $\langle B, -A \rangle$ is one direction vector for the line $Ax + By + C = 0$!</p>
<p>But in order to group our lines according to slope, we must again be able to detect vectors representing the same direction. Similarly to rational numbers, we must find some sort of "normal form" that we can reduce our direction vectors to. Note that we also consider opposing vectors as representing the same "direction", e.g. $\langle x, y \rangle$ and $\langle -x, -y \rangle$.</p>
<p>One way to define such a normal form is the following. Let's say a vector $\langle x, y \rangle$ with integer coordinates is in <em>normal form</em> if and only if $x$ and $y$ are <a href="https://en.wikipedia.org/wiki/Coprime_integers">relatively prime</a> and the <a href="http://mathworld.wolfram.com/PolarAngle.html">polar angle</a> of $(x,y)$ is less than 180 degrees. The reader is invited to prove that every direction vector has a unique <em>normal form</em>. </p>
<p>Finally, to convert $\langle x, y \rangle$ to normal form, simply divide both coordinates by $\gcd(x,y)$, and then negate both if $y$ is negative, or $y = 0$ and $x$ is negative.</p>
<p>Using vectors instead of slopes, we don't have to worry about "infinite" slopes any more!</p>
<h1>Detecting coinciding lines</h1>
<p>Next, what about detecting coinciding lines? Note that coinciding lines necessarily have the same slope, so we can simply look at lines with the same slope, and find among those the lines that overlap.</p>
<p>Note that two lines overlap if and only if <em>their equations are the same, up to a nonzero multiplicative constant</em>. For example, the following lines all coincide with one another:<br>
$$4x + 6y + 1 = 0$$
$$8x + 12y + 2 = 0$$
$$44x + 66y + 22 = 0$$
$$-44x - 66y - 22 = 0$$
However, these lines do not coincide with the line $4x + 6y + 2 = 0$ or $4x + 6y - 1 = 0$. </p>
<p>In this case, we can simply try to reduce the equations into some sort of "normal form" (as in the previous section), in such a way that each equation of a line has a unique normal form. Here's one way: Let's say the equation $Ax + By + C = 0$ is in <em>normal form</em> if $A$, $B$ and $C$ are relatively prime, and one of the following conditions hold:</p>
<ul>
<li>$C > 0$</li>
<li>$C = 0$ and $B > 0$</li>
<li>$C = 0$, $B = 0$ and $A > 0$</li>
</ul>
<p>The idea behind this is actually just an extension of our "normal form" of direction vectors in the previous section, because $\langle x, y \rangle$ is in normal form if $x$ and $y$ are relatively prime and one of the following conditions is satisfied:</p>
<ul>
<li>$y > 0$</li>
<li>$y = 0$ and $x > 0$</li>
</ul>
<p>Thus, we can just reduce all our equations to their normal forms, and this way, two lines coincide if and only if their equations are equal!</p>
<h1>Solution</h1>
<p>Armed with the above techniques, the solution is now easy. First, group the lines according to their slopes (or normal forms of their direction vectors). Then, for each group, compute the normal forms of their equations, and remove duplicates. Finally, the answer is simply the largest remaining group!</p>
<p>The following is a Python implementation which solves a single test case:</p>
<pre><code>from fractions import gcd
from collections import defaultdict
s = defaultdict(set)
for i in xrange(input()):
a, b, c = map(int, raw_input().strip().split())
g = gcd(a, b)
h = gcd(g, c)
s[a/g, b/g].add((a/h, b/h, c/h))
print max(map(len, s.values()))
</code></pre>
<p>Since Python's $\text{gcd}(a,b)$ is guaranteed to have the same sign as $b$, dividing by the gcd will already guarantee normality (as we've defined it).</p>
<p>The time complexity of this algorithm is $O(N \log N)$ if one uses balanced tree sets. </p>
<p>Alternatively, you can just sort them according to their normal forms, so parallel lines and coinciding lines are found consecutively. This runs in $O(N \log N)$ time also. </p>
<h1>Time Complexity:</h1>
<p>$O(N \log N)$ or expected $O(N)$ </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="https://www.codechef.com/download/Solutions/DEC15/Setter/PLANEDIV.cpp">Setter</a><br>
<a href="https://www.codechef.com/download/Solutions/DEC15/Tester/PLANEDIV.cpp">Tester</a><br>
<a href="https://www.codechef.com/download/Solutions/DEC15/Editorialist/PLANEDIV.py">Editorialist</a> </p>kevinsogoSat, 12 Dec 2015 23:19:23 +0530https://discuss.codechef.com/questions/77627/planediv-editorialsortinggcdsimpleeuclideaneditorialsetsdec15parallelCODE1602-Editorialhttps://discuss.codechef.com/questions/80356/code1602-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CODE1602">Practice</a><br>
<a href="http://www.codechef.com/COIT2016/problems/CODE1602">Contest</a></p>
<p><strong>Author:</strong>Kamal Verma<br>
<strong>Tester:</strong> Ashish Ahuja <br>
<strong>Editorialist:</strong> Ashish Ahuja</p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://en.wikipedia.org/wiki/Set_theory">Set Theory</a><br></p>
<h1>PROBLEM:</h1>
<p>This is undoubtedly the simplest problem on this planet.</p>
<h1>QUICK EXPLANATION:</h1>
<p>As the name suggests the problem asks one to find out the subsets within a given set through programming.</p>
<h1>EXPLANATION:</h1>
<p>I know what are you thinking, how stupid of someone to make a problem like this. But,it happens.
The problem is focused for absolute newbies in the field of programming. The set theory is the only thing in the world you need to know about to solve this problem. Everything else is cakewalk. Here's a snippet if the code to understand the context well.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://www.codechef.com/viewsolution/9728210">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/viewsolution/9728210">here</a>. </p>se_aashishThu, 24 Mar 2016 16:55:25 +0530https://discuss.codechef.com/questions/80356/code1602-editorialcode1602editorialsubsetscoit2016easysetscakewalkProblem in hackerrank java hashsethttps://discuss.codechef.com/questions/82798/problem-in-hackerrank-java-hashset<p>I tried to solve <a href="https://www.hackerrank.com/challenges/java-hashset/copy-from/22964287">this</a> problem on hackerrank but I am failing some test cases.</p>
<p><a href="http://pastebin.com/5hvAY1gg">My solution</a></p>arpit728Fri, 01 Jul 2016 17:38:59 +0530https://discuss.codechef.com/questions/82798/problem-in-hackerrank-java-hashsetdata-structurejavasetsJava Collections Tutorial Part - 2https://discuss.codechef.com/questions/87027/java-collections-tutorial-part-2<p>In the previous tutorial, we have seen the introduction to JCF and Iterators. In this tutorial,
lets look into the details of Collection Interfaces and Classes.</p>
<p><strong>THE COLLECTION INTERFACES</strong></p>
<p>The Collection Classes implementing these interfaces have the functionality of these
interfaces. Therefore, these interfaces define the core behavior of a Collection class.</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/2.Coll_Inter.png"></p>
<p><strong>THE COLLECTION ABSTRACT CLASSES</strong></p>
<p>The Abstract Classes provide skeletal implementations that are used as starting points for
creating concrete Collections.</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/3.Coll_Abs_Class.png"></p>
<p><strong>THE COLLECTION CLASSES</strong></p>
<p>These standard classes provide full implementation of the Collection that can be used
as-is.</p>
<p>The below table shows various differences between the Collection classes. The terms used
in the table are -</p>
<p><strong>1) AD -</strong> Allow Duplicates: It tells whether that particular collection allows duplicate values
to be inserted.</p>
<p><strong>2) AN -</strong> Allow Null: It tells whether null objects can be inserted into that particular
collection.</p>
<p><strong>3) Inserted Order:</strong> It tells whether the objects are stored in the same order in which they
were inserted.</p>
<p><strong>4) Sorted Order:</strong> It tells whether the objects are stored in sorted order.</p>
<p><strong>5) Synchronized:</strong> It tells whether the collection is thread-safe or not.</p>
<p><strong>6) Random Access:</strong> It tells whether the collection has a get() method to returns the index
of an object or return the object using an index.</p>
<p><strong>7) Default capacity:</strong> The initial capacity of the collection when it is created using an empty
constructor.</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/4.Coll_Classes_3.png"></p>
<p>The Time Complexities of basic operations are given below:</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/11.Coll_Time_1.png"></p>
<p><a href="https://discuss.codechef.com/questions/87026/java-collections-tutorial-part-3">Click here to go to next tutorial</a></p>
<hr>
<p>Java Collections Tutorial Series:</p>
<p><a href="https://discuss.codechef.com/questions/87028/java-collections-tutorial-part-1">Java Collections Tutorial Part - 1</a></p>
<p><a href="https://discuss.codechef.com/questions/87027/java-collections-tutorial-part-2">Java Collections Tutorial Part - 2</a></p>
<p><a href="https://discuss.codechef.com/questions/87026/java-collections-tutorial-part-3">Java Collections Tutorial Part - 3</a></p>
<p><a href="https://discuss.codechef.com/questions/87025/java-collections-tutorial-part-4">Java Collections Tutorial Part - 4</a></p>kay_kaySat, 05 Nov 2016 08:53:59 +0530https://discuss.codechef.com/questions/87027/java-collections-tutorial-part-2javacollectionlinked-listqueuesetstutorialNOTINCOM - Editorialhttps://discuss.codechef.com/questions/90470/notincom-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/NOTINCOM">Practice</a> <br>
<a href="https://www.codechef.com/LTIME44/problems/NOTINCOM">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/errichto">Sergey Kulik </a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/pkacprzak">Kamil Debowski</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/errichto">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p>Basic programming, sets</p>
<h1>PROBLEM:</h1>
<p>The problem can be reformulated as follows: for given two sets of integers $A$ and $B$, the goal is to find the minimum number of elements from $A$, such that after removing these elements from $A$, sets $A$ and $B$ do not have any common elements.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Find the intersection of $A$ and $B$ and return its size.</p>
<h1>EXPLANATION:</h1>
<p>Since all numbers within $A$ are distinct and also all elements within $B$ are distinct, A and B are sets. What we want to do is to remove the minimum number of elements from $A$ in such a way that $A$ and $B$ do not have any common elements. In other words, it means that we want to make their intersection empty, which means that if $C$ is the intersection of $A$ and $B$, we have to remove all elements of $C$, and there is no need to remove any other elements. Thus the problem is reduced to finding the size of the intersection of $A$ and $B$. Depending on the subtask below methods are possible.</p>
<h1>Subtask 1</h1>
<p>In this subtask, we know that each $A$ and $B$ have at most $1000$ elements each and there are at most $25$ test cases to handle. This allows us to iterate over all elements of $A$, and for each one perform a full scan over elements of $B$ to check if the element belongs to both sets. For a single test case this method results in $O(|A| \cdot |B|)$ time complexity.</p>
<h1>Subtask 2</h1>
<p>In the second subtask, $A$ and $B$ can have up to $10^5$ elements, which makes the above approach too slow. However, one can use a hash map to count the number of occurrences of all elements from $A$ and $B$ together. It follows that each element belongs to intersection of $A$ and $B$ if and only if its count is equal to $2$. This approach has $O(|A| + |B|)$ time complexity per single test case. It is worth to mention that since all input elements are positive integers not greater than $10^6$, one can use a simple array instead of a hash map to compute the counters, which results in a similar time complexity and perhaps even easier implementation.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME44/Setter/NOTINCOM.cpp">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME44/Tester/NOTINCOM.cpp">here</a>. </p>pkacprzakMon, 23 Jan 2017 17:05:15 +0530https://discuss.codechef.com/questions/90470/notincom-editorialltime44notincomeditorialsetsbasic-progcakewalkSplitting the set of numbrs into n partitionhttps://discuss.codechef.com/questions/8540/splitting-the-set-of-numbrs-into-n-partition<p>How can we split the set of numbers in n parts. For eg set {1,2,3,4,5,6}, we
have to split it in 3 parts using all the elements for eg valid split could be {123,45,6} , {14,23,56} , {13,245,6} etc.</p>skatercoderSun, 21 Apr 2013 09:19:11 +0530https://discuss.codechef.com/questions/8540/splitting-the-set-of-numbrs-into-n-partitiondynamic-programmingbitmaskingsets[solved] DP - Maximum Weighted Independent Setshttps://discuss.codechef.com/questions/88701/solved-dp-maximum-weighted-independent-sets<p>I am solving a problem in which you are given a tree in the form of a graph and weights at it's each node. You need to find the Maximum Weighted Independent Sets of that tree in which tree root is unknown. However, answer will be independent of the root you take in the tree.
My code with problem description is given here can anybody help me out with my code bug.
<strong>Code is in Java</strong></p>
<p><a href="http://ideone.com/yMoBH2">http://ideone.com/yMoBH2</a></p>
<p>Current Output:
18
Expected Output:
11</p>coderbond007Thu, 08 Dec 2016 13:07:37 +0530https://discuss.codechef.com/questions/88701/solved-dp-maximum-weighted-independent-setsindependentweighteddynamic-programminggraphtreemaximumsetsCLOSESTQ - Editorialhttps://discuss.codechef.com/questions/97031/closestq-editorial<p><a href="https://www.codechef.com/problems/CLOSESTQ">Practice</a> <br>
<a href="https://www.codechef.com/LTIME47/problems/CLOSESTQ">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/gainullinildar">Ildar Gainullin</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/lg5293">Lewin Gan</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<h1>Difficulty:</h1>
<p>Medium-Hard</p>
<h1>Pre-Requisites:</h1>
<p>Set</p>
<h1>Problem Statement</h1>
<p>There is a set of points in 2D, we need to process next queries. Add/erase point in the set of points, and output the square of distance between pair of nearest points. If size of set less than 2, output 0. Initially the set is empty, coordinates of points lies in a range from 1 to 500.</p>
<h1>Subtasks 1 and 2</h1>
<p>Number of queries is less than 2500, we can store all paires squares of distances in set. Adding/erasing point into the set equivalent adding/erasing squares of distance to all points which lies in the set. After that we need to print minimal element in the set. Complexity will be $O(Q^2 log Q)$</p>
<p><code>
points = []
dist = {}
for i=1..Q
c,x,y=read()
if c == '+':
for i in points:
dist.insert(square(points[i], (x,y)))
points.add((x,y))
else:
points.erase((x,y))
for i in points:
dist.erase(square(points[i], (x,y)))
if !dist.empty():
print dist.minElement()
else:
print 0
</code>
</p><h1>Subtask 3</h1>
<p>We can use divide-and-conquer by queries to solve this problem, consider problem only with adding queries. Suppose that we are adding point $(x, y)$ into set and $ans$ is the current minimal square of distance between two points in the set, if set contains less than 2 points, assume $ans = 10^9$. We need to check only those points $(dx, dy)$, which makes new answer less than $ans$. Let's maintain for each $x$ the set of $y$ - coordinates of points which has the same $x$. If we need to update answer for a point $(x, y)$, let's iterate over $dx$, and check two points(if they exists), point $(dx, dy1)$, where $dy1 >= y$ and $(dx, dy2)$, where $dy2 < y$ we can find them in $O(log 500)$ and update the answer. We don't see, if $(dx -x)^2>ans$, because it has no sense to update the answer. When a number of points in the set are more then a couple of thousands, $ans$ won't be big. How to process erase queries? At first, we will solve this problem in offline, i.e initially read all queries and after that process it. At second, for each time of adding a point, let's find nearest time of erasing this point, if this point will be in the set to the end, assume that we erase it in moment of time $Q+1$, after that each point has an interval [L; R], where it is alive(i.e contains in the set). One point can have several intervals. $intervals$ contains all intervals for points. Look at the following code: </p>
<code>
solve(L, R, intervals, ans = 1e9) {
int M = (L + R) / 2
newIntervals = []
for cint in intervals
if cint.end < L OR cint.begin > R //Point which is added in moment of time cint.begin won't be used in queries in a range from L..R, because it erased in the moment of time cint.end
continue
if cint.begin <= L AND cint.end > R //Point will be used for any query in a range L..R, we add it
AddPoint(x[cint.begin], y[cint.begin], newAns) //adding point and recalcuating ans
else: //Otherwise we will process this point somewhere deeper, number of such adding is O(R - L) in array newIntervals
newIntervals.add(cint)
if (L != R) {
solve(L, M, newIntervals, newAns)
solve(M + 1, R, newIntervals, newAns)
} else
res[L] = newAns
rollback() //rollback all changes which were done in this call of function with AddPoint
}
solve(1, Q, 1e9)
</code>
<p>Total complexity of this algorithm is $O(Q * log Q * 500 * log 500)$ but with very small constant. </p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME47/Setter/CLOSESTQ.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME47/Tester/CLOSESTQ.java">here</a></p>
<p><strong>Please feel free to post comments if anything is not clear to you.</strong></p><p></p>mgchSat, 29 Apr 2017 21:15:04 +0530https://discuss.codechef.com/questions/97031/closestq-editorialltime47sqrtdivide-and-conquermedium-hardsetsclosestqWhat is a Set under the account "My Set"https://discuss.codechef.com/questions/97891/what-is-a-set-under-the-account-my-set<p>I have not noticed it so keenly till now, what is a Set under the account "My Set", what is the difference between a Set and a Team.</p>sai_praneethFri, 12 May 2017 16:39:48 +0530https://discuss.codechef.com/questions/97891/what-is-a-set-under-the-account-my-setsetsBITMASK4 - Editorialhttps://discuss.codechef.com/questions/97936/bitmask4-editorial<h1>Problem Link:</h1>
<p><a href="https://www.codechef.com/BITM2017/problems/BITMASK4">Contest</a><br>
<a href="https://www.codechef.com/problems/BITMASK4">Practice</a> </p>
<h1>Difficulty:</h1>
<p>Medium</p>
<h1>Problem:</h1>
<p>We need to find the biggest set of parallel lines from the given lines.
</p><h1>Explanation:</h1>
Equation of line is given by $ ax+by+c=0$ -eq(1). <br>
where <b>a,b,c</b> are coefficients.<br>
And the slope-intercept form of the line is given by $y = mx + C$ -eq(2). <br>
where <b>m</b> is the slope of line and <b>C</b> is the y-intercept.<br>
Comparing eq(1) and eq(2), we get:<br>
$ m = -a/b$ and $C = -c/b$<p></p>
<p>Now for two lines to be parallel, they must have the same slope and different y-intercept. Different y-intercept because if two lines have same slope and y-intercept then both lines are same and they will meet at every point. <br>
So we just need to make different sets of parallel lines according to their slopes and then find the length of the largest set. <br>Also, we need to check for the case where b is 0. To handle the divide by zero exception. In that case, we can assign m to a very large number and C to -c/a.<br>
One way to do this is to use a map of slope and set of lines having that slope. The slope with the largest set of lines will be the required answer.</p>
<h1>Solution:</h1>
<p>Author's solution can be found <a href="https://www.codechef.com/viewsolution/13553743">here</a>.</p>hsagarthegr8Sat, 13 May 2017 19:27:44 +0530https://discuss.codechef.com/questions/97936/bitmask4-editorialgeometrymapmediumbitmask4setsquery related to stl vector and sethttps://discuss.codechef.com/questions/100476/query-related-to-stl-vector-and-set<pre> can we assign a set to each index of vector. if it is possible how can we do implement this?
i did like this :
vector<set<pair<int,int>> > vsp;
for i=1 to n
take set as local variable
set<int,int> s;
insert some values in s;
and assign this set to vector
vsp[i]=s;
but it is giving error.what should i do any help?thanks in advance.
</pre>todumanishSun, 04 Jun 2017 09:10:32 +0530https://discuss.codechef.com/questions/100476/query-related-to-stl-vector-and-setstlvectorsetsKJCP3 - Editorialhttps://discuss.codechef.com/questions/87357/kjcp3-editorial<h1>PROBLEM LINK:</h1>
<p>Take Turns</p>
<p><a href="https://www.codechef.com/problems/KJCP3">Practice</a><br>
<a href="https://www.codechef.com/KCPR2016/problems/KJCP3">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/vedipen">Dipen Ved</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/vedipen">Dipen Ved</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/nir21">Nirali</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY </p>
<h1>PREREQUISITES:</h1>
<p>Use of <a href="https://en.wikipedia.org/wiki/Iterator">iterators</a> and <a href="https://en.wikipedia.org/wiki/Associative_containers">sets</a></p>
<h1>PROBLEM:</h1>
<p>Given two lists, you have to sort them and print them alternatively starting with list one.</p>
<h1>QUICK EXPLANATION:</h1>
<p>The input is taken using two 'sets' and two 'for loops' for two lists. Take two iterators, each pointing to the beginning of the respective sets. Using a for loop, alternatively print the numbers the two iterators are pointing to.</p>
<h1>EXPLANATION:</h1>
<p>Let's first consider solving the problem for a single test case. We are given two lists. We have to take the input using set so that they are already sorted and we don't have to write a separate code again for sorting the list. So, using for loop and insert function - </p>
<pre><code>for(int i=0;i<n;i++) {
int temp;
scanf("%d",&temp);
set1.insert(temp);
}
</code></pre>
<p>Here, n is the size of the list and temp is the number in the list
Similarly, for the second list.
Now, we wish to print the elements of the lists alternatively starting with list one. So let's put an iterator to point to the beginning to set2.</p>
<pre><code>set<int>::iterator it2 = set2.begin();
</code></pre>
<p>We also want an iterator pointing to the start of set1, which we will do in the for loop.</p>
<pre><code>for(set <int>::iterator it1 = set1.begin();it1!=set1.end() && it2!=set2.end();it1++,it2++) {
cout<<*it1<<" "<<*it2<<" ";
}
</code></pre>
<p>The for loop will run till both the iterators reach the end of their respective sets and alternatively both sets will be printed.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Solution can be found <a href="http://www.ideone.com/X5Q4mL">here</a> </p>vedipenFri, 11 Nov 2016 18:08:23 +0530https://discuss.codechef.com/questions/87357/kjcp3-editorialmapkcpr2016stlkjcp3iterationssetsCHEFD - Editorialhttps://discuss.codechef.com/questions/51848/chefd-editorial<h1>Problem link:</h1>
<p><a href="http://www.codechef.com/LTIME16/problems/CHEFD">contest</a><br>
<a href="http://www.codechef.com/problems/CHEFD">practice</a> </p>
<h1>Difficulty :</h1>
<p>Medium </p>
<h1>Pre-requisites :</h1>
<p>Binary Indexed Tree or Sets in C++[Balanced Binary Search Trees]</p>
<h1>Problem:</h1>
<p>You are given an array of N integers. You have to make M queries. Each query has one of the two types: </p>
<ul>
<li>(1, l, r, p) - choose all numbers with indexes between l to r. Divide all numbers by p, that are divisible by p. </li>
<li>(2, l, d) - assign l-th number in array to d </li>
</ul>
<p>Also p is in [ 2 3 5] </p>
<h1>Explanation</h1>
<p>Let us assume that we have a data structure which can give us the next number divisible by p in the range [l r] in O(t) time, t is what we will find out later. </p>
<p>Can you give an estimate of total amortised cost on the total time complexity using the above data structure ? </p>
<p>If we forget that there is any query of type 2, then what will be the total amortised cost ?
As each number is less than 10<sup>9</sup>, in the worst case a number can be divided by p by at most 30 times (when p is 2 and number is 10<sup>9</sup>).
So total time complexity would be O(t) * 30 * N</p>
<p>Now Let us add queries of type 2.
Each number which is replaced will require at most 30 steps to reach 1. So at most M numbers are added.
So total time complexity is O(t) * 30 * (M + N) + Time required to change the data structure for query 2.</p>
<p>Now, if t = O(log N), then we are done. </p>
<h1>The Data Structure</h1>
<p>We will make 3 balanced binary search trees [ one for p = 2, other for p=3 and the last one for p=5 ].
Balanced Binary search trees to keep numbers in the sorted is implemented in C++ as <a href="http://www.cplusplus.com/reference/set/set/">"set"</a> and in Java as HashSet or TreeSet.</p>
<p>In our set , we will keep index of the numbers which are divisible by p.</p>
<p>Let us solve for p = 2, rest primes are analogous to this case.</p>
<p><strong>Query of First Type</strong> : l r p <br>
Find in the balanced binary search tree [i.e. set ] for index which is just greater than or equal to l and less than or equal to r. Divide the number on that index with p.
If after division it is no longer divisible by p then remove that index from the binary search tree and proceed to find another index which is greater than this index and less than or equal to r. We will continue this again and again till it terminates.</p>
<p><strong>Query of Second Type</strong> : l d <br>
We first remove index l from all 3 set if it is present in them.
Then we'll add index l in the set if d is divisible by p.</p>
<p><strong>Pseudo Code</strong><br>
<code>
//Declaring the Data Structure
set<int> myset<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">6</a><br>
//Building the Data Structure
for(int i=1;i<=N;i++)
Read( arr[i] )
if( arr[i]%2 == 0 ) myset[ 2 ].insert(i);
if( arr[i]%3 == 0 ) myset[ 3 ].insert(i);
if(arr[i]%5 == 0 ) myset[ 5 ].insert(i);<br>
//Report Query
scanf("%d%d%d",&l,&r,&p); //taking the input.
a = lower_bound(myset[p].begin(),myset[p].end(),l);//finding the first index
vector<int> del; //to store the index which are needed to be deleted
for(set<int>::iterator it = a;it!=myset[p].end();it++) //iterating the set from the found index
if( <em>it > r) break; //breaking the loop when you encounter index greater than r
arr[</em>it]/=p; //dividing the number by p
if ( arr[<em>it] %p )
del.push_back(</em>it); //if number is no more divisible by p, then we need to remove this from the set
for(vector<int>::iterator it = del.begin();it!=del.end();it++)
myset[p].erase(*it); //deleting the numbers<br><br>
//Update Query
scanf("%d%d",&l,&d);
//Delete them if already in set.
if( arr[l] %2 == 0 ) myset[ 2 ].erase(l);
if( arr[l] %3 == 0 ) myset[ 3 ].erase(l);
if( arr[l] %5 == 0 ) myset[ 5 ].erase(l);
//Add them
if ( d%2 == 0 ) myset[ 2 ].insert(l);
if ( d%3 == 0 ) myset[ 3 ].insert(l);
if ( d%5 == 0 ) myset[ 5 ].insert(l);
arr[l] = d;
</code></p>
<h1>Other Data Structure</h1>
<p>We can use Binary Indexed trees to solve this problem.
We will make 3 binary indexed trees[p=2 ,3 and 5] of size N . We will keep 1 at index i if number in that index is divisible by p.</p>
<p><strong>Updating in Binary Indexed Tree</strong> <br>
If a[l] is divisible by p=2 , then we will add -1 in Binary Indexed tree for p=2.
If d is divisible by 2 , we will add +1 in Binary Indexed tree for p=2.
We will do it similarly for other Binary Indexed Tree.</p>
<p><strong>Reporting in Binary Indexed Tree</strong> <br>
We will find the sum of the values stored till l-1 for Binary Indexed tree of p.
We will find the index of the next value which is just greater than the sum found. We will divide that index of the array by p. We will update our sum to this new sum. We will continue to do this till our index just exceeds r. We will keep track of the numbers which are no more divisible by p. We will add -1 there at the end.</p>
<p>Thus Overall time complexity of querying from both the structure is O(log N)</p>
<h1>Subtask</h1>
<p><strong>subtask 1</strong>: <br>
Brute Force algorithm will pass.</p>
<p><strong>Subtask 2</strong>: <br>
Find for all index , number of times it is divided by p= [2 3 5] .<br>
How can this be done ? </p>
<p>Maintain 3 arrays for the counter and as soon as a Divide query comes for prime p, you can simply do Add 1 at position l and -1 to Position r+1 in array made for prime p.<br>
After all queries, find prefix sum of all 3 arrays. </p>
<p>This will give you the power of p which is proposed to be divided for each index. </p>
<h1>Some Important Links to Read</h1>
<p><a href="http://www.cplusplus.com/reference/set/set/">Sets in Cplusplus</a>
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">Binary Indexed Tree in Topcoder</a><br>
<a href="http://bitdevu.blogspot.in/">Binary Indexed Tree in Editorialist's blog</a> </p>
<h1>Setter and Tester Solutions:</h1>
<p><a href="http://www.codechef.com/download/Solutions/LTIME16/Setter/CHEFD.cpp">setter</a><br>
<a href="http://www.codechef.com/download/Solutions/LTIME16/Tester/CHEFD.cpp">tester</a> </p>devuy11Sun, 28 Sep 2014 14:01:23 +0530https://discuss.codechef.com/questions/51848/chefd-editorialbitmediumltime16editorialsetscan set of pairs can be created?https://discuss.codechef.com/questions/105872/can-set-of-pairs-can-be-created<p>eg-:set<pair<char,char>></p>rsbjgjWed, 19 Jul 2017 11:20:18 +0530https://discuss.codechef.com/questions/105872/can-set-of-pairs-can-be-createdstlsetsany container that stores duplicate elements in a sorted manner ?https://discuss.codechef.com/questions/113149/any-container-that-stores-duplicate-elements-in-a-sorted-manner<p>can anyone suggest me a container that stores duplicate elements ? set does that , but it does not stores duplicates.</p>pawan_asipuMon, 02 Oct 2017 14:22:49 +0530https://discuss.codechef.com/questions/113149/any-container-that-stores-duplicate-elements-in-a-sorted-mannerhelpsetsNeed help in set.https://discuss.codechef.com/questions/122148/need-help-in-set<p>Given a set of pairs. Each pair represent a range of numbers. </p>
<p>Example : (5, 8) represents {5, 6, 7, 8}.</p>
<p>I want to find in which pair an element x is present, it is sure that element x exits in at least one pair?</p>
<p>Can this be solved in logarithmic time? Thanks in advance!</p>chef_keshavSun, 28 Jan 2018 05:02:04 +0530https://discuss.codechef.com/questions/122148/need-help-in-setpairhelpsets