suvankar123's blog

By suvankar123, history, 5 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

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, # |
  Vote: I like it +4 Vote: I do not like it

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.

Hint
Solution
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to do better i mean the to solve the problem without brute-force approach?