Well, SEATST concluded again last week, on Sunday. It was my second TST, and I started off at #16, and ending off with #11. The tasks were quite good. You can solve the problems here: Problems
Congratulations to Tyx2019 blackscreen1 gelastropod jatro13 for making into the team! Orz to literalchild for being the only person who got FC.
I will add on the remaining problems when I feel like doing it.
By the way, my score distribution was as follows:
For the code, don't mind the terrible indentation. It is probably because I use tab by default, and the code given uses 2 spaces. I may have accidentally changed it to 4 spaces for some of these pieces of code. So indentation may be really funny. Sorry.
It initially felt like a classic problem. 15 minutes in, I found a $$$O(N^2)$$$ solution, using vector insertion. The solution is as follows:
We process the $$$N$$$ students one by one. Store the current vector of the current relative order of the already processed students. Then, we attempt to insert the next student at the correct position.
Observation: If you process a student, if it is not inserted at the back, then it cannot have the highest $$$P[i]-i$$$.
Proof: Consider the element right after $$$i$$$ in the final array $$$P$$$. It will always be larger.
Observation: When processing a student, it is always better to always put the student with the highest possible $$$P[i]$$$.
Proof: When you insert at a position $$$k$$$, then all the $$$P[x]$$$ at positions $$$k, k+2, \dots, i-1$$$ will increment by 1. Thus, by keeping it as right as possible, we increase the minimum number of such positions. Although if you were to insert at a lower position, the value of $$$P[i]-i$$$ is small, but it cannot be the largest.
So, we can linear scan for the largest position you can put in: You can only put it in a location such that either all of the $$$A[x]$$$ before it are less, or all the $$$B[x]$$$ before it are less. Then, you can insert it in in $$$O(N)$$$ time using std::vector::insert.
Overall time complexity: $$$O(N^2)$$$.
vector<int> ans;
for (int i = 0; i < N; i++) {
int best = -1;
for (int j = 0; j < ans.size(); j++) {
if (A[ans[j]] < A[i]) best = max(best, j);
else break;
}
for (int j = 0; j < ans.size(); j++) {
if (B[ans[j]] < B[i]) best = max(best, j);
else break;
}
ans.insert(ans.begin()+best+1, i);
}
int a = 0; for (int i = 0; i < N; i++) a = max(a, i-ans[i]);
return a;
Now, we can make better use of the first observation to avoid the bottleneck of insertions (Because the scan can be done in $$$O(\log N)$$$ time using a segment tree).
We can instead only store the points that are the new largest values. Then, when processing an element, perform binary search on a segment tree to find the correct position where it can be "inserted". If this element is not at the end, notice that to accommodate for this new element, is equivalent to a point update to the segment tree, and a range increment to the values of $$$P[i]-i$$$. Otherwise, it is just add it to the end.
This gives time complexity $$$O(N \log N)$$$. This gets you 83 points, which was the score I got in contest.
#include <bits/stdc++.h>
using namespace std;
struct node {
int s,e;
int m;
node *l, *r;
int val=0;
//range update
int lazy=0;
int a, b;
//range max for val
node (int _s, int _e) {
s = _s; e = _e;
m = s+(e-s)/2;
a = -1;
b = -1;
if (s!=e) l = new node(s,m), r = new node(m+1,e);
}
void upd(int n, int x, int y) {
if (s==e) {
a = max(a,x);
b = max(b,y);
return;
}
prop();
if (n<=m) l->upd(n,x,y);
else r->upd(n,x,y);
a = max(l->a, r->a);
b = max(l->b, r->b);
val = max(l->val, r->val);
}
void prop() {
l->val += lazy;
r->val += lazy;
l->lazy += lazy;
r->lazy+=lazy;
lazy = 0;
}
int find1(int x) {
if (s==e) return s;
prop();
if (l->a > x) return l->find1(x);
else return r->find1(x);
}
int find2(int x) {
if (s==e) return s;
if (l->b > x) return l->find2(x);
else return r->find2(x);
}
int qry(int x, int y) {
if (x<=s and y>=e) return val;
prop();
if (y<=m) return l->qry(x,y);
else if (x>=m+1) return r->qry(x,y);
else return max(l->qry(x,m), r->qry(m+1,y));
}
void inc(int x, int y) {
if (x<=s and y>=e) {val ++; lazy++;return;}
prop();
if (y<=m) l->inc(x,y);
else if (x>=m+1) r->inc(x,y);
else l->inc(x,m), r->inc(m+1,y);
val = max(l->val, r->val);
}
};
int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B) {
int x = -1;
int y = -1;
node *root = new node(-1, N);
int idx = 0;
for (int i = 0; i < N; i++) {
if (A[i] > x || B[i] > y) {
//append
root->upd(idx, A[i], B[i]);
idx++;
x = max(A[i], x);
y = max(B[i],y);
}
else {
int id = max(root->find1(A[i]), root->find2(B[i]));
//cout << id << '\n';
root->inc(id, idx-1);
//cout << id << '\n';
if (id != idx) {
root->upd(id, A[i], B[i]);
}
x = max(A[i], x);
y = max(B[i], y);
}
//for (int j = 0; j < N; j++) cout << root->qry(j,j) << ' ';
//cout << '\n';
}
return root->qry(0, idx-1);
}
Yes, this is much longer than the AC solution.
Realize that there is not a need to process from the front. Instead, we can process from the back! Here, we make the key observation:
Observation: The last person must have the highest $$$A[i]$$$ or $$$B[i]$$$ among the first $$$i$$$.
Why am I restating the problem condition? Just stimulate this from the back, line sweeping to ensure that you don't accidentally reach one that has already been taken. There, you would take the larger index, as the smaller would give a larger $$$P[i]-i$$$. This runs in $$$O(N)$$$ time. In fact, the solution code is less than 20 lines long.
int takenA[N],takenB[N],invA[N],invB[N];
memset(takenA,0,sizeof(takenA));
memset(takenB,0,sizeof(takenB));
for (int i = 0; i < N; i++) invA[A[i]]=i, invB[B[i]]=i;
int ptr1=N-1,ptr2=N-1;
int ans=0;
for (int i = N-1; i>=0;i--) {
while (ptr1>=0 && takenA[ptr1]) ptr1--;
while (ptr2>=0 && takenB[ptr2]) ptr2--;
int best = -1;
if (ptr1 != -1) best=invA[ptr1];
if (ptr2 != -1 && invB[ptr2] > best) best=invB[ptr2];
if (i-best > ans) ans=i-best;
takenA[A[best]]=1;
takenB[B[best]]=1;
}
return ans;
Note that you may need constant optimization, as $$$N$$$ is large.
Very weirdly, in contest, I tried coding minimum excluded from the start. (While AC is just maximum excluded from the back, note the resemblance.) This was sadly because of a careless mistake with working on the sample testcases, where I actually tried this algorithm and started to confuse myself, causing myself to reject this. This was another unfortunate circumstance of me confusing myself during contest resulting in not solving. (First was in NOI this year, confusing myself with very unorganized inequalities) I guess I should be more careful next time (or even just code it, it's like 3 line modification from my MEX sol).
When I first saw this, I actually thought the statement was funny.
I find it even funnier that we can apply this to the overall SEATST scoreboard.
This problem is a 2-part problem — first is to count the number that must be together, and the second is to count the number that can be together. (Where together means from the same country).
We will first do the first part.
Observation 1: If $$$A$$$ must be with $$$B$$$ and $$$B$$$ must be with $$$C$$$, then $$$C$$$ must be with $$$A$$$. Thus, it is only required for us to consider those of ranking $$$k-1$$$ if the ranking you are currently processing is $$$k$$$.
Then, we are essentially trying to create a matching between those with ranking $$$k-1$$$ and ranking $$$k$$$. We can first store all the possible indices that could be unmatched. Hence, if they have the same cardinality then the matching must involve all elements. Hence, we can conveniently kill off these elements with ranking $$$k-1$$$. Otherwise, there exists a possible construction involving any of the elements, so if the size is larger than 1, nothing is forced, but if size is 1, then they must be together. We can use a UFDS/DSU to store the matchings.
This gives $$$O(N)$$$ or $$$O(N\alpha (N))$$$ or $$$O(N\log N)$$$.
long long count_same_country(int N, std::vector<int> country_rank) {
vector<int> cand[N];
long long ans = 0;
int take[N]; memset(take,0,sizeof(take));
for (int rank:country_rank) {
if (rank == 0) cand[0].push_back(1);
else {
int cur = 0;
if (cand[rank-1].size() == 1) cur = cand[rank-1][0];
ans += cur;
take[rank-1]++;
if (take[rank-1] == cand[rank-1].size()) {
take[rank-1]=0; cand[rank-1]={};
}
cand[rank].push_back(cur+1);
}
}
return ans;
}
This idea can be brought into part 2 too, but there are more details you need to care about. Now, we should instead draw a directed graph where each node with ranking $$$k$$$ will point to the set of nodes of ranking $$$k-1$$$ that it can match with, using a similar idea to the first part. Then, the set of nodes that a certain node can be together will be the set of nodes connected to it. Thus, by running BFS on this, and processing the students in order, we can get a $$$O(N^3)$$$ solution. This was what I managed to get in contest. (And stitching the subtask where there is no one of rank 2, it is the exact same idea). This somehow gets $$$N\leq 2000$$$ as it probably has a decent constant.
long long count_diff_country(int N, std::vector<int> country_rank) {
vector<int> cand[N];
int take[N]; memset(take,0,sizeof(take));
int con[N][N]; memset(con,0,sizeof(con));
vector<int> visit[N];
for (int i = 0; i < N; i++) {
int rank = country_rank[i];
if (rank == 0) cand[0].push_back(i);
else {
for (auto x:cand[rank-1]) visit[i].push_back(x), con[i][x]=1;
take[rank-1]++;
if (take[rank-1] == cand[rank-1].size()) {
take[rank-1]=0; cand[rank-1]={};
}
cand[rank].push_back(i);
}
}
for (int i = 0; i < N; i++) {
int sz = visit[i].size();
for (int j = 0; j < sz; j++) {
for (auto y:visit[visit[i][j]]) {
if (con[i][y] == 0) {
con[i][y] = 1;
visit[i].push_back(y);
}
}
}
}
long long ans = 0;
for (int i = 0; i < N; i++) ans += visit[i].size();
long long n = N;
return n*(n-1)/2-ans;
}
This code looks like $$$O(N^3)$$$, but I am quite sure the constant is decent.
Consider the worst case scenario, which this code runs on, which is clearly $$$n$$$ 0s, then $$$n$$$ 1s, and so on, until $$$n$$$ values of some $$$k$$$. In this case, $$$nk \leq N$$$. On each node with rank $$$i$$$, it will run $$$n(i-1)n$$$ such operations. ($$$n$$$ edges, and each has $$$(i-1)n$$$ such neighbors). So, the total is $$$n^3(1+2+\dots+k-1)=O(n^3k^2)$$$..? So indeed this is a $$$O(N^3)$$$ solution. Running on a few of these values of $$$n$$$, it turns out that they all run comfortably below 200ms.
Now, this can be sped up by considering that the nodes a student can be connected to and the nodes another student with the same ranking are connected to are very close together. If you store the number of nodes that you can visit but not the previous student with the same ranking, then the final result can be easily computed. By maintaining both values, this can be cut to $$$O(N)$$$.
Final complexity: $$$O(N)$$$.
long long count_diff_country(int N, std::vector<int> country_rank) {
vector<int> cand[N]; //now this stores the number connected to each candidate
int notincl[N]; memset(notincl,0,sizeof(notincl)); // number of connected to each layer without the previous of i+1.
int lastguy[N]; memset(lastguy,0,sizeof(lastguy));
int take[N]; memset(take,0,sizeof(take));
long long ans = 0;
for (int rank:country_rank) {
if (rank == 0) cand[0].push_back(0), notincl[0]++;
else {
int newtotal = lastguy[rank]+notincl[rank-1];
notincl[rank] += notincl[rank-1]+1;
notincl[rank-1] = 0;
take[rank-1]++;
lastguy[rank] = newtotal;
if (take[rank-1] == cand[rank-1].size()) {
take[rank-1]=0; cand[rank-1]={};
lastguy[rank] = lastguy[rank-1];
}
ans += newtotal;
cand[rank].push_back(newtotal);
}
}
long long n = N;
return n*(n-1)/2-ans;
}
I had managed to tunnel-vision how simply you can just store the difference instead. I was hard thinking about how to have a difference function that can be adjusted due to the UFDS. So I guess, this is me getting too sucked into the UFDS rabbit hole. Oopsies.
I am still very unhappy that I didn't manage to AC this problem. Maybe I should go back and code binary search.
Observation 1: The worst assignment means that the furthest person gets the highest $$$C[i]$$$, and that the second furthest gets the second largest $$$C[i]$$$, etc. This can be easily seen by exchange argument.
Essentially, the easiest way to play around with this problem is to see how the answers change at different indices. If you were to sketch a graph of positions against the cost, you realize that it turns out to be convex piecewise function.
You can perform ternary search on this function for a $$$O(N \log 2e9)$$$ solution. There is a way to AC from this point by calculating worst(p) in $$$O(C\log 2e9\log N)$$$. However, I will discuss the solution I found instead.
Rather than assigning some cost to the cars one by one, we consider sweeping by $$$C[i]$$$ instead. Suppose that there are $$$K[i]$$$ such $$$C[i]$$$ where $$$C[i] \geq i$$$, then we can make it such that $$$K[1]$$$ cars have cost 1, then make $$$K[2]$$$ of these $$$K[1]$$$ cars have cost 2, and so on. This can be motivated by the strange $$$C[i] \leq 100$$$ condition. How is this useful?
Observation 2: Instead of incrementing $$$K[i]$$$ points that is a subset of $$$K[i-1]$$$, it suffices to consider incrementing $$$K[i]$$$ points.
This is because at a certain point, those incremented by $$$K[i-1]$$$ must already be the furthest $$$K[i-1]$$$ such points. The furthest $$$K[i]$$$ points must be a subset of these $$$K[i-1]$$$ points anyway, and hence cannot be any point that is not taken.
Now, this whole question simplifies to solving $$$C[i]\leq 1$$$ 100 times.
Observation 3: You can start with initial position to be $$$-\infty$$$. Then, as you slide to the right, the answer changes by the number of 1s to the right, subtracting the number of 1s to the left.
Observation 4 (Reallocating the locations of the 1s): Suppose that there are $$$x$$$ elements having $$$C[i]=1$$$ as prefix, and $$$y$$$ elements having $$$C[i]=1$$$ as the suffix. ($$$x+y=K[1]$$$), then the next location where this allocation will change is then the $$$x+1$$$th element is further to the point than the $$$y$$$th last element. Hence, there are at most $$$N$$$ such "Changing points".
It is now obvious that the best thing to try is to apply slope trick on this. It suffices to find the first point with slope $$$\geq 0$$$. And, the slope changing points is the average of the 2 points considered in observation 4. Note that the slope will change by 2.
However, this would also imply that you would need to store "slope changing points" at non-integer coordinates. One way to get around this is that if $$$x$$$ is the slope changing point and $$$x\not\in\mathbb{Z}$$$, then you can set the slopes to be $$$\lfloor x\rfloor$$$ and $$$\lceil x \rceil$$$, as the fractional part of $$$x$$$ is 0.5.
This would give a $$$O(N \max(C[i]) \log(N\max C[i]))$$$ solution, and 64 points. This was what I managed to get in contest.
int counts[101]; for (int i = 0; i < 101; i++) counts[i] = 0;
for (int i = 0 ;i < N; i++) counts[C[i]]++;
for (int i = 99; i >= 0; i--) counts[i] += counts[i+1];
//store the slopes time
vector<long long> slopes;
//initially its all 0.
long long initialslope = 0;
for (int i = 1; i <= 100; i++) {
initialslope -= counts[i];
for (int j = 1; j <= counts[i]; j++) {
//you have j on the left, counts[i]-j on the right
int n = X[j-1]+X[N-(counts[i]+1-j)];
if (n%2==0) {
slopes.push_back(n/2);
slopes.push_back(n/2);
}
else {
if (n>0) {
slopes.push_back(n/2);
slopes.push_back(n/2+1);
}
else {
slopes.push_back(n/2);
slopes.push_back(n/2-1);
}
}
}
}
sort(slopes.begin(), slopes.end());
for (auto i:slopes) {
initialslope++;
if (initialslope == 0) return i;
}
return -100;
Beware of negative numbers integer division. Quite a few people could not fix their bugs due to this.
So now, we want to essentially remove having to store all of the slope changing points. Thus, it may be a good idea to binary search for the correct one, each time counting the number of slope changing points before it. However, realize that for each layer, you can again count the number of slope changing points before it through another binary search. Beware of negative numbers, and odd numbers. It may be useful to stress test this with the previous solution with just storing the slope changing points.
Final time complexity: $$$O(N+\max(C[i])\log 2e9 \log N)$$$, with essentially negligible constant.
int find(int N, vector<int>& X, int c, int m) {
int l2 = -1;
int h2 = c;
while (h2 - l2 > 1) {
int m2 = (h2 + l2) / 2;
int n = X[m2] + X[N - c + m2];
if (n <= m) l2 = m2;
else h2 = m2;
}
return h2;
}
int car_gathering(int N, vector<int> X, vector<int> C) {
int counts[101]; memset(counts,0,sizeof(counts));
for (int i = 0; i < N; i++) counts[C[i]]++;
for (int i = 99; i >= 0; i--) counts[i] += counts[i + 1];
long long initialSlope = 0;
for (int i = 1; i <= 100; i++) initialSlope -= counts[i];
int l = -1e9-10, h = 1e9+10;
while (h-l > 1) {
int m = l+(h-l)/2;
long long cur = 0;
for (int i = 1; i <= 100; i++) {
cur += find(N, X, counts[i], 2*m);
cur += find(N, X, counts[i], 2*m + 1);
// You want floor(n / 2) and ceil(n / 2)
// floor(n / 2) <= m
// ceil(n / 2) <= m
// floor(n / 2) <= m -> n <= 2m + 1
// ceil(n / 2) <= m -> n <= 2m
}
if (cur + initialSlope >= 0) h = m;
else l = m;
}
return h;
}
I am extremely unhappy that I did not get the AC on this one. I had coded the binary search for 1.5 hours, and I just couldn't get one detail right (which was when there are indeed a lot of equal car locations, and the positions are odd). :(
Personally, there should be a subtask where all car locations are even to make people getting this detail wrong still attain some points.
I was especially excited when I found the slope trick idea — I knew that I would get something very close to AC very soon. Little did I know binary search would screw me over. Very disappointing that I did not get it. I don't know why, lately I keep getting screwed over by binary search, having been screwed over by JOISC teleporter2 just a few weeks prior.
The solutions for 1C: XOR Teleport and 2A: Triple Circuit have been shared in the comments. Thus, I will only share my thoughts in contest.
This problem initially looked kind of scary, compared to 1A and 1B. Indeed, I realized that I had to deal with the troublesome task of having to handle paths that go downwards? I was initially confused when I looked at this, but I guess this is probably some form of problem shock.
Anyway, for my 20pt solution, the solution is as follows:
First, compute the XOR to the root. Then, you can calculate the cost to go from a node to a direct ancestor directly. Run a modified FLoyd Warshall to get the desired costs for all pairs. Queries can be handled in $$$O(1)$$$ time by just reading the table.
Time complexity: $$$O(N^3+Q)$$$.
const int MAXN = 10005;
int best[MAXN][MAXN];
int n;
void init(int N, std::vector<int> P, std::vector<int> W) {
n = N;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) best[i][j] = 2e9;
for (int i = 0; i < N; i++) best[i][i] = 0;
for (int i = 0; i < N; i++) {
int cur = 0;
int curpos = i;
while (curpos != 0) {
cur ^= W[curpos];
curpos = P[curpos];
best[i][curpos] = min(best[i][curpos], cur);
best[curpos][i] = min(best[curpos][i], cur);
}
}
//now we perform apsp
//modified ahh
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
best[i][j] = min(best[i][j], max(best[i][k], best[k][j]));
}
}
}
}
int minimum_energy(int U, int V) {
return best[U][V];
}
I didn't quite manage to spend a lot of time on this problem, I was busy trying to get AC on either 1A or 1B, unfortunately got none of them. I tried to grab the $$$W[i]\leq 1$$$ subtask, but failed to do so probably due to a bug.
const int MAXN = 50005;
int n;
int par[MAXN][20];
int depth[MAXN];
int xorroot[MAXN];
int has[MAXN];
int kpar (int n, int k) {
for (int i = 19; i >= 0; i--) {
if (k&(1>>i)) n = par[n][i];
}
return n;
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x,y);
x = kpar(x, depth[x]-depth[y]);
if (x==y) return x;
for (int i = 19; i >= 0; i--) {
if (par[x][i] != par[y][i]) x = par[x][i], y = par[x][i];
}
return par[x][0];
}
void init(int N, std::vector<int> P, std::vector<int> W) {
for (int i = 0; i < N; i++) par[i][0] = P[i];
par[0][0] = 0;
for (int i = 1; i < 20; i++) {
for (int j =0; j < N; j++) par[j][i] = par[par[j][i-1]][i-1];
}
n = N;
depth[0] = 0;
for (int i = 1; i < N; i++) depth[i] = depth[P[i]]+1;
xorroot[0] = 0;
for (int i = 1; i < N; i++) xorroot[i] = xorroot[P[i]]^W[i];
has[0] = 0;
for (int i = 1; i < N; i++) has[i] = has[P[i]] | W[i];
}
int minimum_energy(int U, int V) {
int lc = lca(U,V);
int a = xorroot[U]^xorroot[lc];
int b = xorroot[V]^xorroot[lc];
if (a!=b) return 1;
if (a==1 and has[lc] == 0) return 1;
else return 0;
}
There are 2 typos in here. Do try to find them :)
When I first saw this problem, I was relieved that we were not getting 6 batch. As it turns out that somehow, you can treat this more like a MO problem — optimize, then submit your construction.
Also, since there were 3 or 1 1s, I knew that this problem was probably going to be seeing how one can abuse pigeonhole principle as much as possible. This motivates the first idea:
If you pair them up, bits $$$2k$$$ and $$$2k+1$$$, then if there are 3, there are going to be at least 2 pairs with bits. If you perform a bitwise OR for each pair, there will still be at least 2 pairs with bits, unless they are both in the same pair, which you can handle with a bitwise AND. Implementing this gives you $$$2n-C$$$ for some constant $$$C$$$.
In contest, I managed to get the construction for 252 ($$$2n-4$$$), but clearly a lot got 251 ($$$2n-5$$$). The one extra operation can be saved from not performing a bitwise or on the last layer, when there are 2 left. Also, this question had essentially everyone scoring 64 or 65 points, and was hence a non-differentiator. Maybe it will differentiate by the time you take to think of and implement this.
The AC solution was pretty magic personally — I knew you had to abuse pigeonhole, but maybe would not really think of abusing it in a 2d grid. I guess the skill difference is still quite big.
Funny: Someone tried to make this algorithm randomized. However, note that the number of possible testcases will be $$$\binom{128}{3}+128$$$, which is quite small, so a large number of the possible scenarios can be ran rather quickly. In fact, it is not difficult to code one locally, which is good for debugging or ensuring correctness of your solution.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("1.out", "w", stdout);
deque<int> A;
deque<int> B;
int id = 128;
for (int i = 0; i < 128; i += 2) {
cout << "OR" << ' ' << i << ' ' << i+1 << '\n';
A.push_back(id);
id++;
}
while (A.size()>2) {
int x = A[0];
int y = A[1];
cout << "OR" << ' ' << x << ' ' << y << '\n';
A.push_back(id);
id++;
cout << "AND" << ' ' << x << ' ' << y << '\n';
B.push_back(id);
id++;
A.pop_front();
A.pop_front();
}
cout << "AND" << ' ' << A[0] << ' ' << A[1] << '\n';
B.push_back(id);
id++;
while (B.size() > 1) {
int x = B[0];
int y = B[1];
cout << "OR" << ' ' << x << ' ' << y << '\n';
B.push_back(id);
id++;
B.pop_front();
B.pop_front();
}
}
#include <bits/stdc++.h>
using namespace std;
int check(vector<int> cur) {
freopen("1.out", "r", stdin);
int x; cin >> x;
for (int i = 0; i < x; i++) {
string s; cin >> s;
if (s == "NOT") {
int a; cin >> a;
cur.push_back(!cur[a]);
}
else if (s == "OR") {
int a,b; cin >> a >> b;
cur.push_back(cur[a]|cur[b]);
}
else {
int a,b; cin >> a >> b;
cur.push_back(cur[a]&cur[b]);
}
}
return cur.back();
}
int main() {
for (int i = 0; i < 128; i++) {
vector<int> cur(128,0);
cur[i] = 1;
assert(check(cur)==0);
}
vector<int> cur(128,0);
cur[0] = 1; cur[1] = 1; cur[2] = 1;
mt19937 rng(0);
for (int tc = 0; tc < 10000; tc++) {
shuffle(cur.begin(), cur.end(), rng);
assert (check(cur)==1);
}
cout << "ALL TESTCASES ARE CORRECT!";
}
Auto comment: topic has been updated by YSH2020 (previous revision, new revision, compare).
Auto comment: topic has been updated by YSH2020 (previous revision, new revision, compare).
omg
First take the bitwise OR of bits $$$2i$$$ and $$$2i+1$$$. If there is an anomaly, at least two of the $$$64$$$ bits are $$$1$$$; if not, exactly one of them is.
Arrange the $$$64$$$ bits in an $$$8 \times 8$$$ grid. For each row, calculate the OR of the bits in the row. Do the same for each column. We will obtain two new bit arrays $$$R$$$ and $$$C$$$ of length $$$8$$$, one for the rows and one for the columns.
Observe that if $$$R$$$ and $$$C$$$ each have one bit equal to $$$1$$$, there can only be $$$1$$$ bit among the $$$64$$$ that is equal to $$$1$$$. Thus, there is an anomaly if and only if at least one of $$$R$$$ and $$$C$$$ has two bits equal to $$$1$$$. Checking this condition can be done in $$$3 \times 8 - 5 = 19$$$ gates for each array.
Thus, we use $$$64$$$ bits for the first step, $$$8 \times 7 \times 2$$$ to calculate the ORs of rows and columns, and $$$2 \times 19 + 1$$$ to process $$$R$$$ and $$$C$$$, for a total of exactly $$$215$$$ gates.
Note: In the contest, I did not realise that the naive $$$3m-5$$$ algorithm would solve the problem on arrays of size $$$8$$$ using sufficiently few gates, so I further subdivided $$$8$$$ into $$$2 \times 4$$$ and $$$4$$$ into $$$2 \times 2$$$, which also used $$$215$$$ gates.
orz only fc
Even though I didn't compete I would like to share my solution for:
Let $$$D_X$$$ be the XOR of all edge weights on the path from $$$0$$$ to $$$X$$$, then its clear that the XOR of a path between $$$U$$$ and $$$V$$$ is $$$D_U \oplus D_V$$$.
Lets build a graph of N nodes and add undirected edges for each pair $$$(U, V)$$$ such that $$$U$$$ is an ancestor of $$$V$$$ with weight $$$D_U \oplus D_V$$$.
Suppose we find a MST of this graph, then the answer of each query between $$$X$$$ and $$$Y$$$ will be the maximum edge weight on the path between $$$X$$$ and $$$Y$$$ on the MST.
This gives us $$$O(N^2 \log{N} + Q \log{N})$$$ solution.
The biggest bottleneck of our solution is obviously generating the graph of $$$O(N^2)$$$ edges, but that can be simplified with the following observation:
There are at most $$$O(N \log W)$$$ edges that matter, namely for each node $$$X$$$ we consider nodes $$$Y, U_0, U_1, U_2, ...$$$ such that each of them is an ancestor, $$$D_Y = D_X$$$ and $$$MSB(D_{U_i} \oplus D_X) = i$$$ for each $$$i$$$
Proof: Suppose node $$$X$$$ uses two nodes $$$A$$$ and $$$B$$$ such that $$$D_X = D_A = D_B$$$ then notice that all costs between these three is $$$0$$$ hence we can replace the edge between $$$X$$$ and $$$B$$$ with the edge between $$$A$$$ and $$$B$$$ without changing the cost.
Suppose node $$$X$$$ uses two nodes $$$A$$$ and $$$B$$$ such that $$$MSB(D_A \oplus D_X) = MSB(D_B \oplus D_X)$$$. Then if we consider the edge between $$$A$$$ and $$$B$$$ its cost will be $$$D_A \oplus D_B$$$ and we can notice that $$$MSB(D_A \oplus D_B) = MSB((D_A \oplus D_X) \oplus (D_B \oplus D_X)) \lt MSB(D_B \oplus D_X) \Rightarrow D_A \oplus D_B \lt D_B \oplus D_X$$$. Hence the edge between $$$X$$$ and $$$B$$$ can be replaced with the edge between $$$A$$$ and $$$B$$$ which maintains connectivity but makes the cost of the MST strictly better.
And since from each node there exists at least one edge toward its ancestors the graph of these edges is guaranteed to be connected hence only those edges are imporant.
Now only what remains is finding those edges, which is pretty standard: DFS down the tree and maintain a trie on the ancestors of each node $$$X$$$ and just traverse through the trie for each node to find its $$$\log W$$$ important ancestors.
Time complexity is $$$O(N (\log N \log W + \log ^ 2 W) + Q \log N))$$$ where $$$W$$$ is the maximal value of $$$W_i$$$
What is SEATST? Is that the Singapore IOI team selection test or something else?
South East Asian TST
Which country is that exactly? What's the goal of the competition?
SEA TST is the team selection test co-organised by multiple South(east) Asian countries, including Singapore, Malaysia, Indonesia, Thailand, Vietnam, Philippines, and Pakistan.
The goal of the competition is to select the IOI team for each of the participating countries (as the name TST suggests)
Oh, are you saying that all the countries you listed go through the exact same team selection test problems? That must also mean that their IOI teams are decided at the same time too?
Edit: for some clarification, I'm from India and we have our own 'private' TSTs, and I assumed that was the case for all other countries too
For Thailand, we use SEATST (2 days), together with our own TST (3 days) to select the IOI team.