September Challenge 2018

BSHUFFLE

I don't know why this is correct.
https://ideone.com/p8tq79

TABGAME

View the win-loss table diagonally and alternately. You can realize that the values almost unchange except for the both ends. So you can compute the all of values sequentially and compute the answer at an appropriate time.
https://ideone.com/uXVcpK

ANDSQR

Let's list the continuous subsequences such that the right end is R. Actually, the number of distinct values is at most 30. That is why for each adjacent values x and y, x is a proper subset of y, so at least one bit is lost.
https://ideone.com/H1eQ6R

PHOTOCOM

This is an implementation problem (I supposed).
https://ideone.com/bO9TAR

STCFOTT

My simple O(NQ) dp solution pass the all test cases. It is no wonder. 5 seconds should be enough. The key property is similar to Ant (introduced in Antbook). By this property, each ants is not necessary to be distinguished. After that, only have to do is to compute the expectation at each positions. It is achieved by standard Markov-Chain like DP.
https://ideone.com/HnoH73

FCTR

I have seen a similar problem. So I didn't feel it difficult. My solution is a little dirty. Given information about the order of the group (it's equivalent to Euler's phi), you can use Euler's theorem. It states that any element of the group raised to the power of the order of group is always equal to 1. Considering analogy of Miller-Rabin method, you can find x such that x^2=1 (mod N) and x is neither 1 or -1 with high probability, but skip the details here. If x is neither 1 nor -1, x-1 is a nontrivial divisor, so this problem is reduced to N/(x-1). Repeating this procedure, finally you can factor N. You might notice that if N is not square-free, this algorithm doesn't work properly, but this can be resolved by reducing to N to N/gcd(N,phi(N)).
https://ideone.com/YVWRnq

CHEFLST

My solution is perfectly wrong but luckily passed all test cases.
https://ideone.com/81Pi48

CHEFZERO

Is there any approximation algorithm?
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://pekempey.hatenablog.com/entry/2018/09/17/185923", "fetch_time": 1555852491000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-18/segments/1555578531462.21/warc/CC-MAIN-20190421120136-20190421142136-00263.warc.gz", "warc_record_offset": 510357224, "warc_record_length": 8670, "token_count": 522, "char_count": 2028, "score": 3.59375, "int_score": 4, "crawl": "CC-MAIN-2019-18", "snapshot_type": "latest", "language": "en", "language_score": 0.9363062381744385, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00020-of-00064.parquet"}