You can tell me better

The strategy didn't work. They still only have 9025 people registered. Only 27 people have registered in the last 5 minutes.

atulyakv

Not that it changes much but that formula has a nice graphic interpretation as following:

Suppose you build a binary heap with number 1, 2, ..., N ( A binary tree with node u having 2*u and 2*u + 1 as it's childs ). Then the occurrence of v is

1. Subtree size of v if v is odd, and

2. Sum of subtree size of v and v + 1 if v is even.

If you don't mind can you elaborate that checking for k occurence part(I understood the bin search),say n=11 and k=3,how to find if number 5 has 3 occurences?

Well, I use a weird method: We first calculate the path of n and store it in one list, then for every even number x in path(n), add x-2 to another list. And a weird but true statement is that the answer will only occur in the two lists. Since the size is O(log n) and checking can be done in O(log n), This solution is O(log^2 n)

Assume that $$$x$$$ lies on the path of $$$A$$$. Then

$ (it can be easily seen by trying to invert the function $$$f$$$). By using induction, we get that

$ If $$$x$$$ is odd, then $$$a_1 \gt 0$$$, else $$$a_1 \geq 0.$$$ Let's say

$ Then, obviously, if $$$x$$$ is odd and greater than $$$1$$$, $$$x$$$ lies on the path of every number of the form $$$2^a \cdot x + y$$$, for $$$0 \leq y \leq 2^a - 1$$$, and if $$$x$$$ is even, then $$$x$$$ lies on the path of every number of the form $$$2^a \cdot x + y$$$, for $$$0 \leq y \leq 2^{a+1} - 1$$$. Now, let's fix $$$a$$$ (the power of two) and count the number of numbers of such form. For odd $$$x$$$ there are $$$2^a$$$ such numbers and for even $$$x$$$ there are $$$2^{a+1}$$$ such numbers. Assume that $$$A$$$ is the largest number of such form that is not greater than $$$n$$$ ($$$n \geq A = 2^a \cdot x + y$$$). Then if $$$x$$$ is odd, then x is contained in the following number of different paths:

$ and if $$$x$$$ is even, then $$$x$$$ is contained in the following number of paths:

$ We also know that $$$n \geq 2^a \cdot x + y$$$. Intuitively, we want to maximize $$$x$$$, so we have to minimize the number of paths that contain $$$x$$$, so we have to make it the least possible value that is not less than $$$k$$$. One can easily see that for odd $$$x$$$ we can make $$$2^a + y = k$$$, and for even x we can make $$$2^{a+1} + y - 1 = k$$$ and the values of $$$a$$$ and $$$y$$$ will be uniquely determined. Thus, $$$x$$$ will be the largest number of respective parity that is not greater than $$$(n - y) / 2^a$$$ (from the maximality of $$$A = 2^a \cdot x + y$$$). Now, how to compute the answer: let $$$a = [log_2(k)]$$$. For odd $$$x$$$ we let $$$y = k - 2^a,$$$ then $$$x = (n - y)/2^a$$$ (if $$$x$$$ will be even, decrease $$$x$$$ by one). For even $$$x$$$, if $$$k \lt 2^{a+2} - 1$$$, then $$$a := a-1$$$; let $$$y = k - 2^{a+1} + 1$$$, then $$$x = (n - y)/2^a$$$ (if x will be odd, decrease $$$x$$$ by one).

I didn't submit because what I wrote wasn't working correctly.

Basically, I wanted to calculate f(x) = number of elements in whose path, x came. so, dp[x] = dp[2x] + dp[x+1] + 1 if x is even

else if x is odd, dp[x] = 1 + dp[2x]

but this function was taking a huge amount of time AND memory, hence I tried to compute the same thing, which this function is doing, but used digit dp my digit dp compared two numbers n and x and output in how many ways can I add digits to the right of x to make its length = length of n and still maintain x<=n. Actually, the number of numbers, in whose path x comes will just be the number of ways we can append 1 or 0 to the right of x such that len(x)<=len(n) && x<=n so the len(x) = len(n) part was handled by the digit dp and when len(x)<len(n) we could use combinatorics

The new function I made was working properly, i.e. giving the same answer as my time and memory expensive f(x).

So, now I thought of binary search on x and I got stuck, because I noticed that f(x) values when x is even is about double when x is odd, hence a constantly increasing, monotonic search space wasn't what I was getting...

So, I got stuck, basically its not giving the correct answer at the 1000000 100 test case.

So, thats why I didn't submit. My wrong submission for clarity

If you can compute the function $$$g(x)$$$ which denotes the number of integers up to $$$n$$$ that start with the binary representation of $$$x$$$, then $$$f(x) = g(x)$$$ for odd $$$x$$$ and $$$f(x) + f(x+1)$$$ for even $$$x$$$ by "retracing" the steps of $$$f$$$.

$$$g$$$ is easily computed, you can look at my submission for example.

First consider how many B's (suppose m) and W's (suppose n) are in the given string. Secondly, observe that doing any operation, either the number of B's become m-2 and number of W's become n+2 or the other way round. Another possibility is the number of B's and W's will not change. This happens when you swap B W -> W B. Thus, we can conclude that either the number of B must be even or the number of W must be even or both.

After that, i just iterate through the string and swap accordingly. I declare another variable to count the swap and put the index into an array. Hopefully it helps.

Math is hard.

What I meant is either y ends with 1 and is a prefix of x or ends with 0 and either y or y + 1 is a prefix of x.