### suvankar123's blog

By suvankar123, history, 5 weeks ago, ,

hello everyone! I am eagerly waiting for any suggestion regarding a error raised while solving a problem here it is https://codeforces.com/contest/318/submission/71941739 .Any sort of advice is preferred.

• -16

 » 5 weeks ago, # | ← Rev. 4 →   +16 The input data for test case 8 is $n = 10^{12}$ and $k =5\times 10^{11}+1$. On the other hand, the memory limit of the problem is 256 megabytes. As each 32-bit integer requires 4 bytes of memory storage, the maximum size of an integer array is 64 mega items (roughly $64\times 10^{6}$ numbers), which is insuffient to create an array of integers with $10^{12}$ items. For 64-bit integers, the maximum array size is roughly $32\times 10^{6}$. Try to find an algorithm for computing the $k_{th}$ item in the array indirectly without generating all the $n$ items. Hint: Suppose that $n$ can be expresed as $n = 2 q+r$, where both $q$ and $r$ are integers, $q \geq 0$ and $0 \leq r \leq 1$. Then, there are exactly $q+r$ odd numbers and $q$ even numbers in all integers from 1 to $n$.
 » 5 weeks ago, # |   +4 The problem with your approach is that, you are allowed only $256$ MB memory. In the worst case test, where $n = 10^{12}$, you will make an array of $10^{12}$ integers. One integer requires $4$ bytes, which means, you will be using $4*10^{12}$ bytes, i.e. $4*10^6$ MB. This gives you Memory Limit Exceeded.You are doing what the problem is saying exactly, which is usually called a Naive solution. But, you must do better. There is a way to solve the problem, without actually constructing the array. HintLet $O$ be the total number of odd numbers between $1$ to $n$. Consider two cases, $k <= O$ $k > O$ Solution $k <= O \implies$ Print the $k$ th odd number. $k > O \implies$ Print the $(k-O)$ th even number.
•  » » 5 weeks ago, # ^ |   0 how to do better i mean the to solve the problem without brute-force approach?