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:

Value250
Submission Rate72 / 82 (87.80%)
Success Rate47 / 72 (65.28%)
High Scorelynmisakura for 244.26 points (4 mins 22 secs)
Average Score194.08 (for 47 correct submissions)

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:

Value500
Submission Rate37 / 82 (45.12%)
Success Rate26 / 37 (70.27%)
High ScoreGeothermal for 472.73 points (6 mins 54 secs)
Average Score305.66 (for 26 correct submissions)

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:

Value1000
Submission Rate9 / 82 (10.98%)
Success Rate1 / 9 (11.11%)
High Scorejackylove for 389.41 points (38 mins 56 secs)
Average Score389.41 (for 1 correct submission)

Used as: Division One – Level One:

Value250
Submission Rate77 / 82 (93.90%)
Success Rate30 / 77 (38.96%)
High ScorePetr for 242.71 points (4 mins 57 secs)
Average Score160.26 (for 30 correct submissions)

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:

Value500
Submission Rate33 / 82 (40.24%)
Success Rate28 / 33 (84.85%)
High Scoreecnerwal for 458.67 points (8 mins 41 secs)
Average Score340.22 (for 28 correct submissions)

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:

Value1000
Submission Rate6 / 82 (7.32%)
Success Rate4 / 6 (66.67%)
High Scoretourist for 785.21 points (15 mins 47 secs)
Average Score577.93 (for 4 correct submissions)

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;
}


Guest Blogger


categories & Tags


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