Problem statement: https://www.codechef.com/RC122020/problems/RECNDNUM
My solution: https://www.codechef.com/viewsolution/32359646
To understand the solution, you need to know the size of each, let’s say ‘chunk’
Chunk 1 = 0 1: Size = 2 Chunk 2 = 0 1 2 1: Size = 4 Chunk 3 = 0 1 2 3 2 1: Size = 6 ...
Now, solving for:
N * N
The first time N occurs is during the time N*N. Here’s why:
A number N will first occur in the Nth chunk at the Nth index.
The index will be 2 + 4 + 6 + ... (for N-1 times) + N(we need to add the index as well)
Let’s distribute N to all the N-1 numbers.
Then, it’ll be 3 + 5 + 7 + ... (for N-1 times) + 1 since we have a leftover.
Now, the sum is 1 + 3 + 5 + ... (for N times).
The sum of the first N odd numbers = N*N
Floor(K/2) * 2*N
Notice the differences between the last index of any number in a chunk and the first index of the same element in the next chunk. It’s always 2*Number. And that will occur Floor(K/2) times when finding the Kth occurrence.
So, we have to add Floor(K/2)*2*N.
Ceil(K/2) * Ceil(K/2-1)
Note: We have to remove Floor(K/2) from K (since it was taken care of above), which would be Ceil(K/2).
We only have to add the differences of the first index of an element and the last index of an element in each chunks. Notice that the differences start at
0 and increase by 2 for every chunk after it. Therefore, the sum will be:
0 + 2 + 4 + 6 ... for Ceil(K/2) times
That is equal to Ceil(K/2) * Ceil(K/2-1)
And therefore, we get the formula N*N + Floor(K/2) * 2 * N + Ceil(K/2) * Ceil(K/2-1)
The only exception if for
0, in which case you have to print K*(K-1)
Hope you understood my editorial!
Also, do rate this post, since it’s my first time writing an editorial
And feel free to ask any doubts or give me any suggestion!