Questions asked by lakhhttps://discuss.codechef.com/questions/asked-by/140798/lakh/?type=rssQuestions asked by <a href="/users/140798/lakh" >lakh</a>enTue, 04 Sep 2018 19:20:38 +0530Help Needed in array based problemhttps://discuss.codechef.com/questions/126886/help-needed-in-array-based-problem<p>Given T testcases each testcase consists of an array A[] of length N. Now for each array we have to count the no. of subarrays such that sum of elements of the subarray is divisible by each individual element of the subarray.</p>
<p>Here 1<=T<=100 , 1<=N<=2000 and A[i]<=10^9.</p>
<p>My approach: I am computing the sum and LCM of each subarray and then checking if sum of subarray is divisible by LCM with time complexity of O(T<em>N^2</em>log(n)) but getting TLE. Here log(n) comes from the gcd() function required for computing LCM.Please suggest some optimizations or some other approach for this problem. Thanks in advance.</p>lakhThu, 17 May 2018 18:24:28 +0530https://discuss.codechef.com/questions/126886/help-needed-in-array-based-problemarraylcmHelp needed in LCM range query problemhttps://discuss.codechef.com/questions/126968/help-needed-in-lcm-range-query-problem<p>Given an array A of N (N<=2*10^4) elements and Q(Q<=10^6) queries. Each array element A[i]<=60. </p>
<blockquote>
<p>In each query you are given a number K (K<=N). Compute LCM for all subarrays of size K and report the smallest value of LCM found.
Please suggest some approach for this problem.</p>
</blockquote>lakhFri, 18 May 2018 23:06:03 +0530https://discuss.codechef.com/questions/126968/help-needed-in-lcm-range-query-problemarraylcmqueriesCount pairs in array whose XOR is less than Khttps://discuss.codechef.com/questions/127072/count-pairs-in-array-whose-xor-is-less-than-k<p>Given an array of N elements how to count all pairs whose XOR is less than equal to K??</p>lakhSun, 20 May 2018 10:21:07 +0530https://discuss.codechef.com/questions/127072/count-pairs-in-array-whose-xor-is-less-than-karrayxorMinimize the sum of absolute difference of adjacent array elementshttps://discuss.codechef.com/questions/127440/minimize-the-sum-of-absolute-difference-of-adjacent-array-elements<p>Given an array A of N (N<=10^6) elements , you can choose any subarray and invert the sign of all elements lying in that subarray i.e positive elements are changed to negative and vice versa. </p>
<p>You have to apply this operation exactly once. Determine the minimum possible sum of absolute difference of adjacent array elements that can be obtained after applying the operation exactly once. -10^9<=A[i]<=10^9.</p>
<p>Link to problem: <a href="http://codeforces.com/gym/101522/problem/I">http://codeforces.com/gym/101522/problem/I</a> </p>
<p>Please suggest how to approach this problem.</p>lakhWed, 23 May 2018 22:18:59 +0530https://discuss.codechef.com/questions/127440/minimize-the-sum-of-absolute-difference-of-adjacent-array-elementsarraySQRT DECOMPOSITION problems on treeshttps://discuss.codechef.com/questions/127974/sqrt-decomposition-problems-on-trees<p>I am looking for some problems involving the concept of sqrt decomposition on trees but not able to figure them out.Please suggest some problems involving trees that requires sqrt decomposition technique. </p>lakhTue, 29 May 2018 11:30:42 +0530https://discuss.codechef.com/questions/127974/sqrt-decomposition-problems-on-treessqrt-decomptreeNeed help In a segment tree problemhttps://discuss.codechef.com/questions/128086/need-help-in-a-segment-tree-problem<p>Given an array of N(N<=10^5) elements and -10^9<=A[i]<=10^9. Q(Q<=10^5) queries are there of two types:</p>
<ol>
<li>L R K: Add K to all numbers in range [L,R] in array.</li>
<li>L R: Find no. of positive elements>0 in range [L,R].</li>
</ol>
<p>I Thought of segment tree with lazy propagation but not able to understand what info to be stored in each node. Please suggest some approach for this problem. <a href="/users/313176/freeloop">@freeloop</a> </p>lakhWed, 30 May 2018 19:34:21 +0530https://discuss.codechef.com/questions/128086/need-help-in-a-segment-tree-problemsegmentarraytreequerieshow to generate random numbers without using rand() function?https://discuss.codechef.com/questions/134876/how-to-generate-random-numbers-without-using-rand-function<p>I wanted to know if there is some way of generating pseudo random integers without using rand() function giving lesser number of collisions.</p>lakhTue, 04 Sep 2018 19:20:38 +0530https://discuss.codechef.com/questions/134876/how-to-generate-random-numbers-without-using-rand-functionrandom