Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I'm sorry for misunderstood this problem last time, so I edit it and now I can promise the correction and you can test the code first, the complexity is <code>O(n^2)</code>, the detail answer is follow</p> <hr> <p>First, we can equal the problem to the next one</p> <p>We are looking for <code>kth largest</code> number (k is limited by <code>10^9</code>) which has following properties:</p> <ul> <li>Amount of <code>1's</code> is equal to amount of <code>0's</code> what can be described as following: <code>#(1) = #(0)</code></li> <li>Every prefix of this number has to contain at least as much [[<code>1's</code> as <code>0's</code>]], which means: There is no prefix which would contain more [[<code>0's</code> than <code>1's</code>]].</li> </ul> <p>Let's give an example to explain it: let <code>n=3</code> and <code>k=4</code>, the amount of satisfied numbers is <code>5</code>, and the picture below has explain what we should determine in previous problem and new problem:</p> <pre><code>| 000111 ------&gt; 111000 ^ | 001011 ------&gt; 110100 | | 001101 ------&gt; 110010 | | previous 4th number 010011 ------&gt; 101100 new 4th largest number | v 010101 ------&gt; 101010 | </code></pre> <p>so after we solve the new problem, we just need to bitwise not.</p> <p>Now the main problem is how to solve the new problem. First, let A be the array, so <code>A[m]{1&lt;=m&lt;=2n}</code> only can be 1 or 0, let <code>DP[v][q]</code> be the amount of numbers which satisfy condition2 and condition #(1)=q in <code>{A[2n-v+1]~A[2n]}</code>, so the <code>DP[2n][n]</code> is the amount of satisfied numbers. </p> <p><code>A[1]</code> only can be 1 or 0, if <code>A[1]=1</code>, the amount of numbers is <code>DP[2n-1][n-1]</code>, if <code>A[1]=0</code>, the amount of numbers is <code>DP[2n-1][n]</code>, now we want to find the <code>kth largest</code> number, if <code>k&lt;=DP[2n-1][n-1]</code>, <code>kth largest</code> number's <code>A[1]</code> must be 1, then we can judge <code>A[2]</code> with <code>DP[2n-2][n-2]</code>; if <code>k&gt;DP[2n-1][n-1]</code>, <code>kth largest</code> number's <code>A[1]</code> must be 0 and <code>k=k-DP[2n-1][n-1]</code>, then we can judge <code>A[2]</code> with <code>DP[2n-2][n-1]</code>. So with the same theory, we can judge <code>A[j]</code> one by one until there is no number to compare. Now we can give a example to understand <code>(n=3, k=4)</code></p> <p>(We use <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow">dynamic programming</a> to determine DP matrix, the DP equation is <strong><em>DP[v][q]=DP[v-1][q-1]+DP[v-1][q]</em></strong>)</p> <pre><code> Intention: we need the number in leftest row can be compared, so we add a row on DP's left row, but it's not include by DP matrix in the row, all the number is 1. the number include by bracket are initialized by ourselves the theory of initialize just follow the mean of DP matrix DP matrix = (1) (0) (0) (0) 4&lt;=DP[5][2]=5 --&gt; A[1]=1 (1) (1) (0) (0) 4&gt;DP[4][1]=3 --&gt; A[2]=0, k=4-3=1 (1) (2) (0) (0) 1&lt;=DP[3][1]=3 --&gt; A[3]=1 (1) (3) 2 (0) 1&lt;=1 --&gt; a[4]=1 (1) (4) 5 (0) no number to compare, A[5]~A[6]=0 (1) (5) 9 5 so the number is 101100 </code></pre> <p>If you have not understand clearly, you can use the code to understand</p> <p><strong><em>Intention</em></strong>：<code>DP[2n][n]</code> increase very fast, so the code can only work when <code>n&lt;=19</code>, in the problem <code>n&lt;1000</code>, so you can use big number programming, and the code can be optimize by bit operation, so the code is just a reference</p> <pre><code>/*-------------------------------------------------- Environment: X86 Ubuntu GCC Author: Cong Yu Blog: aimager.com Mail: funcemail@gmail.com Build_Date: Mon Dec 16 21:52:49 CST 2013 Function: --------------------------------------------------*/ #include &lt;stdio.h&gt; int DP[2000][1000]; // kth is the result int kth[1000]; void Oper(int n, int k){ int i,j,h; // temp is the compare number // jishu is the int temp,jishu=0; // initialize for(i=1;i&lt;=2*n;i++) DP[i-1][0]=i-1; for(j=2;j&lt;=n;j++) for(i=1;i&lt;=2*j-1;i++) DP[i-1][j-1]=0; for(i=1;i&lt;=2*n;i++) kth[i-1]=0; // operate DP matrix with dynamic programming for(j=2;j&lt;=n;j++) for(i=2*j;i&lt;=2*n;i++) DP[i-1][j-1]=DP[i-2][j-2]+DP[i-2][j-1]; // the main thought if(k&gt;DP[2*n-1][n-1]) printf("nothing\n"); else{ i=2*n; j=n; for(;j&gt;=1;i--,jishu++){ if(j==1) temp=1; else temp=DP[i-2][j-2]; if(k&lt;=temp){ kth[jishu]=1; j--; } else{ kth[jishu]=0; if(j==1) k-=1; else k-=DP[i-2][j-2]; } } for(i=1;i&lt;=2*n;i++){ kth[i-1]=1-kth[i-1]; printf("%d",kth[i-1]); } printf("\n"); } } int main(){ int n,k; scanf("%d",&amp;n); scanf("%d",&amp;k); Oper(n,k); return 0; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm for finding kth binary number with certain properties
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAImager
    1. USAImager
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUndeletion
    1. COPrint all `kth` number? There is always only one. As input I have given `n` which is bits number times two and `k` which tells me what number we looking for as output we have to write one line containing the number (as binary).
      singulars
      1. PO
      1. USabc
    2. CO@Kostek: I have change my answer, you can have a look
      singulars
      1. PO
      1. USAImager
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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