night.watchman's blog

Weird issue with "String Hashing"
By night.watchman, history, 7 months ago, In English

Recently after solving this problem with Polynomial Hashing. I got TLE.

I thought my solution would be AC well within 2000 ms. I changed the vector size from 1600 to 1e4 [Even Increased]. But then the problem got AC.

See these two submissions (TLE) VS Accepted. [99.9999999% same]

Can anybody share the reason? Have you faced these type of things?

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

»
7 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

347255084

lucky AC lol

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I suspect this is due the constants of the set DS (your code could insert more than $$${10}^6$$$ elements). After cleanup of the mod template and replacing set with sorting, it passed easily: 347525212.

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I think you got AC just by luck, the time limit is tight. Here's my two submissions:

TLE: 337732539

AC: 337732965

I optimized the code by using vector instead of set lol :v

→ Reply