113B: Petr#

  • find all S(begin) and S(ends)
  • for each i..j, calculate its rolling hash, add it to the corresponding map hash -> (start, end), if i is in S(begin), and j is in S(end)
  • for each entry in the map, add the size of the entry - # of duplicates to the final answer

633C: Spy Syndrome 2

  • reverse the whole sentence
  • caluclate the rolling hash of each word in the dictionary
  • DP on the suffix size. The overall run time will be O(n), because for each check, we reduce the overall problem size by 1,because we search for the FIRST matching one

965C: Greedy Arkady

  • bsearch on the times A gets, note that D is no more than 1000, we can brute force on all possible Ds, and find the max possible factor A gets
  • k * D * x >= n, K * (D - 1) * x <= n - x, also, x <= M
  • The target function is D * x

448D: Multiplication Table

  • bsearch on answer, at least iteration we can afford an O(n) iteration, i.e., just calculate through all rows to see if number < the target number matches, also keep track of equal coutns