## Intuition The problem revolves around recalculating the rating changes dynamically as participants are removed from the contest results. The key insight is that we need to repeatedly check the conditions for each participant based on their position and remove them if their rating change is less than `k`. This process is dynamic because removing a participant affects the positions and rating changes of the remaining participants. ## Approach 1. **Initial Calculation**: - Calculate the initial rating changes for each participant. The rating change for the participant at position `i` is given by: \[ d_i = a_i - a_1 - (i - 1) \times 10 \] - Here, `a_i` is the rating of the participant at position `i`, and `a_1` is the rating of the first participant. 2. **Dynamic Removal**: - Iterate over the participants and check if any participant has a rating change `d_i < k`. - If such a participant is found, remove them from the list and recalculate the rating changes for the remaining participants. - Repeat this process until no more participants can be removed. 3. **Output**: - Keep track of the original indices of the participants who are removed in the order they are removed. - Print these indices as the result. ## Complexity - **Time Complexity**: O(n^2) in the worst case, because in each iteration, we might need to recalculate the rating changes for all remaining participants. - **Space Complexity**: O(n) for storing the ratings and indices. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin >> n >> k; vector> participants(n); // pair of (rating, original index) for (int i = 0; i < n; ++i) { cin >> participants[i].first; participants[i].second = i + 1; // store original index } vector removed_indices; while (true) { bool removed = false; for (int i = 1; i < participants.size(); ++i) { long long d_i = participants[i].first - participants[0].first - (i * 10); if (d_i < k) { removed_indices.push_back(participants[i].second); participants.erase(participants.begin() + i); removed = true; break; } } if (!removed) break; } for (int index : removed_indices) { cout << index << " "; } cout << endl; return 0; } ``` This solution reads the input, calculates the initial rating changes, and iteratively removes participants whose rating change is less than `k`. It outputs the indices of the removed participants in the order they are removed.

Sereja and Contest

Problem Details