[My Contests] Intra NSU Programming Contest Fall 2018 (Replay)

Date : 7th December, 2018

Contest Link : https://toph.co/c/inpc-fall-2018-r

This contest was basically arranged for juniors of North South University. So most of the problems
were easy. 

I solved 11 problems out of 12 problems during contest time and got me in top 5 rank. Once again
Geometry punnished me a lot. 

Standings : https://toph.co/c/inpc-fall-2018-r/standings

A. Like Old Times Again
Category   : Add Hoc
Difficulty : Easy
Complexity : O(1)

int main()
{
      cout << 13 << endl;

}

B. Gauss - The Great Mathematician
Category   : Math
Difficulty : Easy
Complexity : O(1)

ll get_nth(ll a, ll d, ll n)
{
      ll nth = (n - a) / d + 1;
      return nth;
}
 
ll get_sum(ll a, ll d, ll n)
{
      ll sum = (2*a + (n - 1) * d) * n;
      sum /= 2;
      return sum;
}
 
int main()
{
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            ll a, b, c;
            cin >> a >> b >> c;
            ll d = b - a;
            ll nth = get_nth(a, d, c);
            ll sum = get_sum(a, d, nth);
            cout << sum << endl;
      }

}

C. For Loop FTW
Category   : Number Theory, Divisor of a number
Difficulty : Easy
Complexity : O(sqrt(n))

int main()
{
      int n;
      cin >> n;
      int maxi = n+1;
      for (int i = 2; i*i <= n; i++)
      {
            if (n % i == 0)
            {
                  int p = i;
                  int q = n / i;
                  if (p+q > maxi) maxi = p+q;
            }
      }
      cout << maxi << endl;
}
D. Think Positive
Category   : Math, Modular Arithmetic
Difficulty : Easy
Complexity : O(1)
int main()
{
      puts("-1");
}
E. XOR on Pascal
Category   : Combinatorics, XOR
Difficulty : Medium
Complexity : pre calculation O(n), query O(logn)
static const int maxn = 1e5 + 5;
static const int logn = 18;
static const ll mod = 1e9 + 7;
 
 
ll fact[maxn];
 
inline void preCalculation()
{
      fact[0] = 1;
      for (int i = 1; i < maxn; i++) fact[i] = (i * fact[i-1]) % mod;
}
 
inline ll bigMod(ll a, ll p, ll m)
{
      if (p == 0) return 1;
      if (p == 1) return a;
      if (p & 1) return (a % m * bigMod(a, p-1, m)) % m;
      ll ret = bigMod(a, p >> 1, m) % m;
      return (ret % m * ret % m) % m;
}
 
inline ll modInverse(ll a, ll m)
{
      return bigMod(a, m-2, m);
}
 
inline ll nCr(ll n, ll r)
{
      ll upor = fact[n] % mod;
      ll nich = (fact[r] * fact[n-r]) % mod;
      nich = modInverse(nich, mod);
      ll ncr = (upor * nich) % mod;
      return ncr;
}
 
 
int main()
{
      preCalculation();
 
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            ll n;
            cin >> n;
            if (n == 0)
            {
                  cout << "1" << endl;
                  continue;
            }
            if (n & 1)
            {
                  cout << "0" << endl;
                  continue;
            }
            cout << nCr(n, n>>1) << endl;
      }
}
F. Niko Plays PUBG
Category   : Graph Theory, DFS
Difficulty : Medium
Complexity : O(n)
static const int maxn = 2e3 + 5;
static const int logn = 18;
 
vi graph[maxn];
bool vis[maxn];
int which[maxn];
 
inline void dfs(int u, int compo)
{
      which[u] = compo;
      vis[u] = 1;
      for (int v : graph[u])
      {
            if (vis[v]) continue;
            dfs(v, compo);
      }
}
 
int main()
{
      //FI;
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            int n, m, q;
            cin >> n >> m >> q;
            FOR(i, m)
            {
                  int u, v;
                  cin >> u >> v;
                  graph[u].eb(v);
                  graph[v].eb(u);
            }
            int compo = 0;
            FOR(i, n) if (!vis[i]) dfs(i, ++compo);
            cout << "Case " << tcase << ":\n";
            FOR(i, q)
            {
                  int a, b;
                  cin >> a >> b;
                  if (which[a] == which[b]) cout << "Chicken dinner coming soon!\n";
                  else cout << "Eat vegetables!\n";
            }
            For(i, maxn)
            {
                  graph[i].clear();
                  vis[i] = 0;
                  which[i] = 0;
            }
      }
}
G. Pota(t)o
Category   : Add Hoc
Difficulty : Medium
Complexity : O(n)
int getMax(string s)
{
      queue <char> PQ;
      int sum = 0;
      int maxi = 0;
      bool flag = 0;
      for (int i = 0; i < sz(s); i++)
      {
            char b = s[i];
            if (b == '(')
            {
                  sum = 0;
                  if (flag == 1)
                  {
                        while (!PQ.empty()) PQ.pop();
                  }
                  flag = 0;
                  PQ.em(b);
            }
            else if (b == ')')
            {
                  flag = 1;
                  if (!PQ.empty())
                  {
                        sum += 2;
                        PQ.pop();
                  }
                  else sum = 0;
            }
            if (sum > maxi) maxi = sum;
      }
      return maxi;
}
 
 
int main()
{
      //FI;
      FAST;
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
             string s;
             cin >> s;
             cout << getMax(s) << endl;
      }
}
H. Find NSUPS
Category   : Dynamic Programing
Difficulty : Medium
Complexity : O(len(text) * len(pat))
ll dp[1000+5][6];
bool memoize[1000+5][6];
 
int N;
string s, pat;
 
inline ll solve(int pos = 0, int take = 0)
{
      if (take >= 5) return 1;
      if (pos >= N) return 0;
      ll &ret = dp[pos][take];
      bool &mem = memoize[pos][take];
      if (mem) return ret;
      mem = 1;
      ll sum = 0;
      if (s[pos] != pat[take])
      {
            sum += solve(pos+1, take);
      }
      else
      {
            sum += solve(pos+1, take+1);
            sum += solve(pos+1, take);
      }
      return ret = sum;
}
 
int main()
{
      //FI;
      cin >> N;
      cin >> s;
      pat = "NSUPS";
      cout << solve() << endl;
}
I. Robin Sparkles
Category   : Geometry
Difficulty :
Complexity :
I could not manage to solve it during contest time.
J. Man in the Queue
Category   : Data Structure, Binary Search
Difficulty : Hard
Complexity : update O(logn * logn), query(logn * logn)
This is a hard problem. I used order set (Policy Based Data Structure) to maintain dynamically
sorting the waiting time and used binary search to cover serving to minimum number of customer.
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
 
template <typename T> using orderset = tree <T, 
                                             null_type, 
                                             greater <T>, 
                                             rb_tree_tag, tree_order_statistics_node_update>;
 
static const int maxn = 1e5 + 5;
static const int logn = 18;
static const ll mod = 1e9 + 7;
 
orderset <ll> os;
int waiting_time[maxn];
 
inline int binarySearch(ll serve, int n)
{
      int low = 1;
      int high = n;
      int ans = -1;
      while (low <= high)
      {
            int mid = low + (high - low) / 2;
            ll kth = *os.find_by_order(mid-1);
            ll ttime = (mid-1) * serve;
            if (ttime > kth)
            {
                  high = mid - 1;
            }
            else
            {
                  ans = mid;
                  low = mid + 1;
            }
      }
      return ans;
}
 
int main()
{
      //FI;
      FAST;
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            int n;
            cin >> n;
            FOR(i, n)
            {
                  cin >> waiting_time[i];
                  os.insert(waiting_time[i]);
            }
            int q;
            cin >> q;
            FOR(_q, q)
            {
                  int type;
                  cin >> type;
                  if (type == 2)
                  {
                        ll serve;
                        cin >> serve;
                        int ans = binarySearch(serve, n);
                        cout << ans << endl;
                  }
                  else
                  {
                        int pth;
                        ll tym;
                        cin >> pth >> tym;
                        os.erase(os.lower_bound(waiting_time[pth]));
                        waiting_time[pth] = tym;
                        os.insert(waiting_time[pth]);
                  }
            }
            os.clear();
      }
}
K. Bakana
Category   : Number Theory, Fast Exponentiation
Difficulty : Medium
Complexity : O(logn)
inline ll bigMod(ll a, ll p, ll m)
{
      if (p == 0) return 1 % m;
      if (p == 1) return a;
      if (p & 1) return (a % m * bigMod(a, p-1, m)) % m;
      ll ret = bigMod(a, p >> 1, m) % m;
      return (ret % m * ret % m) % m;
}
 
inline ll modInverse(ll a, ll m)
{
      return bigMod(a, m-2, m);
}
  
int main()
{
      //FI;
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            ll N, a, b, M;
            cin >> N >> a >> b >> M;
            ll gcd = __gcd(a, b);
            ll ans = (bigMod(N, gcd, M) - 1 + M) % M;
            cout << ans << endl;
      }
}
L. Magical Pascal
Category    : Lucas Theorem, Dynamic Programing, Digit DP
Difficulty  : Hard
Complexity  :

This is the toph problem of the contest. Only a few number of contestants could solve this problem.
I was one of them and got a lot of pleasure to solve the problem.
static const int maxn = 2e3 + 5;
static const int logn = 18;
static const ll mod = 1e9 + 7;
 
 
ll dp[100][100];
bool memoize[100][100];
int a[100];
 
inline ll bigMod(ll a, ll p, ll m)
{
      if (p == 0) return 1;
      if (p == 1) return a;
      if (p & 1) return (a % m * bigMod(a, p-1, m)) % m;
      ll ret = bigMod(a, p >> 1, m) % m;
      return (ret % m * ret % m) % m;
}
 
inline ll modInverse(ll a, ll m)
{
      return bigMod(a, m-2, m);
}
 
inline ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)
{
      if (pos < 0)
      {
            return bigMod(2, one, mod) % mod;
      }
      ll &ret = dp[pos][one];
      bool &mem = memoize[pos][one];
      if (!flag && take && mem) return ret;
      int loop = 1;
      if (flag) loop = a[pos];
      ll sum = 0;
      for (int i = 0; i <= loop; i++)
      {
            if (!take && i == 0) sum = (sum + solve(pos-1, 0, 0, 0)) % mod;
            else sum = (sum + solve(pos-1, one + (i == 1), flag & i == a[pos], 1)) % mod;
      }
      if (!flag && take) mem = 1, ret = sum;
      return sum;
}
 
inline ll digit(ll num)
{
      int len = 0;
      while (num)
      {
            a[len++] = num % 2;
            num /= 2;
      }
      return solve(len-1) % mod;
}
 
inline ll mulMod(ll a, ll b, ll p)
{
      ll x = 0;
      ll y = a % p;
      while (b)
      {
            if (b & 1) x = (x + y) % p;
            y = (y * 2) % p;
            b /= 2;
      }
      return x % p;
}
 
int main()
{
      ll n;
      cin >> n;
      ll sum = mulMod(n, n+1, mod);
      sum = (sum * modInverse(2, mod)) % mod;
      ll nn = n-1;
      ll ans = (sum - digit(nn) + mod) % mod;
      cout << ans << endl;
}