ezdp's blog

By ezdp, history, 4 months ago, In English

According to this link testcases for nearly all AtCoder problems are posted in a dropbox, however files from ABC336 to ABC342 aren't available. Are they not going to be published or are they uploaded somewhere else? Files for AGC and ARC are updated regularly.

Full text and comments »

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

By ezdp, history, 4 years ago, In English

[Problem]: 1200E - Compress Words [Solution]: 74203908

I'm getting a TLE on test 3. I'm using hashing to answer queries "Is string A equal to string B?" in O(1) time with O(N) preprocessing time. I'm doing N queries at worst so my time complexity should be O(N + N) = O(N).

As I'm just learning hashing I was using this solution(58603158) to check if I'm doing the right things. The only difference in the two solution should be(I might have overlooked something, if that's the case I'm sorry) that I'm using two-dimensional arrays to save the two hashes per prefix, where the other solution is using vectors. The other difference is that instead of using modular multiplicative inverse to "divide" the hash of the substring I'm querying for and "drag" it such that there are 0 empty spaces before it, I'm multiplying so that I "push" the substring to the end so that there are MAXN(1e6 + 5 in my code) empty spaces.

Let's say in string "abcdefg", I'm querying for substring from index 4 to 6 (0-indexex): 1) I will subtract the hash of prefix "abcd" from prefix "abcdefg". The result will be "____efg"(_ is a empty space, 0 value); 2) Instead of "dragging" the substring I'm querying for so that I get the hash for "efg", I multiply it so that I get MAXN(1e6 + 5 in my code) empty spaces "_" and "efg" at the end.

I hope that made my idea more clear.

Thanks in advance for the help!

UPD1: I and a friend of mine tried some optimizations and found that the f() function was not working properly(it returned the same values for 'X' and 'x') but I still get TLE on test 3.

Full text and comments »

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