hiddentesla's blog

By hiddentesla, history, 8 years ago, In English

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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).


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

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)