## 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:

Value | 250 |

Submission Rate | 72 / 82 (87.80%) |

Success Rate | 47 / 72 (65.28%) |

High Score | lynmisakura for 244.26 points (4 mins 22 secs) |

Average Score | 194.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:

Value | 500 |

Submission Rate | 37 / 82 (45.12%) |

Success Rate | 26 / 37 (70.27%) |

High Score | Geothermal for 472.73 points (6 mins 54 secs) |

Average Score | 305.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:

Value | 1000 |

Submission Rate | 9 / 82 (10.98%) |

Success Rate | 1 / 9 (11.11%) |

High Score | jackylove for 389.41 points (38 mins 56 secs) |

Average Score | 389.41 (for 1 correct submission) |

Used as: Division One – Level One:

Value | 250 |

Submission Rate | 77 / 82 (93.90%) |

Success Rate | 30 / 77 (38.96%) |

High Score | Petr for 242.71 points (4 mins 57 secs) |

Average Score | 160.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:

Value | 500 |

Submission Rate | 33 / 82 (40.24%) |

Success Rate | 28 / 33 (84.85%) |

High Score | ecnerwal for 458.67 points (8 mins 41 secs) |

Average Score | 340.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:

Value | 1000 |

Submission Rate | 6 / 82 (7.32%) |

Success Rate | 4 / 6 (66.67%) |

High Score | tourist for 785.21 points (15 mins 47 secs) |

Average Score | 577.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; }

**a.poorakhavan**

Guest Blogger