Single Round Match 710 Editorials
We are extremely excited and thankful to the community members who went ahead and contributed to the SRM 710 Editorials. Thanks to stni, Nickolas, jki14, lg5293
Below are the editorials that got submitted. You can reach out to the writers in the discussion forum.
Single Round Match 710 Round 1 - Division II, Level One MagicSubset by Nickolas
There are two options to get the subset which has the maximum sum: using stone 0 or not using it.
If we're not using stone 0, we're simply looking for the maximum sum of a subset of stones 1..n-1, which can be calculated using a greedy approach: pick every stone which has positive value, and discard every other stone.
If we're using stone 0, we're looking for the minimum value of (value of stone 0) plus sum of a subset of stones 1..n-1, which can be calculated in the same way, but picking only stones with negative values.
C++ solution follows:
#include <vector>
using namespace std;
class MagicSubset {
public:
int findBest(vector <int> values) {
int maxs = 0, mins = values[0];
for (int i = 1; i < values.size(); ++i) {
if (values[i] > 0)
maxs += values[i];
else
mins += values[i];
}
return max<int>(maxs, -mins);
}
};
Single Round Match 710 Round 1 - Division II, Level Two - ForwardMancala by stni
Let’s use brute force to play the turns in a while loop till the final state.
In this case we always choose the last non-zero slot, only slots labeled 1 to n-1 will be chosen, and their stones will reduce. Stones in slot 0 will only increase. So finally all stones will go to slot 0, which is the final state.
So worst case could be {0,1,1,1,...,1}, the complexity is 1+2+3+..+n, O(n^2).
Other cases are similar, e.g., always choose the first non-zero slot.
C++
#include<vector>
using namespace std;
class ForwardMancala{
public:
vector <int> findMoves(vector <int> start){
vector<int>ret;
while(1){
int count=0,index=-1;
for(int i=0;i<start.size();i++){
if(start[i]!=0){
count++;
index=i;
}
}
if(count==1){
return ret;
}
ret.push_back(index);
int selected=start[index];
start[index]=0;
for(int i=selected;i>0;i--){
start[(index+i)%start.size()]++;
}
}
return ret;
}
};
Single Round Match 710 Round 1 - Division II, Level Three - MinMaxMax by stni
Let's use Floyd–Warshall algorithm.
We will first sort all nodes by value v, so that the nodes we are going to traverse in Floyd–Warshall algorithm always have the largest v in the updated path.
Then in a for loop we traverse all nodes in the graph,
- We update all path weights in the graph using Floyd–Warshall, e.g., for path a->b, if max(weight a->k, weight k->b) smaller than previous weight a->b, which means we found a new path whose max value is smaller, we update weight a->b to max(weight a->k, weight k->b).
- If smaller v*weight exists ((updated weight of path passing k) * k.v is smaller) , we update the difficulty of the path.
We sum all difficulties in the graph and we will have the answer.
Overall time complexity is O(n^3).
C++
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
typedef long long ll;
const int N = 301;
struct node{
int v,id;
bool operator<(const node& n) const{
return v<n.v;
}
};
ll weight[N][N],difficulty[N][N];
class MinMaxMax{
public:
long long findMin(vector <int> a, vector <int> b, vector <int> w, vector <int> v){
ll ret=0;
int n=(int)v.size(),m=(int)a.size(),i,j,k,id_i,id_j,id_k;
vector<node>nodes;
for(i=0;i<n;i++){
nodes.push_back((node){v[i],i});
}
sort(nodes.begin(),nodes.end());
for(i=0;i<n;i++)
for(j=0;j<n;j++){
weight[i][j]=LONG_LONG_MAX,difficulty[i][j]=LONG_LONG_MAX;
}
for(i=0;i<m;i++)
weight[a[i]][b[i]]=weight[b[i]][a[i]]=w[i];
//Floyd–Warshall algorithm
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i!=j&&i!=k&&j!=k){
id_i=nodes[i].id;
id_j=nodes[j].id;
id_k=nodes[k].id;
/*
max edge weight of the best (minimum weight) path from id_i to id_j
by comparing the previous best path with the current one passing node k
*/
weight[id_i][id_j]=min(weight[id_i][id_j],max(weight[id_i][id_k],weight[id_j][id_k]));
}
}
}
for(i=0;i<=k;i++){
for(j=0;j<=k;j++){
id_i=nodes[i].id;
id_j=nodes[j].id;
if(weight[id_i][id_j]!=LONG_LONG_MAX){
/*
nodes[k].v bigger than previous v because we sorted nodes,
we update difficulty if
- weight[id_i][id_j] updated using path passing k
- the updated weight times the biggest node weight (node k weight) is the smallest
*/
difficulty[id_i][id_j]=min(difficulty[id_i][id_j],(ll)weight[id_i][id_j]*nodes[k].v);
}
}
}
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
ret+=difficulty[i][j];
return ret;
}
};
Single Round Match 710 Round 1 - Division I, Level One - ReverseMancala - jki14
Define int[] status to be an integer array describing the distribution of stones.
Define len(int[] status) to be the number of slots.
Define A(int pos) to be a type A move at position pos.
Define B(int pos) to be a type B move at position pos.
Define the operator * as a valid move on a status, for example:
status{ 6, 3, 4, 0 } * A(0) = status { 1, 5, 6, 1 }
status{ 1, 5, 6, 1 } * B(2) = status { 6, 3, 4, 0 }
Now, we can observe that the operations are inverses, namely:
status * A(pos) * B((pos+status[pos]) % len(status)) = status (0<=pos<len(status), status[pos]>0)
status * B((pos+status[pos]) % len(status)) * A(pos) = status (0<=pos<len(status), status[pos]>0)
" the type B move is a kind of inverse operation of the move of type A move, vise versa "
According to the conclusion above:
if:
status * A(pos1) * A(pos2) * ... * A(posm) = status'
then:
status = status' * B((posm+status[posm])%len(status)) * ... * B((pos2+status[pos2])%len(status)) * B((pos1+status[pos1])%len(status))
" With the conclusion above, we can construct a valid move sequence if we are able to find a key-status which is reachable with some valid moves from both start and finish. "
In my own solution, I defined the key-status to be the state where all slots from 0 to n-2 are empty, and all remaining stones are in slot n-1.
We can reach key-status from any status follow the operation sequence below:
Find the non-empty slot with smallest number, let the number be p
if p==n-1 then break the procedure, since it means the key-status is already reached
A(p), make a type A move from slot p
Loop back to step 1
After each type A move described in step 3, the slot p and all the slots numbered smaller than p will be empty or the status[n-1] will increase. We can also notice that status[n-1] will never decrease. So all status are able to reach key-status with less than (len(status)-1)*sum(status) times of type A move. Briefly, in worst case, there are at most 900 times of type A move.
" Thus, we can always generate a valid result by converting the start and the finish to key-status with the operation sequence and reversing the move from the finish to the key-status. "
#include "bits/stdc++.h"
using namespace std;
class ReverseMancala {
private:
void processA(vector<int> &arr, const unsigned int pos){
assert(pos<arr.size());
int foo=arr[pos];
arr[pos]=0;
for(unsigned int i=0; i<arr.size(); i++){
arr[i]+=foo/arr.size();
}
for(unsigned int i=1; i<=foo%arr.size(); i++){
arr[(pos+i)%arr.size()]++;
}
}
int toLast(vector<int> &arr, int *last=NULL){
for(unsigned int i=0; i<arr.size()-1; i++){
if(arr[i]>0){
if(last!=NULL){
*last=(i+arr[i])%arr.size();
}
this->processA(arr, i);
return i;
}
}
return -1;
}
public:
vector<int> findMoves(vector<int> start, vector<int> target){
vector<int> ans;
while(true){
int foo=this->toLast(start);
if(!~foo)break;
ans.push_back(foo);
}
stack<int> seq;
while(true){
int last;
int foo=this->toLast(target, &last);
if(!~foo)break;
seq.push(last);
}
for(; !seq.empty(); seq.pop()){
ans.push_back(start.size()+seq.top());
}
return ans;
}
};
Single Round Match 710 Round 1 - Division I, Level Two- MagicNim by lg5293
First, let's list some obvious winning and losing states.
All piles have 1 stone: Alice can always win by taking the magic stone and decide the winning condition based on partiy of the remaining stone.
XOR of all piles is equal to zero. Alice can take the magic stone and leave the victory condition alone.
Otherwise, if the xor is nonzero and there exists a pile with at least 2 stones, then it is not optimal to take the magic stone. Since winning conditions of misere and normal nim are the same when there exists a pile with at least 2 stones, you are passing a winning state to the other player by taking the magic stone. After checking those two cases, we can ignore the magic stone.
So, we are now playing a modified nim game, where we want to avoid making a move that leads the stones to one of the two configurations above. This should look similar to misere nim, but with some modifications.
This then becomes a game where a[i] is replaced by a[i]>>1, and the last player who takes a stone loses. This is misere nim. We can map moves in the original game to the reduced game by dividing by 2. There are some special cases. We can think about taking 1 stone from a pile with odd size as a "pass" move. Only the parity of pass moves matters, since our opponent can copy our pass moves. First, if the misere nim is a winning position for the current player, then they will win no matter what. If it is a losing position, then the current player can win if they have a pass move, and the resulting xor is nonzero. This only happens if all pile sizes are < 4. All this case analysis leads to a simple solution below.
Java code:
public class MagicNim {
public String findWinner(int[] a) {
return (Arrays.stream(a).max().getAsInt() <= 3 ? 2 : 1) != Arrays.stream(a).reduce(0, (x,y) -> x^y) ? "Alice" : "Bob";
}
}
Single Round Match 710 Round 1 - Division I, Level Three- Hyperboxes by lg5293
First, solve a more general version of the problem when k=1, but we also want certain pairs of hyperboxes to be intersecting (described by a bit-mask with (m choose 2) bits). To restate, for every 2^(m choose 2) choices of bitmasks, compute the number of ways to solve this problem in 1 dimension.
Two hyperboxes intersect if and only they intersect in every single dimension. Thus, they are disjoint if we take the bitwise and of all intersections of each dimension and it equals zero. This can be done efficiently with a Fast Walsh Hadamard transform.
Java code below:
public class Hyperboxes {
public static int mod = 998244353;
public static long[] inv;
static {
inv = new long[20];
inv[1] = 1;
for (int i = 2; i < inv.length; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
}
public long choose(long n, int k) {
if (k < 0 || k > n) return 0;
long ret = 1;
for (int i = 0; i < k; i++) { ret = ret * (n-i) % mod; ret = ret * inv[i+1] % mod; } return ret; } public int[] t = {0,1,3,6,10,15}; public int getBit(int i, int j) { if (j > i) {
int w = i; i = j; j = w;
}
return t[i-1] + j;
}
public boolean nextPermutation(int[] p) {
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1]) for (int b = p.length - 1; ; --b) if (p[b] > p[a]) {
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } public long mod_exp(long b, long e, long mod) { long res = 1; while (e > 0) {
if ((e & 1) == 1)
res = (res * b) % mod;
b = (b * b) % mod;
e >>= 1;
}
return res;
}
public int n,m,k;
public int[] f1;
public int[] f2;
public void dfs(int next, int closed, int groupopen, int pclosed, int intersections, int groups, long mult) {
if (next == m && closed == (1 << m) - 1) { f1[intersections] += choose(n, groups) * mult % mod; if (f1[intersections] >= mod) {
f1[intersections] -= mod;
}
return;
}
if (next < m) {
dfs(next + 1, closed, (1 << next), -1, intersections, groups + 1, mult);
if (pclosed == -1) {
dfs(next + 1, closed, groupopen | (1 << next), -1, intersections, groups, mult * inv[Integer.bitCount(groupopen) + 1] % mod);
}
}
// choose to close, continue same group
for (int x = pclosed+1; x < next; x++) { if (((closed>>x) & 1) == 1) continue;
if (((groupopen>>x) & 1) == 1) continue;
int ninter = intersections;
for (int w = 0; w < next; w++) { if (w != x && ((closed>>w) & 1) == 0) {
ninter |= 1 << getBit(x, w);
}
}
dfs(next, closed|(1<<x), groupopen, x, ninter, groups, mult);
}
// start different group
for (int x = 0; x < next; x++) { if (((closed>>x) & 1) == 1) continue;
int ninter = intersections;
for (int w = 0; w < next; w++) { if (w != x && ((closed>>w) & 1) == 0) {
ninter |= 1 << getBit(x, w);
}
}
dfs(next, closed|(1<<x), 0, x, ninter, groups+1, mult);
}
}
public void postprocess() {
int[] perm = new int[m];
for (int i = 0; i < m; i++) perm[i] = i;
for (int mask = 0; mask < 1 << t[m-1]; mask++) {
if (f1[mask] == 0) continue;
for (int i = 0; i < m; i++) perm[i] = i;
do {
int nmask = 0;
int c = 0;
for (int x = 0; x < m; x++) {
for (int y = 0; y < x; y++) { int target = getBit(perm[x], perm[y]); if (((mask>>c)&1) == 1)
nmask |= 1 << target; c++; } } f2[nmask] += f1[mask]; if (f2[nmask] >= mod) f2[nmask] -= mod;
} while (nextPermutation(perm));
} while (nextPermutation(perm));
}
public int findCount(int _n, int _m, int _k) {
n = _n; m = _m; k = _k;
f1 = new int[1<<t[m-1]];
// brute force m
// catalan(m) * m! * 2^(2m)
dfs(1, 0, 1, -1, 0, 1, 1);
// post process
// 2^(m choose 2) * m! * m
f2 = new int[1<<t[m-1]]; postprocess(); // FWT // (m choose 2) * 2^(m choose 2) int levels = 31-Integer.numberOfLeadingZeros(f2.length); int len = f2.length; for (int i = levels-1; i >= 0; i--) {
for (int j = 0; j < len; j++) { if (((j>>i)&1) == 0) {
f2[j] = (f2[j] + f2[j|(1<<i)]) % mod;
}
}
}
for (int i = 0; i < len; i++) {
f2[i] = (int)mod_exp(f2[i], k, mod);
}
for (int i = 0; i < levels; i++) {
for (int j = 0; j < len; j++) { if (((j>>i)&1) == 0) {
f2[j] = (f2[j] - f2[j|(1<<i)] + mod) % mod;
}
}
}
return f2[0];
}
}