AIT Crack Editorial

editorial
1

https://www.codechef.com/AITC19TS

  1. Help Ajay!! - As the problem state , the player who wins the last game wins. Also the printing the player who won more matches also the accepted solution.

  2. Solve for Sakura!! - The first number in the i’th row is the sum of first i natural numbers. Therefore it is - (i*(i + 1)) / 2. Now the m’th element in the n’th row , will be : (n*(n + 1)) / 2 + m.

  3. Sahil in trouble!!! - It can be easily seen that the subset can be generated by print the ith element of the set S if the ith bit is set in the binary representation of n and not printing anything if the bit is not set.

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;typedef long double ld;
#define F first
#define S second
#define PB push_back
#define MP make_pair
const ll mod = 1e18, M = 3e5+7;
ll powe(ll x, ll y){ ll ans = 1;while(y>0){if (y&1){ans = (1ll * x * ans);}y>>=1;x = (1ll * x * x);}return ans;}
int main(){
    fast;
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if (n == 1)
            cout<<"NULL";
        n--;
        int pow = 0;
        while(n){
            if (n&1)
                cout<<powe(3,pow)<<" ";
            n>>=1;
            pow++;
        }
        cout<<"\n";
    }
    return 0;
}
  1. Josephus Again - Note that there are 2 cases:
  • If N is even, you will always end up at 1st person if you are able to replace all dead people in 1 cycle.
  • If N is odd, you will move 1 step further for 1 cycle if you are able to replace all dead people in that cycle. For rest of people remaining in group we can simulate process by traversing in array and following steps or using standard Josephus problem.
 int main(){
    fast;
    int t;
    cin>>t;
    while(t--){
        ll n,m,dn;
        cin>>n>>m;
        m = (2*m)%n;
        int lpos = 0;
        for (int i = 0; i<64; i++)
            if (n&1ll<<i)
                lpos = i;
        dn = n^(1ll<<lpos);
        dn = 2*dn + 1;
        dn = (dn-1+m)%n +1;
        cout<<dn<<"\n";
    }
    return 0;
}
  1. Make him The Ultimate - At first in this simple problem you need to find shortest path between all pair of transformtion. That can’t be done using O(N^3) algorithms, so you must use Dijkstra algorithm to find this in O(NNlogN) time. Next part of this problem is to create new matrix, G[i][j] = C[i], if D[i][j] <= requiredBattery[i], else G[i][j] = INF. Here D[i][j] – length of shortest path between i and j. So, result is shortest path between X and Y using matrix G. That can be done using simple Dijkstra algorithm.
        #include <bits/stdc++.h>
        #define int long long
        #define w cout
        #define e '\n'
        using namespace std;
        const int N = 1e3 + 10;
        int n , m , start , endd;
         
        int a[N] , b[N] , W[N] , t[N] , c[N] , dist[N][N];
         
        vector<pair<int , int > > v[N];
        vector<int> can[N];
         
        void find_path(int i) {
            dist[i][i] = 0;
            set<pair<int , int > > q;
            q.insert({0 , i});
            while(q.size()) {
                int from = (*q.begin()).second , d = (*q.begin()).first;
                q.erase(q.begin());
                for(auto to : v[from]) {
                    int dd = d + to.second;
                    if(dd < dist[i][to.first]) {
                        q.erase({dist[i][to.first] , to.first});
                        q.insert({dd , to.first});
                        dist[i][to.first] = dd;
                    }
                }
            }
        }
            
         
            
         
        signed main() {
            ios::sync_with_stdio(0); cin.tie(0) ; cout.tie(0);
            cin >> n >> m >> start >> endd;
        
        for(int i = 0 ; i < m ; i ++ ) {
            int x , y , z; cin >> x >> y >> z;
            v[x].push_back({y , z}) , v[y].push_back({x , z});
        }
        for(int i = 1 ; i <= n ; i ++ ) {
            for(int j = 1 ; j <= n ; j ++ ) {
                dist[i][j] = 1e15;
            }
        }
        for(int i = 1 ; i <= n ; i ++ ) {
            cin >> t[i] >> c[i];
            find_path(i);
        }
        int ans[N] ;
        for(int i = 0 ; i <= n ;i ++ ) ans[i] = 1e15;
        set<pair<int , int > > q;
        ans[start] = 0;
        
        q.insert({0 , start});
        while(!q.empty()) {
            int i = (*q.begin()).second , d = (*q.begin()).first;
            q.erase(q.begin());
            for(int j = 1 ; j <= n ;j ++ ) {
                if(dist[i][j] > t[i]) continue;
                int dd = c[i] + d;
                if(dd < ans[j]) {
                    q.erase({ans[j] , j});
                    ans[j] = dd;
                    q.insert({dd , j});
                }
            }
        }
        if(ans[endd] == 1e15) w << -1;
        else
        cout << ans[endd];
        
    }
1 Like