Блог пользователя hiddentesla

Автор hiddentesla, история, 8 лет назад, По-английски

the problem: http://jollybeeoj.com/problem/view/255

i tried all i can, but i can only think of preprocessing and save it in a string, then output the questions in O(1), but sadly, i cant because its memory limit exceeded, is there a math based approach?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can you solve it if all squares have the same number of digits?

In the general case in which squares may have a different number of digits, group them by their number of digits, and use the previous algorithm for each group.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Suppose all the squares have the same number of digits. For example, let's say 2 digits.

The numbers that have 2-digit squares are in the interval [4, 9].

Now, given a query q, you can easily see where the digit q belongs, because there are 6 squares with 2-digits each (12 digits).

16|25|36|49|64|81

Find the block (or bucket) where q falls into with a simple division.

You can use this strategy in the general case, just keep track of all the intervals that contain 1-digit squares, 2-digit squares, 3-digit squares, 4-digit squares ... etc

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

thanks for the help guys!, im guessing you have to precompute the frequency of every digit number, so thats what i did, i tried running the precomputation algo in my machine, it took about 2,5 seconds to generate, so i got worried and run it offline, then just hardcode it into the program, and got AC 1 ms :D

but, because im curious, i just use the precomputation algo on the start of the program, and submit it again, and i got AC ~400 ms ._., so i guess my machine is just really slow :(

for the future, here is how i solve the problem: https://ideone.com/S3OBbq (commented out lines is the wy i precompute)