Single Round Match 770 Editorials
misof · SRM Editorials
MaximumMoves
Used as: Division Two - Level One:
Value
250
Submission Rate
195 / 237 (82.28%)
Success Rate
94 / 195 (48.21%)
High Score
kshitij_sodani for 246.76 points (3 mins 15 secs)
Average Score
202.98 (for 94 correct submissions)
Every number greater than 1 can be written using the sum of several twos and threes, for example, 7 = 2 + 2 + 3. The number n, needs n / 2 (rounded down) summands. For example, 7 needs 3 summands. 20 needs 10 summands.
If p > q or q - p = 1, the answer is -1. Else, the answer is (q - p) / 2 (rounded down).
def getMaximumMoves(self, p, q):
if pq:
return -1
if p==q:
print(0)
d=q-p
if d==1:
return -1
if d%2==0:
return d//2
else:
return d//2
LayeredGlass
Used as: Division Two - Level Two:
Value
500
Submission Rate
116 / 237 (48.95%)
Success Rate
87 / 116 (75.00%)
High Score
yongwhan for 436.60 points (11 mins 9 secs)
Average Score
287.84 (for 87 correct submissions)
Each glass has 2 options to flip or not to flip and 4 options to rotate. We check each of the options for each glass and find the minimum. Note that we can skip 4 options of rotation of one of the glasses.
Here is the code (by cntswj):
def rotate(self, a):
n = len(a)
ret = [[None] * n for _ in range(n)]
for i in range(n):
for j in range(n):
ret[j][n - i - 1] = a[i][j]
ret = [''.join(row) for row in ret]
return ret
def flip(self, a):
n = len(a)
ret = [[None] * n for _ in range(n)]
for i in range(n):
for j in range(n):
ret[i][j] = a[i][n - j - 1]
ret = [''.join(row) for row in ret]
return ret
def check(self, a, b):
n = len(a)
ret = 0
for i in range(n):
for j in range(n):
if a[i][j] == 'X' or b[i][j] == 'X':
ret += 1
return ret
def minDefects(self, a, b):
n = len(a)
ret = n * n
for _ in range(2):
for _ in range(4):
ret = min(ret, self.check(a, b))
b = self.rotate(b)
b = self.flip(b)
return ret
DeleteArrays
Used as: Division Two - Level Three:
Value
900
Submission Rate
15 / 237 (6.33%)
Success Rate
5 / 15 (33.33%)
High Score
taran_1407 for 481.22 points (33 mins 24 secs)
Average Score
431.97 (for 5 correct submissions)
Used as: Division One - Level One:
Value
300
Submission Rate
110 / 167 (65.87%)
Success Rate
89 / 110 (80.91%)
High Score
Petr for 245.04 points (14 mins 7 secs)
Average Score
168.45 (for 89 correct submissions)
Let’s solve the problem case by case:
One of the arrays is longer than the sum of the length of the other arrays.Consider this array be A, sort A, some of the first elements of A will remain and others will be deleted using the first and third type of move.
The total number of elements is odd.An element will remain, the smallest element of an array.
The general case.Note that the number of moves we should do on a particular type of move is fixed. For example, consider a = b = c = 4. We must use the first, second, and, third type of move 2 times each.In fact, we should solve a system of equations with three variables.
The following code uses the NumPy library to solve the system of equations (by wilkluka).
def doDelete(self, a, b, c, x, y, z):
A = [33, 42]
for i in xrange(2, a):
A.append((5 * A[i - 1] + 7 * A[i - 2]) % 1000000007 + 1)
B = [13]
for i in xrange(1, b):
B.append((11 * B[i - 1]) % 1000000007 + 1)
C = [7, 2]
for i in xrange(2, c):
C.append((5 * C[i - 1] + 7 * C[i - 2]) % 1000000007 + 1)
mm = 0
aa = len(A)
bb = len(B)
cc = len(C)
if aa bb+cc:
A.sort()
n = aa-bb-cc
mm = sum(A[:n])
A = A[n:]
elif bb aa + cc:
B.sort()
n = bb - aa - cc
mm = sum(B[:n])
B = B[n:]
elif cc aa + bb:
C.sort()
n = cc - aa - bb
mm = sum(C[:n])
C = C[n:]
if (len(A) + len(B) + len(C)) % 2 == 1:
mm = min(A)
cost = x + z
tb = A
if (mm == min(B) and cost < x + y) or (mm min(B)):
mm = min(B)
cost = x + y
tb = B
if (mm == min(C) and cost < y + z) or (mm min(C)):
mm = min(C)
cost = z + y
tb = C
tb.remove(mm)
a = np.array([[1, 1, 0], [0, 1, 1], [1, 0, 1]])
b = np.array([len(A), len(B), len(C)])
solutions = np.linalg.solve(a, b).astype(int)
return mm, (solutions * np.array([z, x, y])).sum() + sum(A) + sum(B) + sum(C)
And a c++ code (by ecnerwal):
vector<long long doDelete(int NA, int NB, int NC, long long wx, long long wy, long long wz) {
vector<ll A(NA);
vector<ll B(NB);
vector<ll C(NC);
A[0] = 33;
A[1] = 42;
for (int i = 2; i <= NA-1; i++) {
A[i] = (5*A[i-1] + 7*A[i-2]) % 1000000007 + 1;
}
B[0] = 13;
for (int i = 1; i <= NB-1; i++) {
B[i] = (11*B[i-1]) % 1000000007 + 1;
}
C[0] = 7;
C[1] = 2;
for (int i = 2; i <= NC-1; i++) {
C[i] = (5*C[i-1] + 7*C[i-2]) % 1000000007 + 1;
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
vector<ll V[3];
V[0] = A;
V[1] = B;
V[2] = C;
int N[3];
N[0] = NA;
N[1] = NB;
N[2] = NC;
ll W[3][3];
memset(W, 0, sizeof(W));
W[0][1] = W[1][0] = wx;
W[1][2] = W[2][1] = wy;
W[0][2] = W[2][0] = wz;
ll S = 0;
for (int z = 0; z < 3; z++) {
for (int i = 0; i < N[z]; i++) {
S += V[z][i];
}
}
for (int z = 0; z < 3; z++) {
int x = (z+1)%3, y = (z+2) % 3;
if (N[z] = N[x] + N[y]) {
ll ans = 0;
for (int i = 0; i < N[z] - N[x] - N[y]; i++) {
ans += V[z][i];
}
return {ans, N[x] * W[z][x] + N[y] * W[z][y] + (S - ans)};
}
}
int s = (N[0] + N[1] + N[2]) / 2;
if ((N[0] + N[1] + N[2]) & 1) {
vector<ll ans;
for (int z = 0; z < 3; z++) {
int x = (z+1)%3, y = (z+2) % 3;
vector<ll cnd({V[z][0], W[x][y] * (s - (N[z]-1)) + W[y][z] * (s - N[x]) + W[x][z] * (s - N[y]) + (S - V[z][0])});
if (z == 0) {
ans = cnd;
} else {
ans = min(ans, cnd);
}
}
return ans;
} else {
return {0, W[0][1] * (s - N[2]) + W[1][2] * (s - N[0]) + W[2][0] * (s - N[1]) + S};
}
}
ShoppingSpree
Used as: Division One - Level Two:
Value
450
Submission Rate
79 / 167 (47.31%)
Success Rate
42 / 79 (53.16%)
High Score
Stonefeang for 424.48 points (7 mins 3 secs)
Average Score
315.28 (for 42 correct submissions)
The problem is similar to find maximum-weight matching in bipartite graphs (solve it before continuing). One of the methods for solving the problem is to use minimum cost flow (read the article before you continue).
For each vertex like v, the first time we choose an edge which connects v to another vertex, we gain value of it, but next times we gain nothing.
So, here is the edges we should add:
Source to every shirt. Cost = -shirtValue[i]. Capacity = 1.
Source to every shirt. Cost = 0. Capacity = infinity.
Every jean to sink. Cost = -jeanValue[i]. Capacity = 1.
Every jean to sink. Cost = 0. Capacity = infinity.
shirtType[i] to jeansType[i]. Cost = 0. Capacity = infinity.
Now when we calculate the minimum cost, it’s the answer. Three notes:
We can use k instead of infinity.
We should limit the initial flow from source to k.
We want to use the maximum gain but the algorithm calculates the minimum cost flow, so we need to set negative costs.
// flow part
struct kra {
int cel, *prze1, *prze2;
ll koszt;
};
int n=0, zr, uj;
const ll inf=1e9;
vector <vector <kra graf;
vector <int bylo, aktu;
vector <ll odl, pamodl;
void vert(int v) {
if (vn) {
n=v;
graf.resize(n);
bylo.resize(n);
aktu.resize(n);
odl.resize(n);
pamodl.resize(n);
}
}
void add_edge(int v, int u, int prze, ll koszt) {
vert(v+1); vert(u+1);
kra ret1{u, new int(prze), new int(0), koszt};
kra ret2{v, ret1.prze2, ret1.prze1, -koszt};
graf[v].push_back(ret1);
graf[u].push_back(ret2);
}
void spfa() {
for (int i=0; i<n; i++) {
aktu[i]=1;
pamodl[i]=inf;
}
aktu[zr]=pamodl[zr]=0;
queue <int kol;
kol.push(zr);
while(!kol.empty()) {
int v=kol.front();
kol.pop();
if (aktu[v])
continue;
aktu[v]=1;
for (kra i : graf[v]) {
if (*i.prze1 && pamodl[v]+i.koszt<pamodl[i.cel]) {
pamodl[i.cel]=pamodl[v]+i.koszt;
aktu[i.cel]=0;
kol.push(i.cel);
}
}
}
}
void dij() {
for (int i=0; i<n; i++)
odl[i]=inf;
priority_queue < pair <ll,int dijks;
dijks.push({0, zr});
while(!dijks.empty()) {
ll dis=-dijks.top().first;
int v=dijks.top().second;
dijks.pop();
if (odl[v]!=inf)
continue;
odl[v]=pamodl[v]+dis;
for (auto j : graf[v])
if ((*j.prze1) && odl[j.cel]==inf)
dijks.push({-(dis+pamodl[v]-pamodl[j.cel]+j.koszt), j.cel});
}
}
int dfs(int v) {
if (v==uj)
return 1;
bylo[v]=1;
for (int i=0; i<(int)graf[v].size(); i++) {
if (!bylo[graf[v][i].cel] && (*graf[v][i].prze1) &&
odl[v]+graf[v][i].koszt==odl[graf[v][i].cel] && dfs(graf[v][i].cel)) {
(*graf[v][i].prze1)--;
(*graf[v][i].prze2)++;
return 1;
}
}
return 0;
}
pair <int,ll flow(int zrzr, int ujuj, int moge) {
zr=zrzr; uj=ujuj;
vert(zr+1); vert(uj+1);
spfa();
pair <int,ll ret{0, 0};
for (int i=0; i<moge; i++) {
//~ dij();
spfa();
odl=pamodl;
for (int i=0; i<n; i++)
bylo[i]=0;
if (!dfs(zr))
break;
ret.first++;
ret.second+=odl[uj];
}
return ret;
}
};
// end of flow part
struct ShoppingSpree
{
int maxValue(int k, vector <int shirtValue, vector <int jeansValue, vector <int shirtType, vector <int jeansType)
{
MinCost pawel;
int n=shirtValue.size();
int m=jeansValue.size();
int d=shirtType.size();
for (int i=0; i<n; i++)
{
pawel.add_edge(0, i+1, 1, -shirtValue[i]);
pawel.add_edge(0, i+1, k, 0);
}
for (int i=0; i<m; i++)
{
pawel.add_edge(n+1+i, n+m+1, 1, -jeansValue[i]);
pawel.add_edge(n+1+i, n+m+1, k, 0);
}
for (int i=0; i<d; i++)
{
pawel.add_edge(1+shirtType[i], n+1+jeansType[i], k, 0);
}
return -pawel.flow(0, n+m+1, k).second;
}
};
Used as: Division One - Level Three:
Value
900
Submission Rate
20 / 167 (11.98%)
Success Rate
12 / 20 (60.00%)
High Score
bqi343 for 758.95 points (12 mins 44 secs)
Average Score
560.09 (for 12 correct submissions)
We add zero to the array and sort it at the first. Refer to this link next. The problem can be solved in the same way. Let’s calculate P(MAX < x), the probability that maximum (MAX) be less than x.
Note that P(MAX < x) is a piecewise function. For a[i] < x < a[i + 1],
Note that array is zero-based and the function above just works in range (a[i], a[i + 1]).
Let’s calculate the mathematical expectation (in the range (a[i], a[i + 1])):
auto A = Aprefix;
ll state = seed;
while (sz(A) < n) {
state = (1103515245 * state + 12345) % (1LL<<31);
A.pb(T+(state%Amod));
}
A.pb(0);
sort(all(A));
ld ans = A.back();
ld prod = 1;
ROF(i,1,sz(A)) {
int k = sz(A)-i;
ld p1 = A[i]*prod; // two zeroes?
ld p2 = 0;
if (A[i] != 0) {
prod *= pow((ld)A[i-1]/A[i],k);
p2 = A[i-1]*prod;
}
ans -= (p1-p2)/(k+1);
}
return ans;