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.

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | apiadu | 3397 |

4 | TLE | 3374 |

5 | Um_nik | 3358 |

6 | 300iq | 3317 |

7 | maroonrk | 3232 |

8 | Benq | 3230 |

9 | LHiC | 3229 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 191 |

2 | Errichto | 186 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 169 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 163 |

9 | 300iq | 155 |

10 | Petr | 153 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/02/2020 16:46:54 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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$$$.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,

Solution$$$ k <= O \implies $$$ Print the $$$k$$$ th odd number.

$$$ k > O \implies $$$ Print the $$$(k-O)$$$ th even number.

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