November 28, 2020 Topcoder SRM 793 Editorials

Match summary

I was a participant in this contest! A lot of hacks on GoldMining! Cakewalk Div. 2 problem, a binary search problem afterward and a corner case problem at the end for Div. 2.

For Div. 1, round began with a corner case problem, then a dp problem and a complete theory problem at the end.

In Div. 2 just one participant solved the last problem, in Div. 1, four participants solved the last problem. ksun48 beat tourist and took the first place in Div. 1 and jackylove took the first place in Div. 2.

The Problems

SimplestCrossword

Used as: Division Two – Level One:

If there is no letter appearing in both H and V, the answer is {}. 

Otherwise we can always find an answer. Consider the i-th letter of V is the same as the j-th letter of H. We put V in the j-th column and H in the i-th row. Their intersection – the character that they both have it – will position in cell i, j.

To make it easier to implement, just like the C++ code below, add rows one by one. Consider the i-th character of V, if it matched some character in H, say j, start looping on k from 0 to V.size() – 1.

Now add rows one by one. If k is i, simply add H as a row. Otherwise add a row with all cells equal to ‘.’ except the j-th row which is equal to v[k].

Code by Arpa:

vector <string> construct(string H, string V){
    for(int i = 0; i < V.size(); i++){
        int j = H.find(V[i]);
        if(j == -1)
            continue;
        vector<string> ret;
        for(int k = 0; k < V.size(); k++)
            if(k == i)
                ret.push_back(H);
            else{
                ret.push_back(string(H.size(), '.'));
                ret.back()[j] = V[k];
            }
        return ret;
    }
    return {};
}

Code by recuraki:

def construct(self, s1,s2):
    can = False
    l1 = len(s1)
    l2 = len(s2)
    for i in range(l1):
        for j in range(l2):
            if s1[i] == s2[j]:
                can = True
                break
        if can:
            break
    if can is False:
        return tuple("")
    print("")
    res = []
    for ii in range(l2):
        s = ["."] * l1
        s[i] = s2[ii]
        if ii == j:
            s = list(s1)
        res.append("".join(s))
        #print("".join(s))
    return tuple(res)

JumpAcrossTheRiver

Used as: Division Two – Level Two:

Hint: Binary Search.

Consider we can make jumps of length at most x. How many jumps do we need to reach the other side? If there are two stones with distance more than x, we can never reach the otherside. Otherwise we can find how many jumps we need to reach the other side. Let f(x) be the minimum jumps needed to reach the otherside if we can jump with length at most x. If we can’t reach the otherside, f(x) = inf.

So we want to find the minimum L which f(L) <= J. Note that f is a non-increasing function. When x rises, f(x) decreases. This leads us to use binary search. We can find such L with binary search easily. You can check implementations below.

Code by Arpa:

ll minLength(int N, int M, int J){
    ll lo = 0, hi = 1e16;
    while(hi - lo > 1){
        ll mid = (lo + hi) / 2;
        int cnt = 0;
        for(int i = 0, j = 0; i < N; i = j){
            cnt++;
            ll dis = 0;
            while(j < N && dis + 1 + (ll) j * j % M <= mid)
                dis += 1 + (ll) j * j % M, j++;
            if(i == j){
                cnt = 1e9;
                break;
            }
        }
        (cnt <= J ? hi : lo) = mid;
    }
    return hi;
}

Code by recuraki:

class JumpAcrossTheRiver:
def minLength(self, n, m, j):
    l = [0]
    cur = 0
    for i in range(n):
        cur +=  1 + ((i*i ) % m)
        l.append(cur)

    #print(l, j)
    low = 0
    high = 10**32
    import bisect
    from bisect import bisect_left
    from bisect import bisect_right

    def do(power):
        curloc = 0
        curlocval = 0
        ind = 0
        jumpcnt = 0
        can = False
        while curloc < (n+1):
            #print("try", jumpcnt, "cur", curloc, curlocval, power)
            nextloc = bisect_right(l, curlocval + power)
            if nextloc == curloc:
                break # cannot move
            #print("next", nextloc)
            curloc = nextloc
            curlocval = l[curloc - 1]
            jumpcnt += 1

        if curloc == (n+1):
            can = True

        if can is False:
            return False
        #print("jump", jumpcnt, jumpcnt <= j)
        return jumpcnt <= j

    while low <= high:
        mid = (low + high) // 2
        if not do(mid): # ok
            low = mid + 1
        else: # ng
            high = mid - 1
    xxx = do(mid)
    res = low if (xxx != -1 and xxx <= j) else high
    print(res)
    return res

GoldMining

Used as: Division Two – Level Three:

Used as: Division One – Level One:

Hint: decide every minute.

One needs just a careful mind to solve this problem step by step. Every minute, first consider you have an infinite amount of gold to hire workers, how many workers do you hire?

Consider we’re in i-th minute (1-based). A worker can compensate his hiring cost if and only if miningTime – i > hiringCost. Another point to consider is we have limited amounts of gold in the ground. So hiring so many workers where there is not enough gold for them to mine is incorrect.

Consider we currently have w workers currently and goldInGround amount of gold remained (in minute i). If we go ahead with these workers, we will finish with more min(goldInGround, (1 + w) * (miningTime – i)) golds at the end. By “more”, I mean in addition to golds earned till this minute 

So there is goldInGround – (1 + w) * (miningTime – i) remaining for new workers to mine. Each added worker mines miningTime – i golds from it. So hiring 

workers is for sure efficient. There is a tricky case when we have a little more golds remaining again after hiring these workers (because the division is floored division) we just check if (goldInGround – (1 + w) * (miningTime – i)) % (miningTime – i) > hiringCost we hire this extra worker.

In the last step we remove the initial consideration, “we have an infinite amount of gold to hire workers”. We can’t hire more than ans workers, where ans is the current gold mined.

That’s it. Time complexity is O(miningTime).

Code by jackylove:

long long maxProfit(long long goldInGround, long long miningTime, long long hiringCost) {
  long long w = 0, ans = 0;
  
  for (int i = 1; i <= miningTime; ++i) {
    long long change = min(w + 1, goldInGround);
    ans = ans + change;
    goldInGround -= change;
    if (goldInGround <= 0) return ans;
    if (miningTime - i > hiringCost) {
      long long res = goldInGround - (1 + w) * (miningTime - i);
      long long t = res / (miningTime - i);
      if (res % (miningTime - i) > hiringCost) ++t;
      if (t > 0) {
        t = min(t, ans / hiringCost);
        w += t;
        ans -= t * hiringCost;
      }
    }
  }
  
  return ans;
};

Cascade

Used as: Division One – Level Two:

Hint: As you expect, dp!

Ok, dp. Let dp[i] be the expected sum of power if we play card i. Obviously, if card i doesn’t have cascade, dp[i] = power[i].

Otherwise, note that if we’re playing card i, we have never played a card with lower or equal cost. If there are no cards with less cost, dp[i] = power[i] again. Otherwise all of the cards with strictly lower cost have equal probability to be chosen as the next card. Let pref be the sum of dp’s of these cards and L be the number of them, dp[i] = power[i] + pref / L. Answer is dp of the imaginary card (The cost of this card is greater than the cost of any card in your deck, the power of this card is 0, and it does have cascade).

https://community.topcoder.com/stat?c=problem_solution&cr=22934070&rd=18345&pm=16622

TinyChessboardNim

Used as: Division One – Level Three:

Hint: as you desire, find which states are losing position.

Read Theorem 3 from this paper. Every needed proof is also present there. The remaining part is easy. Iterate on initial reachable states and count how many of them are losing positions. 

Just a note for reading the paper. In the paper, “P-position” means losing position.

Code by tourist:

int TinyChessboardNim::countWinningMoves(vector <int> rice) {
  auto Check = [&](int a, int b, int c, int d) {
    if (a != d) {
      swap(a, b);
      swap(c, d);
    }
    if (a != d) {
      return true;
    }
    bool flag = false;
    while (true) {
      if (b == c || a < abs(b - c)) {
        return flag;
      }
      int nb = a;
      int nc = a - abs(b - c);
      int na = min(b, c);
      a = na;
      b = nb;
      c = nc;
      flag = !flag;
    }
    assert(false);
    return false;
  };
  int a = rice[0];
  int b = rice[1];
  int c = rice[2];
  int d = rice[3];
  int ans = 0;
  for (int x = 1; x <= min(a, b); x++) if (!Check(a - x, b - x, c, d)) ++ans;
  for (int x = 1; x <= min(a, c); x++) if (!Check(a - x, b, c - x, d)) ++ans;
  for (int x = 1; x <= min(d, b); x++) if (!Check(a, b - x, c, d - x)) ++ans;
  for (int x = 1; x <= min(d, c); x++) if (!Check(a, b, c - x, d - x)) ++ans;
  return ans;
}