SRM_Blog
SRM Editorials

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 

V7CIU0ogPMTN803Udlgyxr8BC-OpEZPbKQrUc1-kagk0bqQuam20o8Ybn8G33K-593okOkG6naRPXJOiUT0lwvbTzWgdFmoxekWsCdREgQIKvhmh9WG4N5erHW-XGrZ_zHmP8Smv

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