Questions Tagged With bitshttps://discuss.codechef.com/tags/bits/?type=rssquestions tagged <span class="tag">bits</span>enWed, 07 Nov 2018 13:54:14 +0530The Game of Chess(CDWRS05) (CodeWars 2013 - By BITS, Pilani )https://discuss.codechef.com/questions/25603/the-game-of-chesscdwrs05-codewars-2013-by-bits-pilani<p>The link to this question is <a href="http://www.codechef.com/CODW2013/problems/CDWRS05">here</a></p>
<p>The link to my solution is <a href="http://www.codechef.com/viewsolution/2741480">here</a></p>
<p>anyone help me where my logic is wrong </p>maheshwar44Wed, 02 Oct 2013 20:11:00 +0530https://discuss.codechef.com/questions/25603/the-game-of-chesscdwrs05-codewars-2013-by-bits-pilani-codewarspilanibitsby2013counting set bits in a 32 bit numberhttps://discuss.codechef.com/questions/46066/counting-set-bits-in-a-32-bit-number<pre><code> int NumberOfSetBits32(int i) {
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
return (i*(0x01010101))>>24; }
</code></pre>
<p>Can someone explain this code ,which finds the number of set bits in a number . I am completely unable to understand it. </p>bhanu1993Sun, 29 Jun 2014 12:37:13 +0530https://discuss.codechef.com/questions/46066/counting-set-bits-in-a-32-bit-numbercount32bitbitsBITS PILANI CODE VOYAGEhttps://discuss.codechef.com/questions/59675/bits-pilani-code-voyage<p>could I please have the <br><strong>Bits Pilani Aarohan Code Voyage registration link</strong><br>
have been searching for ages<br>but cant find...PLEASE HELP
<br>
SHIVANSH</p>betu1123581321Tue, 23 Dec 2014 21:39:08 +0530https://discuss.codechef.com/questions/59675/bits-pilani-code-voyagereg.pilanibitslinkcode voyagehttps://discuss.codechef.com/questions/60718/code-voyage<p>what to do after registering on code voyage site and can you please send the link</p>naman401Sun, 04 Jan 2015 16:02:12 +0530https://discuss.codechef.com/questions/60718/code-voyagebitsNew to manipulationhttps://discuss.codechef.com/questions/64253/new-to-manipulation<p>hello everyone i am fairly new to bits.I was trying to solve 2 questions..<a href="http://www.codechef.com/problems/AND">1st one</a> and <a href="http://www.spoj.com/problems/XMAX/">2nd one</a> i was able to fetch the 1st one with 52 points but i have no idea to get 100pts and i am facing difficulty with its editorial and not even getting the second question.can anybody tell me how to get comfortable with these type of questions as i have seen many many times in the <a href="http://contests.Is">contests.Is</a> this called bits masking??If yes can anybody help me to understand these concepts.. :) :)</p>doodle90Wed, 11 Feb 2015 12:24:49 +0530https://discuss.codechef.com/questions/64253/new-to-manipulationbitsmanipulationBits concept , How to Crackhttps://discuss.codechef.com/questions/64324/bits-concept-how-to-crack<p>Problem link : <a href="http://www.codechef.com/CDSU2015/problems/MHTPAIR">http://www.codechef.com/CDSU2015/problems/MHTPAIR</a></p>
<p>Everyone solving this problem with bits concept , I know lots of things about bits but didn't applied it in any problem.
So How to apply it in this problem Can anybody explain??</p>n1n1_4Thu, 12 Feb 2015 17:18:16 +0530https://discuss.codechef.com/questions/64324/bits-concept-how-to-crackdoubtbitsBit Maskinghttps://discuss.codechef.com/questions/65809/bit-masking<p>what are some best documents for understanding bit masking and some easy practice problems for learning it</p>placiboTue, 10 Mar 2015 17:52:02 +0530https://discuss.codechef.com/questions/65809/bit-maskingbitsSPIT2-Editorialhttps://discuss.codechef.com/questions/68253/spit2-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/SPIT2">Practice</a> <br>
<a href="http://www.codechef.com/SPT2015/problems/SPIT2">Contest</a> <br></p>
<p>Author : <a href="http://www.codechef.com/users/ankit15">Ankit Sagwekar</a><br>
Tester : <a href="http://www.codechef.com/users/ankit15">Vikesh Tiwari</a><br>
Editorialist : <a href="http://www.codechef.com/users/ankit15">Ankit Sagwekar</a></p>
<h1>DIFFICULTY</h1>
<p>Easy
<br></p>
<h1>PREREQUISITES</h1>
<p>basics,array,implementation</p>
<h1>PROBLEM</h1>
<p>Given two integers 'm' and 'n'. Find the number of combinations of bit-size 'n' in which there are no 'm' consecutive '1'.
</p>
<h1>EXPLANATION</h1>
<p>We are given with m and n. There are 3 cases for any given value of n and m</p>
<ul>
<li>
<p>Case 1:
when n is less than m
for this the ans will be equal to ans=pow(2,n).<br>
eg: 3 2
all the 2 bit words i.e 00 01 10 11 will not have 3 consecutive 1 ,thus all of them are selected.</p>
</li>
<li>
<p>Case 2: when n is equal to m
for this the ans will be equal to ans=pow(2,n)-1.<br>
eg: 3 3
all the 3 bit words i.e 000 001 010 011 100 101 110 111 out of which only one word will have 3 consecutive '1'.</p>
</li>
<li>
<p>Case 3: when n is more than m
This test case needs some computation which we will see through eg.<br>
eg:
3 4<br>
Here we first calculate for <br>
m n <br>
3 3 = 7 <br>
3 2 = 4 <br>
3 1 = 2 <br>
then adding this ,we get for 3 4 as 7+4+2=13. <br>
here m=3 thus we calculate for 3 values and add them . <br>
eg:4 6 <br>
here we first calculate for <br>
m n <br>
4 5 = 29 <br>
4 4 = 15 <br>
4 3 = 8 <br>
4 2 = 4 <br>
then adding this ,we get for 4 6 as 29+15+8+4=56. <br>
here m=4 thus we calculated for 4 values and add them . <br></p>
</li>
</ul>
<p>Note: for faster computation we can precompute all the values and can store them in 2-D matrix. </p>
<h1>
Complexity: </h1>
<p>(O(N^2.logN))</p>
<h1>C++ Code </h1>
<pre><code>#include <stdio.h>
#include<math.h>
int main(void) {
// your code goes here
long long int t,n,m,i,j,k,a[15][105],l;
scanf("%lld",&t);
for(i=2;i<=10;i++)
for(j=1;j<=50;j++)
{
if(j<i)
a[i][j]=pow(2,j);
else if(j==i)
a[i][j]=pow(2,j)-1;
else
{
k=i;
l=j-1;
while(k>0)
{ k--;
a[i][j]+=a[i][l--];
}
}
}
/*
for(i=2;i<=10;i++)
{
for(j=1;j<=50;j++)
{
printf("%lld\t",a[i][j]);
}
printf("\n");
}
*/
// you can uncomment the above section to see all the precomputed values
while(t--)
{
scanf("%lld%lld",&m,&n);
printf("%lld\n",a[m][n]);
}
return 0;
}
</code></pre>vicky002Thu, 23 Apr 2015 07:21:24 +0530https://discuss.codechef.com/questions/68253/spit2-editorialimplementationbitseasycounting set bitshttps://discuss.codechef.com/questions/71407/counting-set-bits<pre>int NumberOfSetBits32(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = ((i + (i >> 4)) & 0x0F0F0F0F);
return (i*(0x01010101))>>24;
}
unable to understand the above code snipplet.Any one please help.
</pre>pallesaiFri, 12 Jun 2015 08:32:59 +0530https://discuss.codechef.com/questions/71407/counting-set-bitsbitsFFCOMB - Editorialhttps://discuss.codechef.com/questions/86772/ffcomb-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/FFCOMB">Practice</a><br>
<a href="https://www.codechef.com/LTIME41/problems/FFCOMB">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic programming, bits</p>
<h1>PROBLEM:</h1>
<p>There are $N$ meals to buy numbered from $1$ to $N$. The $i$-th meal can be bought separately for price $C_i$. Meals can also be bought in sets. There are $M$ sets and each set consists of some meals. The prices of the $i$-th set is $P_i$. The goal is to buy all $N$ meals for the lowest possible price. In one test file there are multiple test cases to handle.</p>
<h1>QUICK EXPLANATION:</h1>
<p>The main idea is to use dynamic programming and bitmasks to compute $dp[mask]$ as the smallest possible cost of buying elements set in the $mask$.</p>
<h1>EXPLANATION:</h1>
<p>In subtasks $1$ and $2$ methods based on computing the exactly value of $dp_1$ defined in the explanation for subtask 3 below might be used. In particular let $dp[mask]$ be the lowest price to buy meals in $mask$. Then one possible idea for lower constrains is to iterate for all possible masks and for each single one, iterate over all possible seats of meals and try to lower the cost of meals covered by the current mask and the set of meals by combining their costs.</p>
<h1>Subtask 3</h1>
<p>First of all, notice that buying all meals is always possible, because they all can be bought separately. However, the price can be reduced by buying the meals in sets.</p>
<p>Let $dp_1[mask_1]$ be the smallest price for buying meals in $mask_1$ using a single purchase - so using either a single purchase of a separated meal or a single purchase of a set of meals</p>
<p>Let $dp_2[mask_2]$ be the smallest price for buying meals in $mask_2$ using any purchases.</p>
<p>Clearly, $dp_2[mask_2]$ for $mask_2$ containing $N$ ones is the final answer.</p>
<p>At the beginning, we can set values of $dp_1$ and $dp_2$ to some extremely large values in order to simplify the implementation.</p>
<p>The first step towards the solution is to compute $dp_1$ values for all possible $2^N$ masks. Later we are going to use these values to compute values in $dp_2$.</p>
<p>Let $mask_{separete, i}$ be the mask corresponding the meal $i$. Moreover, let $mask_{set, i}$ be the mask corresponding to the $i$-th set of meals. Initially, we set:</p>
<p>$dp_1[mask_{separete,i}] = C_i$ for all $i = 1, 2, \ldots, N$. </p>
<p>Then, we set:</p>
<p>$dp_1[mask_{set, i}] = \min(dp_1[mask_{set, i}], P_i)$ for $i = 1, 2, \ldots, M$.</p>
<p>Since buying a set of $B$ meals might be the cheapest way to buy a set of $A$ meals for $A < B$, then we are going to try to lower these costs as follows:</p>
<pre><code>for (int mask = (1 << n) - 1; mask >= 0; —mask) {
for (int j = 0; j < n; ++j) {
if (mask & (1 << j)) {
dp_1[mask ^ (1 << j)] = min(dp_1[mask ^ (1 << j)], dp_1[mask]);
}
}
}
</code></pre>
<p>The thing to notice there is that we iterate from the masks containing the most meals to the masks containing less meals in order to try to reduce their prices. Notice that $\texttt{mask ^ (1 << j)}$ is the $mask$ with the $j$-th bit set to $0$.</p>
<p>After than, we are ready to compute the values of $dp_2$. The idea is very simple, for a given $mask$ we are going to iterate over all submasks of $mask$ and ty to add a single meal to them to expand it to $mask$:</p>
<pre><code>dp_2[0] = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
int submask = (mask - 1) & mask;
while (submask > 0) {
dp_2[mask] = min(dp_2[mask], dp_2[submask] + dp_1[mask ^ submask])
submask = (submask - 1) & mask;
}
}
</code></pre>
<p>The above method has time complexity $O(2^N \cdot N + 3^N)$, where the first part is the complexity of calculating $dp_1$ values and the second part is the complexity of calculating $dp_2$ values. While the complexity of the first part is quite obvious, the complexity of the second part needs an explanation. For each mask, we iterate over all its submasks. We know that there are $\binom{N}{k}$ masks with $k$ ones and each such mask has $2^{N-k}$ submasks. Thus the number of iterations during computation of $dp_2$ can be measure as $\sum\limits_{k=0}^N \binom{N}{k} \cdot 2^{N-k} = 3^N$.</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/LTIME41/Setter/FFCOMB.cpp">here</a>.<br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME41/Tester/FFCOMB.cpp">here</a>.</p>pkacprzakSat, 29 Oct 2016 23:01:13 +0530https://discuss.codechef.com/questions/86772/ffcomb-editorialdynamic-programmingbitsltime41editorialHow to find the number of set bits in large numbers ?https://discuss.codechef.com/questions/93216/how-to-find-the-number-of-set-bits-in-large-numbers<p>By 'Large', I mean numbers containing up to 10^4 digits.<br> I have tried doing it by converting the number to binary, digit by digit (representing numbers as a vector of bits), so I multiply the current result by 10 and add the next digit, which I have done by adding two numbers, left shifted 3 times and 1 time(because N*10 = N<<3 + N<<1) and then wrote a function that adds two binary numbers represented this way, and then add the next digit. But its too slow.</p>hemanth_1Tue, 14 Mar 2017 18:56:11 +0530https://discuss.codechef.com/questions/93216/how-to-find-the-number-of-set-bits-in-large-numbersbinarybignumbersbitsbig_numbersSolution for PRATABHI (LOC Jun '17)https://discuss.codechef.com/questions/104044/solution-for-pratabhi-loc-jun-17<p>What's the approach to solve the problem <a href="http://www.codechef.com/LOCJUN17/problems/PRATABHI">PRATABHI</a>?</p>avi224Tue, 04 Jul 2017 00:14:33 +0530https://discuss.codechef.com/questions/104044/solution-for-pratabhi-loc-jun-17locbitslocjun17Problem in solving this problem based on bits and array?https://discuss.codechef.com/questions/107766/problem-in-solving-this-problem-based-on-bits-and-array<p>I tried to solved <a href="https://www.hackerearth.com/challenge/hiring/peoplestrong-java-hiring-challenge/algorithm/killjee-and-easy-problem-ef205c19/description/">THIS PROBLEM</a> on hackerearth, but I am getting wrong answer.<a href="https://pastebin.com/kSE2jh5n">This</a> is link to my code please help me in finding what's wrong with my approach.</p>arpit728Sat, 05 Aug 2017 17:54:38 +0530https://discuss.codechef.com/questions/107766/problem-in-solving-this-problem-based-on-bits-and-arraymoduloalgorithmexponentiationhackerearthoptimizationwrong-answerbitsHow to Find first set bithttps://discuss.codechef.com/questions/121689/how-to-find-first-set-bit<p>Find first set bit
Given an integer an N, write a program to print the position of first set bit found from right side in the binary representation of the number.</p>
<p>I/P 18, Binary Representation 010010</p>
<p>O/P 2</p>
<p>I/P 19, Binary Representation 010011</p>
<p>O/P 1</p>
<p>Can anyone explain with the help of an example</p>pandey_96Sat, 20 Jan 2018 09:07:03 +0530https://discuss.codechef.com/questions/121689/how-to-find-first-set-bitbitsCPH003B-Editorialhttps://discuss.codechef.com/questions/122023/cph003b-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CPH003B">Practice</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kmalhotra30">Karan Malhotra</a></p>
<p><strong>Tester</strong> <a href="http://www.codechef.com/users/dushsingh1995">Dushyant Singh</a> , <a href="http://www.codechef.com/users/sonu_628">Deepansh Parmani</a></p>
<p><strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kmalhotra30">Karan Malhotra</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p>Math,Bits</p>
<h1>PROBLEM:</h1>
<p>The problem basically asks to print the minimum count of positive integers , such that the sum of each (integer raised to the power 2) results in the given number <strong>N</strong></p>
<h1>QUICK EXPLANATION:</h1>
<p>The answer is the number of set bits in <strong>N</strong></p>
<h1>EXPLANATION:</h1>
<p>Every Natural Number can be represented as a sum of distinct powers of 2.Each set bit represents a distinct power.For eg - 5 (101) = 2^0 + 2^2 , the 0th and 2nd bit are set from left and the distinct powers are 1(2^0) & 4(2^2).</p>
<p>Many languages have built in functions to count the number of set bits.Other solutions also exist which involve manipulation of bits.Check solution for the same.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://ideone.com/wzpQIx">here</a>.</p>kmalhotra30Thu, 25 Jan 2018 00:08:28 +0530https://discuss.codechef.com/questions/122023/cph003b-editorialmanipaluniversityjaipurcodephreniacp132018editorialbitsmathBits fractional parthttps://discuss.codechef.com/questions/122841/bits-fractional-part<p>The n - bit fixed point representation of an unsigned real number x uses f bits for the fraction part . Let i= n- f. The range of decimal values for x in this representation is?</p>phantomhiveTue, 13 Feb 2018 09:28:23 +0530https://discuss.codechef.com/questions/122841/bits-fractional-partbitsMaximize OR of subset of arrayhttps://discuss.codechef.com/questions/130197/maximize-or-of-subset-of-array<p>We are given an array of length N. We have to find the minimum length subset( not subarray) of array with maximum OR value. <br>
N bound till 10^5. Ai<=10^6</p>
<p>Only one example was given:
Array elements are 1,2,3,4,5</p>
<p>possible max OR is 7. Minimum length subset are (5,2) and (3,4)</p>vbt_95Thu, 21 Jun 2018 18:06:02 +0530https://discuss.codechef.com/questions/130197/maximize-or-of-subset-of-arraybitsNeed Help in a questionhttps://discuss.codechef.com/questions/131206/need-help-in-a-question<p>Given Q queries, with each query consisting of two integers L and R, the task is to find the total numbers between L and R (Both inclusive), having atmost two set bits in their binary representation. </p>
<p>Q<=10^5
L,R<=10^18</p>
<p>Question link: <a href="https://practice.geeksforgeeks.org/problems/the-range-query/0">https://practice.geeksforgeeks.org/problems/the-range-query/0</a></p>sagar_samWed, 11 Jul 2018 12:22:23 +0530https://discuss.codechef.com/questions/131206/need-help-in-a-questionbitschef and strange additionhttps://discuss.codechef.com/questions/137974/chef-and-strange-addition<p>problem-<a href="https://www.codechef.com/SNCK1A19/problems/CHEFADD">link text</a></p>
<p>logic- I converted A and B in binary form and stored it in array A[] and B[] respectively.</p>
<p>-> traverse array A[] for every A[i] is set and B[i] is reset mark pos as i do following step</p>
<ul>
<li>
<p>loop starting index to pos if A[j] is 0 && B[j] is 1 </p>
<pre><code> count++;
</code></pre>
</li>
</ul>
<p>display count.</p>
<p>What im doing is increasing the value of A by factor x, and if its possible to decrease B by same factor- overall sum is not going to change.</p>
<p>Why im getting WA what im missing.</p>
<p>Thanks</p>code_manSun, 21 Oct 2018 15:36:33 +0530https://discuss.codechef.com/questions/137974/chef-and-strange-additionsnackdownabitseasyconstraintshttps://discuss.codechef.com/questions/139747/constraints<p>can anyone please theses constraints </p>
<p>Constraints
1≤T≤104
1≤N≤1,600</p>
<p>these are constraints from the bittobyte question</p>codu_cid96Wed, 07 Nov 2018 13:54:14 +0530https://discuss.codechef.com/questions/139747/constraintstobytebitsEditorial for question "bits please" asked in cow by MNIT (JAIPUR).https://discuss.codechef.com/questions/135842/editorial-for-question-bits-please-asked-in-cow-by-mnit-jaipur<p>Please provide the solution for the question "Bits Please" asked in COW conducted by MNIT(JAIPUR).</p>
<p><a href="https://www.codechef.com/COW2018/problems/BP">https://www.codechef.com/COW2018/problems/BP</a></p>
<p>Thanks in advance.</p>ankool88Sun, 23 Sep 2018 11:36:58 +0530https://discuss.codechef.com/questions/135842/editorial-for-question-bits-please-asked-in-cow-by-mnit-jaipurbinary-numbersbitslowest set bithttps://discuss.codechef.com/questions/111310/lowest-set-bit<p>why does n&!(n-1) for n=6 gives 0 in C++ and 2 in python . it should give 2 though .</p>junior_gTue, 12 Sep 2017 22:42:15 +0530https://discuss.codechef.com/questions/111310/lowest-set-bitbitsc++python3