StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMy FB HackerCup code too slow of large inputs
text
Body
copied!<p>I was solving the <a href="https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420" rel="nofollow noreferrer"><code>Find the min</code></a> problem on facebook hackercup using python, my code works fine for sample inputs but for large inputs(10^9) it is taking hours to complete.</p> <p>So, is it possible that the solution of that problem can't be computed within 6 minutes using python? Or may be my approaches are too bad?</p> <p><strong>Problem statement</strong>:</p> <p>After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, <code>m</code>, which contains <code>n</code> non-negative integers. However, only the first <code>k</code> values of the array are known to him, and he wants to figure out the rest.</p> <p>John knows the following: for each index <code>i</code>, where <code>k <= i < n</code>, <code>m[i]</code> is the minimum non-negative integer which is <em>not</em> contained in the previous <code>*k*</code> values of <code>m</code>.</p> <p>For example, if <code>k = 3</code>, <code>n = 4</code> and the known values of <code>m</code> are <code>[2, 3, 0]</code>, he can figure out that <code>m[3] = 1</code>.</p> <p>John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.</p> <p>Given the first <code>k</code> values of <code>m</code>, calculate the nth value of this array. (i.e. <code>m[n - 1]</code>).</p> <p>Because the values of <code>n</code> and <code>k</code> can be very large, we use a pseudo-random number generator to calculate the first <code>k</code> values of <code>m</code>. Given positive integers <code>a</code>, <code>b</code>, <code>c</code> and <code>r</code>, the known values of <code>m</code> can be calculated as follows:</p> <pre><code>m[0] = a m[i] = (b * m[i - 1] + c) % r, 0 < i < k </code></pre> <p>Input</p> <ul> <li><p>The first line contains an integer T (T <= 20), the number of test cases.</p></li> <li><p>This is followed by T test cases, consisting of 2 lines each.</p></li> <li><p>The first line of each test case contains 2 space separated integers, <code>n</code>, <code>k</code> (<code>1 <= k <= 10^5</code>, <code>k < n <= 10^9</code>).</p></li> <li><p>The second line of each test case contains 4 space separated integers <code>a</code>, <code>b</code>, <code>c</code>, <code>r</code> (0 <= a, b, c <= 10^9, 1 <= r <= 10^9).</p></li> </ul> <p>I tried two approaches but both failed to return results in 6 minutes, Here's my two approaches:</p> <p>first:</p> <pre><code>import sys cases=sys.stdin.readlines() def func(line1,line2): n,k=map(int,line1.split()) a,b,c,r =map(int,line2.split()) m=[None]*n #initialize the list m[0]=a for i in xrange(1,k): #set the first k values using the formula m[i]= (b * m[i - 1] + c) % r #print m for j in range(0,n-k): #now set the value of m[k], m[k+1],.. upto m[n-1] temp=set(m[j:k+j]) # create a set from the K values relative to current index i=-1 #start at 0, lowest +ve integer while True: i+=1 if i not in temp: #if that +ve integer is not present in temp m[k+j]=i break return m[-1] for ind,case in enumerate(xrange(1,len(cases),2)): ans=func(cases[case],cases[case+1]) print "Case #{0}: {1}".format(ind+1,ans) </code></pre> <p>Second:</p> <pre><code>import sys cases=sys.stdin.readlines() def func(line1,line2): n,k=map(int,line1.split()) a,b,c,r =map(int,line2.split()) m=[None]*n #initialize m[0]=a for i in xrange(1,k): #same as above m[i]= (b * m[i - 1] + c) % r #instead of generating a set in each iteration , I used a # dictionary this time. #Now, if the count of an item is 0 then it #means the item is not present in the previous K items #and can be added as the min value temp={} for x in m[0:k]: temp[x]=temp.get(x,0)+1 i=-1 while True: i+=1 if i not in temp: m[k]=i #set the value of m[k] break for j in range(1,n-k): #now set the values of m[k+1] to m[n-1] i=-1 temp[m[j-1]] -= 1 #decrement it's value, as it is now out of K items temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1 # new item added to the current K-1 items while True: i+=1 if i not in temp or temp[i]==0: #if i not found in dict or it's val is 0 m[k+j]=i break return m[-1] for ind,case in enumerate(xrange(1,len(cases),2)): ans=func(cases[case],cases[case+1]) print "Case #{0}: {1}".format(ind+1,ans) </code></pre> <p>The last for-loop in second approach can also be written as :</p> <pre><code>for j in range(1,n-k): i=-1 temp[m[j-1]] -= 1 if temp[m[j-1]]==0: temp.pop(m[j-1]) #same as above but pop the key this time temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1 while True: i+=1 if i not in temp: m[k+j]=i break </code></pre> <p>sample input :</p> <pre><code>5 97 39 34 37 656 97 186 75 68 16 539 186 137 49 48 17 461 137 98 59 6 30 524 98 46 18 7 11 9 46 </code></pre> <p>output:</p> <pre><code>Case #1: 8 Case #2: 38 Case #3: 41 Case #4: 40 Case #5: 12 </code></pre> <p>I already tried <a href="https://codereview.stackexchange.com/questions/20926/how-can-i-improve-the-performance-of-this-code">codereview</a>, but no one replied there yet.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload