AtCoder 188

A - Three-Point Shot
Can the lower-point team win with a 3-point goal?

three-point.cppview raw

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

int main(){
    int x, y;
    cin>>x>>y;
    if(abs(x-y)<3) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;

}

B - Orthogonality
If two vectors are orthogonal?

orthogonality.cppview raw

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d", &a[i]);
    for(int i=0;i<n;i++) scanf("%d", &b[i]);
    int res = 0;
    for(int i=0;i<n;i++) res += a[i] * b[i];
    if(res==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

C - ABC Tournament
Simulate the runner-up of 1-1 elimination team match.

ABC-tournament.cppview raw

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second

int main(){
    int n;
    cin>>n;
    vector<PII>v(1<<n);
    for(int i=0;i<1<<n;i++) {
        int t;
        cin>>t;
        v[i] = {t, i+1};
    }
    for(int i=0;i<n-1;i++){
        int k = 0;
        for(int j=0;2*j+1<v.size();j++){
            auto t1 = v[2*j], t2 = v[2*j+1];
            if(t1.x > t2.x) v[k++] = t1;
            else v[k++] = t2;
        }
        v.resize(k);
    }
    if(v[0].x < v[1].x) cout<<v[0].y<<endl;
    else cout<<v[1].y<<endl;
    return 0;
}

D - Snuke Prime
Discretization. Event sweeping method.

snuke-prime.cppview raw

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

typedef long long LL;

int main(){
    LL N, C;
    cin>>N>>C;
    vector<pair<LL,LL>> event;
    for(int i=0; i<N;i++){
        LL a, b, c;
        cin>>a>>b>>c;
        event.push_back({a-1, c});
        event.push_back({b, -c});
    }

    sort(event.begin(), event.end());
    LL ans = 0, fee = 0, t = 0;
    for(auto [x, y]: event){
        if(x!=t){
            ans += min(C, fee) * (x-t);
            t = x;
        }
        fee += y;
    }
    cout<<ans<<endl;
    return 0;
}

E - Peddler
Stock selling on a DAG
Solution:
Build a reverse graph.
For each vertex i, calculate dp[i]: the cheapest purchase price reachable from i (only vertex prior current vertex in DAG, therefore reverse edges).
Sell at vertex i and update res = A[i] - dp[i];

peddler.cppview raw

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;

int main(){
    int n, m;
    cin>>n>>m;
    vector<int> A(n+1);
    for(int i=1;i<=n;i++) scanf("%d", &A[i]);
    vector<int>g[n+1];
    for(int i=0;i<m;i++){
        int a, b;
        scanf("%d%d", &a, &b );
        // reverse edges
        g[b].push_back(a);
    }

    // lowest price reachable from i, sell at point i
    vector<LL> dp(n+1, INF);
    LL res = -INF;
    for(int i=1;i<=n;i++){
        for(int x:g[i]){
            dp[i] = min(dp[i], dp[x]);
        }
        if(dp[i] < INF) res = max(res, (LL)A[i] - dp[i]);
        dp[i] = min(dp[i], (LL)A[i]);
    }
    cout<<res<<endl;
    return 0;
}

F - +1-1x2
Return the minimum steps from X to Y, by applying:

1. X = X + 1
2. X = X - 1
3. X = X * 2
   Solution: A BFS problem. The range of data is very big.
   Start search from Y instead.
   If current y is smaller than X, then can only apply operation 1.
   Otherwise, y can do %2 (if odd) or y = y + 1, or y = y - 1;
   Two pruning strategies:
4. if step is greater than best ans, break;
5. if current y is smaller than X, calculate abs(X - y) and continue;

   +1-1x2.cppview raw

   #include <iostream>
   #include <vector>
   #include <queue>
   #include <cstring>
   #include <algorithm>
   #include <string>
   #include <unordered_set>
   using namespace std;
   #define x first
   #define y second
   typedef long long LL;
   typedef pair<LL, LL> PLL;
   
   int main(){
       LL x, y;
       cin>>x>>y;
       if(x>=y) cout<<x-y<<endl;
       else{
           unordered_set<LL>s;
           LL ans = y - x;
           queue<PLL>q;
           q.push({y, 0});
           s.insert(y);
           while(q.size()){
               auto t = q.front(); q.pop();
               if(t.y >= ans) break;
               ans = min(ans, t.y+ abs(t.x - x));
               if (t.x <= x) continue; // not break; can no longer apply //2.
               if(t.x %2 ==0){
                   if(!s.count(t.x/2)) {
                       s.insert(t.x/2);
                       q.push({t.x/2, t.y + 1});
                   }
               }
               else {
                   if(!s.count(t.x + 1)){
                       s.insert(t.x + 1);
                       q.push({t.x + 1, t.y + 1});
                   }
                   if(!s.count(t.x - 1)){
                       s.insert(t.x - 1);
                       q.push({t.x - 1, t.y + 1});
                   }
               }
   
           }
           cout<<ans<<endl;
       }
       return 0;
   }