a bit of cf: Codeforces Round #274 (Div. 1)

Problem A:
480A. Exams

Solution:
Sort \( (a_i, b_i) \) pairs and go through the sorted pairs from top to bottom, greedily determining the smallest possible time for each exam.

Problem B:
480B. Long Jumps

Solution:
This problem is actually asking us to perform binary search multiple times. First we check whether there is \(a_i, a_j\) such that their difference is \(x\), which can be performed in \(O(N\lg{N})\) time using binary search. We do the same for \(y\), and then we have 3 cases:
1. If both \(x\) and \(y\) can be measured using the current ruler than output 0
2. We have only 1 of them measurable, then output 1 and the length that is not yet measurable.
3. None of \(x\) and \(y\) is measurable. Here we need to check whether we can just place 1 additional mark such that \(x\) and \(y\) are both measurable as a result. To do this, we form two lists: first list consists of all marks that is formed by adding each existing mark with x, and by subtracting each existing mark with x, while the second list is similarly formed but using y as the offset. Then we check if there is any identical element in both lists. To do this in \(O(N\lg{N})\) time, we sort each list, then for each element in the first list, we try to find the same element in the second list using binary search. If such element can be found, it means that we just need to add one additional marker with value equal to this element. Otherwise, we fallback to the worst case scenario which is to add two markers of value x and y.
While the approach is straightforward conceptually, the implementation is very error prone... (at least to me :( )



Problem C:
480C. Riding in a Lift

Solution:
A DP combinatorics problem. Firstly let W[k][n] be the number of ways we can have a k trip starting from n. Let us first agree that W[0][n] for all n is 1, since the number of ways of not moving is 1 (huh.). Then we have the following recursive relationship:
let m be |n - b|, then
W[k][n] = W[k-1][n-m+1] + W[k-1][n-m+2] + ... + W[k-1][n-1] + W[k-1][n+1] + ... + W[k-1][n+m-1]    (notice we did not add W[k-1][n] as this is not a legal move)
We just need to iterate through k = 1 to K and for each k we iterate through all n = 1 to N. However, if we do the summation one by one in each n, we will face a TLE since the running time becomes \(O(N^2K)\). What we need to do is to store the summation before hand using the 1D DP sum array technique, then the calculation for each W[k][n] becomes O(1).
(During the contest I thought the problem asked for a sequence of distinct levels, which I think is at another level of difficulty :/ yeah anyway thats okay the show must go on :) )

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
using namespace std;

long long mod = (int) 1e9 + 7;
long long dp[5003][5003];
long long sum[5003];
int A, B, N, K;


int main(){
    cin >> N >> A >> B >> K;
    sum[0] = 0;
    for(int i=1;i<=N;++i){
        dp[0][i] = 1;
    }
    for(int k=1;k<=K;++k){
        for(int i=1;i<=N;++i){
            sum[i] = dp[k-1][i] + sum[i-1];
            sum[i] %= mod;
        }
        for(int i=1;i<=N;++i){
            int m = i-B;
            if(m == 0) {
                dp[k][i] = 0;
                continue;
            }
            if(m<0) m*=-1;
            dp[k][i] = sum[min(N,i+m-1)] - sum[max(0,i-m)];
            dp[k][i] %= mod;
            dp[k][i] -= dp[k-1][i];
            dp[k][i] %= mod;
            if(dp[k][i] < 0) dp[k][i] += mod;
        }
    }
    cout << dp[K][A] << endl;
    return 0;
}

Problem D, E havent tried yet.