codechef September short

Carvans	CARVANS	1093	39
Coal Scam	COALSCAM	138	24.35
Prime Permutations	PPERM	155	19.58
Pizza Tossing	PTOSS	12	14.81
Recipe Reconstruction	RRECIPE	769	35.21

Carvans: keep track of the slowest car before you.

Coal Scam: Two phase of Kruskal's, the key is to prove that ties can be broken arbitrarily. For implementation, since M is only 20000, even the O(n) union-find implementation will work. For quick union-find, either union by size or union by rank is fast. I had another terrible mistake for not noticing nodes are given as 0 to N-1, while I thought it was 1 to N. This caused id[0] not to get reinitialized between testcases.

Prime Permutation: To count, notice that after you placed 1 to N-1, inserting N to anywhere does not affect whether the first N-1 numbers are in a valid position or not, since their rank does not change. So you only need to place N at 1 or a prime position. My mistake is only calculate cnt[] to 5000000-1, and got a WA.

Recipe Reconstruction: since it has to be palindrome, you can match char by char from both ends. The tricky part is that 10000000+9 = 23 * 434783 which is NOT a prime. So you need Chinese Remainder's Theorem (CRT) to calculate the mod.

Side note: to verify my solution after seeing editorial for PPerm, I wrote a bash for loop to write 1 to 5000000 to a file. This takes about 6m30s. Running the c++ code read in the file and do all the calculations and write to another file takes less than 2s.