TechJam 2018, Grand Final, Code Squad (Coding)

Abridged Problem Statement for
TechJam Thailand 2018, Grand Final, Code Squad

Round 2 - Coding
Time: 3 hours 30 minutes
Penalty is calculated as (the time you obtain your maximum score) + 10*(number of wrong submissions on AC'd problems)

==============================

Problem A - Intercept Meteor (Max. 20 pts)

Given a list of N points on 2D plane. These form a convex polygon in clockwise order, starting from the leftmost point (pick bottom point if there are multiple leftmost points). Given K queries, each query is denoted by (x,y). Answer whether (x,y) is "Inside," "Outside," or "On the boundary."

-10^9 <= x,y <= 10^9
No three points are colinear.
Small (8 pts): 3 <= N <= 1000, 1 <= K <= 1000
Large (12 pts): 3 <= N <= 100000, 1 <= K <= 100000
Time limit: 1 second, Memory limit: 128 MiB

==============================

Problem B - Finding Peep Chan (Max. 20 pts)

Given an N x M grid. Initially, there's a cat inside one of these cells. In a day, the cat can move up/down/left/right one block or use one of the K shortcuts linking between cell (x1,y1) and cell (x2,y2), if it's standing on one of the endpoints. You don't know where the cat is. The cat may be in any cell with equal probability (1/NM for each block). You can use one of the two operations
1) Query (x,y) - You will know the length of the shortest path from cell (x,y) to the cat's cell.
2) Help (x,y) - If the cat is at (x,y), your mission is completed. If it's not, nothing happens.
This is your procedure for helping the cat, in order:
1) Use Query once on some point to get a hint of the cat's position.
2) If you can guarantee the cat's position, use Help immediately then end the process.
3) If not, wait until the next day. The cat will move exactly once while you wait.
4) Use Query once again (you can use a different point) to get another hint.
5) Use Help immediately (even if you can't guarantee the cat's position, you can still try to maximize your chance.)
Find the maximum probability you could save the cat if you follow the procedure and pick optimal (x,y) points for querying.

Small (8 pts): 1 <= N, M <= 20, NM <= 200, 1 <= K <= 100
Large (12 pts): 1 <= N, M <= 20, 1 <= K <= 70000
Time Limit: 2 seconds, Memory Limit: 128 MiB

==============================

Problem C - Stable Molecule (Max. 20 pts)

Given a tree consisting of N nodes. Label every node with a positive integer. It's allowed to use the same number for multiple nodes. Count the number of ways to label every node such that for each node u and v connected through an edge, product of label of u and label of v must not exceed P.

1 <= N <= 1000
Small (8 pts): 1 <= P <= 10^3
Large (12 pts): 1 <= P <= 10^9
Time Limit: 2 seconds, Memory Limit: 128 MiB

==============================

Problem D - Rotate Sort (Max. 18 pts)

Given an array A of size N. You can use operation (p, q) where 1 <= p <= q <= N to transform array A[1..N] into A[(q+1)..N]+A[p..q]+A[1..(p-1)]. Minimize the number of operations you need to sort array A in ascending order.

Scoring Scheme
For each test case, if your solution is invalid, you gain 0 points. Otherwise:
Let K = the number of operations you need for this test case.
Let K* = the minimum number of operations in every contestant's solution.
Your score is 18 if K = K*, 6 + 9(K*/K) otherwise. (A valid solution is guaranteed to obtain at least 6 points. Sub-optimal solution can earn at most 15 points.)
Your final score for this problem is calculated as the average of all test cases' score.

1 <= N <= 100
Time Limit: 1 second, Memory Limit: 128 MiB