August 25, 2020 2020 TCO Southern Asia Regionals Algorithm Editorials

PerfectSquares

Hint: The total numbers x satisfying the condition x = k ^ n (where n >= 2 and k is an integer) in range [1, 10^11] is not so much, it’s 320990.

We iterate on k from 2 to . For every k, we calculate it’s different powers (till maxN) and if it is in range [minimum, maximum], we add it to our set. Finally, return the size of the set.

Code by SSRS_:

    int countRange(long long minimum, long long maximum, int maxN){
        set<long long> st;
        for (int p = 2; p <= maxN; p++){
            long long base = 1;
            while (1){
                long long answer = 1;
                for (int i = 0; i < p; i++){
                    answer *= base;
                }
                if (minimum <= answer && answer <= maximum){
                    st.insert(answer);
                }
                if (answer > maximum){
                    break;
                }
                base++;
            }
        }
        return st.size();
    }

PackingContainers

Hint: Greedy.

Start from the largest container. Try to find the largest container that can be nestled into it. Continue and extend your nestled chain.

Continue the process above till no container remains.

Code by aryanc403 (using the same idea but a little different in approach):

  int pack(vector <int> a) {
    sort(a.begin(), a.end());
    vector<int> b;
    for(auto x:a){
      sort(b.begin(), b.end(), greater<int>());
      bool fl=false;
      for(auto &y:b){
        if(x-y>=10)
        {
          y=x;
          fl=true;
          break;
        }
      }
      if(!fl)
        b.push_back(x);
    }
    int ans=0;
    for(auto x:b)
      ans+=x;
    return ans;
  }

HorseRacing

Keep a map q (dictionary in Python) from horses to the race they appeared in. Now process characters in the ticket one by one. For each character like c,

  • If c is not present in q, the answer is -1.
  • If we have seen q before, the answer is -1.
  • Otherwise, if c is the first character in q, answer += 1

Cod by espr1t:

    int validateTicket(vector <string> races, string ticket) {
        map <char, int> q;
        for (int i = 0; i < (int)races.size(); i++) {
            for (int c = 0; c < (int)races[i].size(); c++) {
                q[races[i][c]] = i;
            }
        }
        set <char> seen;
        set <int> rseen;
        int ans = 0;
        for (int i = 0; i < (int)ticket.size(); i++) {
            if (seen.find(ticket[i]) != seen.end())
                return -1;
            if (q.find(ticket[i]) == q.end())
                return -1;
            if (rseen.find(q[ticket[i]]) != rseen.end())
                return -1;
            rseen.insert(q[ticket[i]]);
            seen.insert(ticket[i]);
            if (races[q[ticket[i]]][0] == ticket[i])
                ans++;
        }
        return ans;
    }

FrameBall

There are three cases to consider:

  • X <= r. We can win during the first phase – where you’re putting red balls and color balls return to the table after removing. It is possible if and only if r*(c+2)+x>y+sum of colors.
    In this case, we can find the minimum X such that X * (c+2) + x > y + (r – x) * (c + 2) + sum of colors.
  • X > r. We want to find minimum X such that x + r * (c + 2) + sum of the first X – r balls of colors > y + sum of the last c – (X – r) colors.
  • X = -1.

Code by Chandnani:

  vector<long long> solve(vector <int> C, vector <int> N, vector<long long> yourScore, vector<long long> oppScore) {
    int t = sz(C);
    vector<ll> ans;
    rep(i,t){
      ll x = yourScore[i],y=oppScore[i];
      ll c = C[i],n = N[i];
      ll sc = (c+1)*(c+2)/2;sc--;
      ll r = max(n-c,0ll);
      if(c>=n){
        sc++;
        sc-=(c+2-n)*(c-n+1)/2;
      }
      if(r*(c+2)+x>y+sc){
        ll lo = 0,hi = r;
        while(lo<hi){
          ll mid = (lo+hi)/2;
          if(mid*(c+2)+x>(r-mid)*(c+2)+y+sc){
            hi = mid;
          }
          else lo = mid+1;
        }
        if(lo>0&&(lo-1)*(c+2)+1+x>y+(r-lo)*(c+2)+sc){
          ans.pb(2*lo-1);
        }
        else ans.pb(2*lo);
      }
      else{
        x+=r*(c+2);
        ll cur = 2*r;
        n=min(n,c);
        if(x+sc<=y){
          ans.pb(-1);
        }
        else{
          ll lo=0,hi=n;
          while(lo<hi){
            ll mid=(lo+hi)/2;
            ll rem = n-mid;
            ll lef = (c+1)*(c+2)/2 - (c+1-rem)*(c+2-rem)/2;
            if(x+sc-lef>y+lef){
              hi=mid;
            }
            else lo=mid+1;
          }
          ans.pb(cur+lo);
        }
      }
    }
    return ans;
  }

DesChiffres

Hint: Full bruteforce.

Consider we have set S of numbers and we want to know f(S) = set of numbers can be produced by an arithmetic expression using numbers in S.

The answer is the maximum value of f(S) where S = tiles.

There are two cases to consider:

  • Our arithmetic expression contains just one element: This is one of the elements in S.
  • Our arithmetic expression contains more than one element. So there is an binary operation (+-/*) in it that has the highest priority. For example in expression 2 + 2 * 3 the * operator has the highest priority. In 2 + 2 + 2 the leftmost + has highest priority.
    Divide S into two parts, L, R (try every possible L, R). Calculate f(L) and f(R), then for each x in f(L) and y in f(R), add x + y, x – y, x * y, x / y (if possible) to the result set f(S).

Code by vivek1998299:

  set<ll> recur(vector<int> a) {
 
    if (a.size() == 1)
      return set<ll>{a[0]};
 
    int n = a.size();
 
    set<ll> curr;
    for (int i = 1; i < n; i++) {
 
      set<ll> left1 = recur(vector<int>(a.begin(), a.begin() + i));
      set<ll> right1 = recur(vector<int>(a.begin() + i, a.end()));
 
      for (auto &it : left1) {
        for (auto &it2 : right1) {
          curr.insert(it * it2);
          curr.insert(it + it2);
          if (it2 && (it % it2) == 0)
            curr.insert(it / it2);
          curr.insert(it - it2);
        }
      }
    }
 
    return curr;
  }
 
  int solve(vector<int> tiles, int target) {
 
    int n = tiles.size();
 
    ll res = inf;
    ll ans = inf;
    for (int i = 1; i < (1 << n); i++) {
      vector<int> arr;
      for (int j = 0; j < n; j++) {
        if ((i >> j) & 1)
          arr.push_back(tiles[j]);
      }
      sort(arr.begin(), arr.end());
 
      do {
 
        set<ll> curr;
        curr = recur(arr);
 
        for (auto &it : curr) {
          if (abs(it - target) < res) {
            res = abs(it - target);
            ans = it;
          } else if (abs(it - target) == res) {
            ans = min(ans, it);
          }
        }
 
      } while (next_permutation(arr.begin(), arr.end()));
    }
 
    return ans;
  }

BridgesAndCutVertices

Start from a triangle, C = B = 0. Attaching a vertex with an edge to the current graph adds one to B and 1 to C. Attaching another triangle to the current graph adds one to C but doesn’t change B. Adding an edge out of the current graph adds one to B but doesn’t change C. Below code is completely easy to understand.

Code by hitonanode:

    vector<int> ret;
    void ade(int u, int v)
    {
        ret.emplace_back(u);
        ret.emplace_back(v);
    }
    vector<int> construct(int B, int C)
    {
        ret.clear();
        ade(0, 1);
        ade(0, 2);
        ade(1, 2);
        int t = 2;
        while (C)
        {
            if (B and C)
            {
                B--;
                C--;
                ade(t, t + 1);
                t++;
            }
            else
            {
                C--;
                ade(t, t + 1);
                ade(t, t + 2);
                ade(t + 1, t + 2);
                t += 2;
            }
        }
        while (B)
        {
            t++;
            ade(t, t + 1);
            t++;
            B--;
        }
        return ret;
    }

TwoPerLine

Hint: DP.

dp[i][z][o] = we have processed first i rows and currently have z columns that have no token in them, and currently have o columns that have a token in them, and for sure n – o – z columns that have two tokens in them.

The base dp is dp[0][n][0] = 1.

Now from dp[i][z][o] we update dp[i + 1]:

  • We can put no token in the row i: dp[i + 1][z][o] += dp[i][z][o].
  • We can put a token in the row i and in a column that doesn’t contain any tokens till now: dp[i + 1][z – 1][o + 1] += z * dp[i][z][o].
  • dp[z][o – 1] += o * old[z][o].
  • dp[i + 1][z – 2][o + 2] += z * (z – 1) / 2 * old[z][o].
  • dp[i + 1][z – 1][o] += o * z * old[z][o].
  • dp[i + 1][z][o – 2] += o * (o – 1) / 2 * old[z][o].

The answer is the sum of dp[n][z][o] where o + 2(n – z – o) = t.

Code by arpa:

typedef long long ll;
const int maxn = 2e2 + 14, mod = 1e9 + 7;
struct TwoPerLine{
    int dp[maxn][maxn], old[maxn][maxn];
    void sadd(int z, int o, ll b){
        if(z < 0 || o < 0)
            return ;
        dp[z][o] = (dp[z][o] + b) % mod;
    }
    int count(int n, int t){
        memset(dp, 0, sizeof dp);
        dp[n][0] = 1;
        for(int i = 0; i < n; i++){
            memcpy(old, dp, sizeof dp);
            memset(dp, 0, sizeof dp);
            for(int z = 0; z <= n; z++)
                for(int o = 0; o + z <= n; o++){
                    sadd(z, o, old[z][o]);

                    sadd(z - 1, o + 1, (ll) z * old[z][o]);
                    sadd(z, o - 1, (ll) o * old[z][o]);

                    sadd(z - 2, o + 2, (ll) z * (z - 1) / 2 * old[z][o]);
                    sadd(z - 1, o, (ll) o * z * old[z][o]);
                    sadd(z, o - 2, (ll) o * (o - 1) / 2 * old[z][o]);
                }
        }
        int ans = 0;
        for(int z = 0; z <= n; z++)
            for(int o = 0; o + z <= n; o++)
                if(o + (n - z - o) * 2 == t)
                    (ans += dp[z][o]) %= mod;
        return ans;
    }
};


Guest Blogger



UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds