Codeforces Educational round 169 Div2 walkthru

Problem A:

there can be no solution if there are 3 or >3 different numbers, so we just have to think of == 2 case.
and also , if there isnt a number between the a[0] and a[1].

so solution can be written like this.

#include <bits/stdc++.h> 
using namespace std; 

int main()  { 
    auto solve = [](void)->void { 
        int n; cin>>n; 
        vector<int> a(n); 
        for(auto &i : a ) cin>>i; 
        if ( n == 2 && (a[1] != a[0] + 1 )) { 
            cout << "YES\n"; 
        } else { 
            cout << "NO\n";
        }
    };
    int t; cin>>t; while(t--) solve();
    return 0 ; 
}

Problem B:

Here we are only concerned about the common length of 2 segments.
corner condition need to think of is that there end are same. so we have to acomodate for those numbers also.

#include <bits/stdc++.h> 
using namespace std; 

int main() { 
    auto solve = [](void) -> void { 
        int l , r , L , R; 
        cin>>l>>r>>L>>R; 
        int commonL = max(l, L); 
        int commonR = min(r, R); 
        /* 
            ..l.......r|L.....R ...
        */
        int ans = commonR - commonL + 2;
        if ( ans < 2) { cout << 1 << endl; return; }
        if (r==R) ans--;
        if (l==L) ans--;
        cout << ans << endl; 
    };
    int t; cin>>t; while(t--)solve();
    return 0 ; 
}

Problem C:

Alice can never score less than B, because she has the first pick, and she will always pick the max. so we have to optimize the second to max's in the array. here's one way to do it.

#include <bits/stdc++.h> 
using namespace std; 

int main() { 
    auto solve = [](void)->void { 
        int n,k; cin>>n>>k;
        vector<int> a(n); 
        for(auto &i : a )cin>>i; 
        sort(a.begin(), a.end());

        for(int i = n-2;i>=0;i-=2) { 
            if (k >= (a[i+1] - a[i])) { 
                k -= (a[i+1] - a[i]); 
                a[i] = a[i + 1];
            } else { 
                a[i] += k; 
                break; 
            }
        }
        long long A=0,B=0;
        for (int i = n-1, turn = 0 ; i>=0 ; i--,turn++) { 
            if (turn & 1 ) {
                B += a[i]; 
            } else A += a[i]; 

        }
        cout << A - B << endl; 
    };
    int t; cin>>t; while(t--) solve(); 
    return 0;
}

Problem D:

now this is a interesting problem. our main observation should be that if there is a common element between string L and string R , then we can find the path directly, but if not then we can find the path using the help of a intermediate number. like
for example
BR -> RY -> GY
so here intermediate in RY.
in my solution i used binary search to find the closest match to string RY next to string BR ( or rather position L ).
here's the implementation.

#include <bits/stdc++.h> 
using namespace std; 

int main() { 
    auto solve = [](void )->void { 
        int n , m; 
        cin>>n>>m;
        map<pair<char,char>, vector<int>> M; 
        auto C = [](pair<char,char> a)->pair<char,char> {
            pair<char,char> b = a; 
            if( a.first > a.second) { 
                b = {a.second , a.first};
            }
            return b;
        };
        vector<string> input;
        for(int i = 0 ; i < n; i++) { 
            string t ; cin>>t; 
            input.push_back(t);
            M[C({t[0], t[1]})].push_back(i);
        }

        auto find = [&](vector<int> &a ,int pos)-> int { 
            if (a.size() == 0) return 1e9;
            // cout << "find : "; for(auto i : a )cout << i << " ";cout << endl; 
            const int n = a.size();
            int l = 0, r = n;
            while(l < r - 1 ){ 
                int mid = (l +r )/2; 
                if ( a[mid] <= pos ) {
                    l = mid; 
                } else { 
                    r = mid; 
                }
            }
            return l;
        };
        auto commonE = [](string a, string b) -> bool { 
            assert(a.size() == 2 ); 
            assert(b.size() == 2 );
            for (int i =0 ; i < 2; i++)
                for (int j = 0 ; j < 2; j++) 
                    if (a[i] == b[j]) 
                        return true; 
            return false; 
        };

        while(m--) {
            int L , R ; 
            cin>>L>>R; L--,R--;
            if ( commonE(input[L], input[R])) { 
                cout << abs( R - L )  << endl; 
            } else { 
                int ans = 1e9;
                for (int i = 0 ; i < 2; i++) { 
                    for (int j = 0 ; j < 2 ; j++){ 
                        char first = input[L][i];
                        char second = input[R][j]; 
                        // cout << ans << " " << first << " " << second << endl; 
                        int loc = find(M[C({first, second})], L);
                        if (loc == 1e9)
                            continue; 
                        int locM =  M[C({first,second})][loc];
                        ans = min(ans, abs(L - locM) + abs(locM - R)); 
                        // cout << "locM" << " " << locM << " loc " << loc << endl; 
                        if (loc != M[C({first,second})].size() -1 ){ 
                            int locM2 = M[C({first,second})][loc + 1]; 
                            ans = min(ans , abs(L - locM2) + abs(locM2 - R));
                        }
                    }
                }
                cout << (ans == 1e9 ? -1 : ans) << endl; 
            }
        }
    };
    int t; cin>>t; while(t--) solve();
    return 0 ;
}

Blog

Codeforces Educational round 169 Div2 walkthru

pastaPicaso

Join Our Newsletter. No Spam, Only the good stuff.

Related