Problem T1: Geometry and Distances

The first problem involves calculating two distances. The first is the distance from a given point to a line segment, and the second is the distance from the same point to a circle.

The distance to the circle is straightforward: it's the distance from the point to the circle's center minus the radius. For the line segment, we calculate the perpendicular distance from the point to the infinite line containing the segment. If the perpendicular projection of the point falls within the segment's bounds, this is the distance. Otherwise, the distance is the minimum distance to either of the segment's endpoints.

// Calculates the Euclidean distance between two points
double calculateDistance(int x1, int y1, int x2, int y2) {
   return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void solve() {
   int x1, y1, x2, y2, px, py, r;
   // ... input reading ...

   // Distance to the circle
   double distToCircle = calculateDistance(px, py, x1, y1) + r;

   // Distance to the line segment
   double distToSegment;
   if (x1 != x2) {
       // Line equation: ax + by + c = 0
       double a = (double)(y1 - y2) / (x1 - x2);
       double b = -1.0;
       double c = y1 - a * x1;
       // Perpendicular distance to the infinite line
       distToSegment = abs(a * px + b * py + c) / sqrt(a * a + b * b);
   } else {
       // Vertical line
       distToSegment = abs(px - x1);
   }
   // ... output formatting ...
}
 

Problem T2: Memoized Search with LCM Optimization

This problem requires finding a value for each query. The solution uses a depth-first search (DFS) with memoization to avoid redundant calculations. An optimization is applied by prceomputing the least common multiple (LCM) of suffixes of the input array. This allows the search to skip certain branches when a condition related to the LCM is met.

#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100005;
int values[MAX_N];
int lcmSuffix[MAX_N];
unordered_map<int int=""> memo[MAX_N];

// Recursive function to find the result for a given starting value
int findResult(int currentValue, int index) {
   if (index > queryCount) return currentValue;
   if (currentValue % lcmSuffix[index] == 0) return currentValue;
   if (currentValue % values[index] == 0) return findResult(currentValue, index + 1);

   int nextValue = currentValue / values[index] + 1;
   if (memo[index].count(nextValue)) return memo[index][nextValue];

   return memo[index][nextValue] = findResult(nextValue * values[index], index + 1);
}

int main() {
   int arraySize, queryCount;
   // ... input reading ...

   // Precompute LCM of suffixes
   lcmSuffix[queryCount] = values[queryCount];
   for (int i = queryCount - 1; i >= 1; --i) {
       lcmSuffix[i] = values[i] * lcmSuffix[i + 1] / __gcd(values[i], lcmSuffix[i + 1]);
   }

   for (int i = 1; i <= arraySize; ++i) {
       printf("%d ", findResult(i, 1));
   }
   return 0;
}
 </int></algorithm></vector></unordered_map>

Problem T3: Combinatorial Dynamic Programming

This is a mathematical problem solved using dynamic programming. The key insight is a derived formula: F_k(S) = sum(T subseteq S) F_0(T) * k^(|S|-|T|). This formula is then translated into a DP state transition. The DP state f(i, w) represents the sum of contributions for the first i elements where the sum of selected elements is w.

The transition is: f(i, w) = f(i-1, w) * k + f(i-1, w - a_i). The first term accounts for not selecting the i-th element, and the second for selecting it.

#include <vector>
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;

int numElements, targetSum, power;
vector<int> elements;
vector<vector long="">> dp;

void solve() {
   // ... input reading ...

   dp.assign(numElements + 1, vector<long long="">(targetSum + 1, 0));
   dp[0][0] = 1;

   for (int i = 1; i <= numElements; ++i) {
       for (int w = 0; w <= targetSum; ++w) {
           dp[i][w] = dp[i - 1][w] * power % MOD;
           if (w >= elements[i - 1]) {
               dp[i][w] = (dp[i][w] + dp[i - 1][w - elements[i - 1]]) % MOD;
           }
       }
   }

   cout << dp[numElements][targetSum] << endl;
}
 </long></vector></int></iostream></vector>

Problem T4: Probabilistic DP with Binary Search

The fourth problem is solved using binary search over the answer. The core of the solution is a probabilistic check function. This function uses random shuffling and a dynamic programming approach with state compression (bitmasking) to verify if a given mid-value is feasible. The DP state dp[i] tracks the best (minimum) value achievable for the i-th element under the current constraints.

#include <vector>
#include <algorithm>
#include <random>
#include <climits>

using namespace std;

struct Point {
   int x, y;
};

vector<point> points;
vector<vector>> valueToIndices;
vector<int> uniqueValues;
int stateDP[100005];
const int INF = INT_MAX;

bool checkFeasibility(int mid) {
   const int trials = 700;
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

   for (int t = 0; t < trials; ++t) {
       shuffle(uniqueValues.begin(), uniqueValues.end(), rng);

       // Initialize DP states for k possible "levels"
       vector<int> bestInState(k, INF);
       bestInState[0] = -INF;

       for (int val : uniqueValues) {
           for (int idx : valueToIndices[val]) {
               // Find the best state we can transition to
               int currentState = upper_bound(bestInState.begin(), bestInState.end(), points[idx].y - mid) - bestInState.begin();
               if (currentState == k) {
                   return true; // Found a valid configuration
               }
               stateDP[idx] = currentState;
           }
           // Update the best values for each state
           for (int idx : valueToIndices[val]) {
               bestInState[stateDP[idx]] = min(bestInState[stateDP[idx]], points[idx].y);
           }
       }
   }
   return false;
}

int main() {
   int testCases;
   // ... input reading ...

   // ... setup (populating points, valueToIndices, uniqueValues) ...

   int low = 1, high = 1e6, answer = 0;
   while (low <= high) {
       int mid = (low + high) / 2;
       if (checkFeasibility(mid)) {
           answer = mid;
           low = mid + 1;
       } else {
           high = mid - 1;
       }
   }
   printf("%d
", answer);
   return 0;
}
 </int></int></vector></point></climits></random></algorithm></vector>