I see the some submission for this problem lot of people did this problem with binary search
and some of them did with direct formula but i am not getting any ,could you guys help me to approach or idea to solve this problem , actually problem seems like easy
prob : CodeChef: Practical coding for everyone
I observed the pattern for the first few terms of the sequence.
A=1,1,2,2,2,3,3,3,3,4,4,4,4,4...
It is evident that any number i occurs i+1 times in the series and hence it is the invariant property of the sequence. So let us assume that the Nth term of the sequence is k and then the following arguments follow:
\underbrace{1,1}_\text{2},\underbrace{2,2,2}_\text{3}, \underbrace{3,3,3,3}_\text{4},\underbrace{4,4,4,4,4}_\text{5}...\underbrace{(k-1),(k-1),..(k-1)}_\text{k},\underbrace{k,k...k}_\text{c}
where 1 \le c \le k+1
\implies 2+3+4+5+....+k +c = N
\implies c =N-2-3-4-....-k
Now we have to find the biggest k which satisfies this condition
Also since c \ge1
\implies N-2-3-4-...-k \ge1
\implies 2+3+4+5+...+k+(1-1)\le N-1
\implies \frac{k(k+1)}{2}-1\le N-1
\implies k^2+k-2N \le0
Using the quadratic formula
\implies k\le \frac{-1+\sqrt{(1+8N)}}{2}
since we’re interested in the maximum integral value of k
\therefore k =\lfloor \frac{-1+\sqrt{(1+8N)}}{2} \rfloor
1 Like
now i understand we can apply binary search also to find the biggest k because the sequence in monotonic increasing , but i am not getting the where from sequence came,can you explain that?
,and thank you very much @cubefreak777
You can check their explanation, they’ve explained how it comes out to be this. I just solved it for small cases and observed the pattern.