Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one!
Tester | A | B | C | D | E | F |
---|---|---|---|---|---|---|
tfg | 800 | 1100 | 1500 | 1600 | 1900 | 2400 |
neko_nyaaaaaaaaaaaaaaaaa | 800 | 1100 | 1700 | 1900 | 2100 | 2600 |
BucketPotato | 800 | 1000 | 1400 | 1800 | 2400 | - |
LetterC67 | 800 | 1200 | 1400 | 1600 | 2100 | - |
_FireGhost_ | 800 | 1100 | 1500 | 1900 | 2000 | 2400 |
fextivity | 800 | 1000 | 1400 | 1700 | 2000 | 2400 |
generic_placeholder_name | 800 | 1100 | 1600 | 1900 | 2200 | - |
1713A - Traveling Salesman Problem
Do we actually need to go off the axis?
How to avoid visiting an axis more than once?
1713A - Traveling Salesman Problem
Suppose we only have boxes on the $$$Ox+$$$ axis, then the optimal strategy is going in the following way: $$$(0, 0), (x_{max}, 0), (0, 0)$$$. There is no way to do in less than $$$2 \cdot |x_{max}|$$$ moves.
What if we have boxes on two axis? Let's assume it is $$$Oy+$$$, suppose we have a strategy to go in the following way: $$$(0, 0), (x_{max}, 0),..., (0, y_{max}), (0, 0)$$$. In this case it is optimal to fill the three dots with $$$(0, 0)$$$, which is just solving each axis independently.
Therefore, the number of axis does not matters. For each axis that has at least one box, go from $$$(0, 0)$$$ to the farthest one, then come back to $$$(0, 0)$$$.
Time complexity: $$$O(n)$$$
def solve():
n = int(input())
minX, minY, maxX, maxY = 0, 0, 0, 0
for i in range(n):
x, y = list(map(int, input().split()))
minX = min(x, minX)
maxX = max(x, maxX)
minY = min(y, minY)
maxY = max(y, maxY)
print(2 * (maxX + maxY - minX - minY))
test = int(input())
while test > 0:
test -= 1
solve()
How to calculate $$$f(a)$$$?
What if $$$a$$$ is intially sorted?
Consider $$$a$$$ has $$$3$$$ elements. What if $$$a_1 > a_2$$$ and $$$a_2 < a_3$$$?
1713B - Optimal Reduction
Let's call $$$M = max(a_1, a_2, \dots, a_n)$$$.
The problem asks us to make all its elements become $$$0$$$ in some operations. And for each operation, we subtract each elements in an subarray by $$$1$$$. Thus, every largest elements of the array have to be decreased in at least $$$M$$$ operations. And also because of that, $$$min(f(p))$$$ over all permutations $$$p$$$ of $$$a$$$ is never less than $$$M$$$.
Every permutations $$$p$$$ of $$$a$$$ such that $$$f(p) = M$$$ have the same construction. That is, they can be divided into $$$2$$$ subarrays where the left subarray is sorted in non-decreasing order, and the right subarray is sorted in non-increasing order. In other words, the elements of the array should form a mountain.
This is how to perform the operations: assign $$$l$$$ equal to the index of the leftmost element whose value is not $$$0$$$, and assign $$$r$$$ equal to the index of the rightmost element whose value is also not $$$0$$$, then subtract each element $$$a_l, a_{l+1}, \dots, a_r$$$ by $$$1$$$. Repeat the operation until all elements become $$$0$$$. The thing is each element of the array is always greater or equal than every elements in the left side or the right side of it so it can never become negative at some point of performing the operations. Besides, all the largest elements are also included in each operation that we perform, which mean we've achieved the goal to make all elements of the array become $$$0$$$ in $$$M$$$ operations.
So how to check whether $$$f(a) = M$$$ or not? Well, we can define $$$preLen$$$ equal to the length of the longest prefix which is sorted in non-decreasing order. Then define $$$sufLen$$$ equal to the length of the longest suffix which is sorted in non-increasing order. If $$$preLen + sufLen \ge n$$$, the answer is YES.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
int main() {
int tc;
for (cin >> tc; tc--; ) {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int preLen = 1;
while (preLen < n && a[preLen] <= a[preLen + 1])
preLen++;
int sufLen = 1;
while (sufLen < n && a[n-sufLen] >= a[n-sufLen + 1])
sufLen++;
if (preLen + sufLen >= n)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
Is there any case that the answer doesn't exist?
What if: $$$n \le 5$$$
Construct the suffix instead of the prefix.
With any positive integer $$$x$$$, there is at least one square number in $$$[x, 2x]$$$. Proof.
1713C - Build Permutation
First, let's prove that the answer always exists. Let's call the smallest square number that is not smaller than $$$k$$$ is $$$h$$$. Therefore $$$h \leq 2 \cdot k$$$, which means $$$h - k \leq k$$$. Proof.
So we can fill $$$p_i = h - i$$$ for $$$(h - k \leq i \leq k)$$$. Using this method we can recursively reduce $$$k$$$ to $$$h - k - 1$$$, then all the way down to $$$-1$$$.
We can prove that $$$h - k \geq 0$$$, as $$$h \geq k$$$.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, ans[N];
void recurse(int r) {
if (r < 0) return;
int s = sqrt(2*r); s *= s;
int l = s - r; recurse(l - 1);
for (; l <= r; l++, r--) {
ans[l] = r; ans[r] = l;
}
}
int main() {
int tc; cin >> tc;
while (tc--) {
cin >> n; recurse(n - 1);
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
}
We made sure that almost every $$$2^{n - 1}$$$ solutions cannot pass.
Did you use the $$$0$$$ query?
$$$\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$$$, what is the conclusion?
1713D - Tournament Coundown
There is a way to erase $$$3$$$ participants in every $$$2$$$ queries. Since there are $$$2^n - 1$$$ participants to be removed, the number of queries will be $$$\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$$$. Suppose there are only $$$4$$$ participants. In the first query we will ask the judge to compare the $$$1^{st}$$$ and the $$$3^{rd}$$$ participants. There are three cases:
The $$$1^{st}$$$ participant wins more game than the $$$3^{rd}$$$ one: the $$$2^{nd}$$$ and $$$3^{rd}$$$ cannot be the winner.
The $$$3^{rd}$$$ participant wins more game than the $$$1^{st}$$$ one: the $$$1^{st}$$$ and $$$4^{th}$$$ cannot be the winner.
The $$$1^{st}$$$ and $$$3^{rd}$$$ participants' numbers of winning games are equal: both the $$$1^{st}$$$ and $$$3^{rd}$$$ cannot be the winner.
Ask the remaining two participants, find the winner between them.
If there are more than $$$4$$$ participants, we can continuously divide the number by $$$4$$$ again and again, until there are at most $$$2$$$ participants left. Now we can get the winner in one final query.
#include <bits/stdc++.h>
using namespace std;
int ask(vector<int> &k)
{
cout << "? " << k[0] << ' ' << k[2] << endl;
int x;
cin >> x;
if (x == 1)
{
cout << "? " << k[0] << ' ' << k[3] << endl;
cin >> x;
if (x == 1) return k[0];
return k[3];
}
else if (x == 2)
{
cout << "? " << k[1] << ' ' << k[2] << endl;
cin >> x;
if (x == 1) return k[1];
return k[2];
}
else
{
cout << "? " << k[1] << ' ' << k[3] << endl;
cin >> x;
if (x == 1) return k[1];
return k[3];
}
}
void solve()
{
int n;
cin >> n;
vector<int> a, b;
for (int i = 1; i <= (1LL << n); i++)
{
a.push_back(i);
}
while (a.size() > 2)
{
while (!a.empty())
{
vector<int> k(4);
k[0] = a.back();
a.pop_back();
k[1] = a.back();
a.pop_back();
k[2] = a.back();
a.pop_back();
k[3] = a.back();
a.pop_back();
int win = ask(k);
b.push_back(win);
}
a = b;
b.clear();
}
if (a.size() == 2)
{
cout << "? " << a[0] << ' ' << a[1] << endl;
int x;
cin >> x;
if (x == 2) a[0] = a[1];
}
cout << "! " << a[0] << endl;
}
int main(int argc, char ** argv)
{
int tests;
cin >> tests;
while(tests--) solve();
}
Think of the most to the least significant cell of the matrix.
How many positions in the matrix can a cell travel to after performing the operations?
And for each position that that cell can travel to, how many ways are there we can make it?
1713E - Cross Swapping
Let's take a look at what the lexicographically smallest matrix is. Let's call $$$(x, y)$$$ a cell that is in the intersection of row $$$x$$$ and column $$$y$$$ of the matrix, and the integer written on that cell is $$$A_{x, y}$$$. A cell $$$(x_p, y_p)$$$ of this matrix is called more significant than the another cell $$$(x_q, y_q)$$$ if and only if $$$x_p < x_q$$$, or $$$x_p = x_q$$$ and $$$y_p < y_q$$$. The problem asks us to find the smallest matrix so the best suitable way to solve this problem is to traverse through the most to the least significant cell of the matrix, then determine if the current cell can be minimized or not.
Suppose the current cell we are looking at is $$$(x, y)$$$. If $$$x = y$$$ then its position will not change after performing the operations. But if $$$x \neq y$$$, there are exactly $$$2$$$ operations that swap $$$(x, y)$$$ with another cell, that is $$$k = x$$$ and $$$k = y$$$. Both of these operations swap $$$(x, y)$$$ with the same cell $$$(y, x)$$$. So the only way we can minimize the value of $$$(x, y)$$$ is to try swapping it with $$$(y, x)$$$ (if $$$x < y$$$ and $$$A_{x, y} > A_{y, x}$$$) in some way.
As a result we have our constructive algorithm. Remind that for each operation $$$k = i$$$ of the matrix ($$$1 \le i \le n$$$), there are $$$2$$$ states: it is being performed and not being performed. Suppose we have traversed to the cell $$$(x, y)$$$. If $$$x \ge y$$$, ignore it. If $$$x < y$$$ then we try to make $$$A_{x, y} = min(A_{x, y}, A_{y, x})$$$ by deciding to swap or not to swap the cells. If $$$A_{x, y} > A_{y, x}$$$, try to swap $$$(x, y)$$$ with $$$(y, x)$$$ by making $$$2$$$ operations $$$k = x$$$ and $$$k = y$$$ having different states. And if $$$A_{x, y} < A_{y, x}$$$ then we should keep their positions unchanged by making $$$2$$$ operations $$$k = x$$$ and $$$k = y$$$ having the same state. Note that if $$$A_{x, y} = A_{y, x}$$$, we do nothing.
Let's implement this algorithm using a simple DSU where the $$$ith$$$ node represents the operation $$$k = i$$$. We define the value $$$par[u]$$$ in such a way that, suppose $$$p$$$ is the root of the $$$u$$$ node's component, $$$par[u] = p$$$ if $$$2$$$ operations $$$k = u$$$ and $$$k = p$$$ should have the same state, or $$$par[u] = -p$$$ if $$$2$$$ operations $$$k = u$$$ and $$$k = p$$$ should have different states. Define another function $$$join(i, j)$$$ to union $$$2$$$ nodes $$$i$$$ and $$$j$$$ to the same component. Note that $$$u$$$ and $$$-u$$$ are always in the same component and $$$par[-u] = -par[u]$$$. Thus, for the current cell $$$(x, y)$$$, we want to swap it with $$$(y, x)$$$ by calling $$$join(x, -y)$$$, or keep its position unchanged by calling $$$join(x, y)$$$.
After constructing the graphs, the last thing to do is to determine which operations should be performed. One way to do so is for each root of the components of the DSU, we perform the operation which this root represents for. Then for other nodes just check $$$par[i] > 0$$$ for the $$$ith$$$ node and if it is true, the $$$k = i$$$ operation should be performed. When we have the list of the operations that need to be performed, we can bruteforcely perform each operation from the list one by one and the final matrix will be the lexicographically smallest matrix.
Time complexity: $$$O(n^2)$$$
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, a[N][N];
int par[N];
int getPar(int u) {
if (u < 0) return -getPar(-u);
if (u == par[u]) return u;
return par[u] = getPar(par[u]);
}
void join(int u, int v) {
u = getPar(u); v = getPar(v);
if (abs(u) != abs(v)) {
if (u > 0) par[u] = v;
else par[-u] = -v;
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int tc; cin >> tc;
while (tc--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
iota(par + 1, par + n + 1, 1);
// set par[i] == i for i in [1, n]
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (a[i][j] < a[j][i]) join(i, j);
if (a[i][j] > a[j][i]) join(i, -j);
}
for (int i = 1; i <= n; i++) {
if (getPar(i) < 0) continue;
// we only perform the operation
// if and only if getPar(i) > 0
for (int j = 1; j <= n; j++)
swap(a[i][j], a[j][i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
}
cout << '\n';
}
}
}
- Is there any case that the answer doesn't exist?
- If exist, are there multiple?
- How many times does $$$a_i$$$ contribute to $$$b_{j, n}$$$?
$$$\rightarrow$$$ Calculate value that $$$a_i$$$ contribute to $$$b_{j, n}$$$.
Consider the inverse problem: Given array $$$a$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$. How can you solve this problem?
Consider easier problem: Let construct matrix $$$g$$$ of size $$$(2n + 1) \times (n + 1)$$$ same way as matrix $$$b$$$. Given $$$g_{i, n}$$$ $$$(1 \le i \le 2n)$$$, please reconstruct $$$a$$$. How can you solve this problem?
1713F - Lost Array
First, we can see that $$$a_i$$$ contribute $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ times to $$$b_{j, n}$$$, which can calculate similar to Pascal's Triangle. It's easy to see that the value that $$$a_i$$$ contribute to $$$b_{j, n}$$$ equal to $$$a_i$$$ when $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ is odd, $$$0$$$ otherwise.
Let's solve the inverse problem: Given array $$$a$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$. $$$(1 \le j \le n)$$$
By Lucas Theorem, $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ is odd when $$$(n - i)\ AND\ (j - 1) = 0$$$
$$$\rightarrow (n - i)$$$ is a submask of $$$\sim(j - 1)$$$ (with $$$\sim a$$$ is inverse mask of $$$a$$$).
Let define $$$m = 2^k$$$ with smallest $$$m$$$ satisfy $$$m \ge n$$$. Set $$$a'_i = a_i$$$ and $$$b'_j = b_{\sim(j - 1)} = b_{(m - 1) - (j - 1)}$$$ then $$$b'$$$ is the Zeta transform of $$$a'$$$.
So we could apply Mobius transform in $$$b'$$$ to get $$$a'$$$. Since the operation is xor, mobius transform is as same as zeta transform. But unlike the inverse problem, there are some differences. We don't know the value of $$$b'_i$$$ for $$$i$$$ in $$$[0, m - n)$$$.
Let $$$c$$$ be the sum over supermasks array of $$$b'$$$ (with $$$i$$$ is supermasks of $$$j$$$ when $$$i\ AND\ j = j)$$$, then set $$$c_k = 0$$$ for $$$k$$$ in $$$[m - n, m)$$$. After that, do another sum over supermasks on $$$c$$$ to get original value of $$$b'$$$. Now we can find $$$a'$$$ from $$$b'$$$ and $$$a$$$ from $$$a'$$$.
Complexity: $$$O(nlog_2(n))$$$
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1 << 19;
int n;
int a[N], b[N], ta[N], tb[N];
int c[N];
int m, lm, all1;
signed main(){
cin >> n;
ForE(i, 1, n){
cin >> b[i];
}
m = 1 << __lg(n);
if (m < n){
m *= 2;
}
lm = __lg(m);
all1 = m - 1;
memset(ta, -1, sizeof(ta));
memset(tb, -1, sizeof(tb));
ForE(i, 1, n){
tb[all1 ^ (i - 1)] = b[i];
ta[n - i] = -2;
}
For(i, 0, m){
c[all1 ^ i] = max(tb[i], 0);
}
For(bit, 0, lm){
For(msk, 0, m){
if (msk >> bit & 1){
c[msk] ^= c[msk ^ (1 << bit)];
}
}
}
For(i, 0, m){
if (tb[i] == -1){
c[all1 ^ i] = 0;
}
}
For(bit, 0, lm){
For(msk, 0, m){
if (msk >> bit & 1){
c[msk] ^= c[msk ^ (1 << bit)];
}
}
}
For(i, 0, m){
if (tb[i] == -1){
tb[i] = c[all1 ^ i];
}
}
For(i, 0, m){
ta[i] = tb[i];
}
For(bit, 0, lm){
For(msk, 0, m){
if (msk >> bit & 1){
ta[msk] ^= ta[msk ^ (1 << bit)];
}
}
}
ForE(i, 1, n){
a[i] = ta[n - i];
}
ForE(i, 1, n){
cout << a[i] << ' ';
} cout << endl;
}
so quick ^_^
I think problem D has the I/O time issue.
Very quick editorial! thank you!
so fast
Super fast editorial
Thanks for fast editorial, I really enjoyed the contest!
Way more balanced than the last contest.
I think problem D has the I/O time issue.
Yes, and it is too hard for Python users.
Most of the Java users had time limit issues.
Fast editorial!Thank you!
The solution to D is so goated. Just making a simple observation cuts the number of queries just enough so you can pass TC.
First time it wasn't binary search lol. Awesome problem!
But I think it is too easy for a div2 D problem,and if it is div2 C,it may be a bit hard and strange...
The ratings is a little bit different than expected. We expect C to be 1500, D 1900 and E 2200, but luckily it is still balanced.
Yeah C is harder than D imo :p But it is still a really good contest! (Although I didn't find my mistake on problem E till now XD
167303250 Why does this fail on time, same logic is used as in the editorial. Thnx for the super fast editorial.
Really fast editorial, good organization, thanks a lot;)
If the ML for C was 512 mb instead of 256 mb, some fun flow solutions could have passed. What was the point in cutting off O(Nsqrt(N)) Dinic algo solutions? It is not like that's super popular.
I did an overkill, but my MBPM solution passed — 167261911 I have also added library reference in code.
Can you provide me with good resources to learn MBPM?
USACO guide has some good resources for flows
These editorials get uploaded faster than my rating drops
Question D did not add endl when outputting, which led to debug for a long time. I felt that the input n of the last game did not use cin to set off each other. :C
fast solutions , a good round xd
Successfully get Wrong Answer in Problem C using the right idea,:( It's time for more training!
Thx for the fast tutorial.:)
I like this round :) Fast editorial, that's great XD
Question: in problem D, if you follow the solution, won't the number of queries be 3/4 2^n, since you divide the number of participants by 4 every 3 queries? I thought of this solution too but discarded it due to this thought.
It is 2 queries, not 3.
Oh right, I forgot... I almost got it, but didn't make the second query, only divided it by 2 and got WA
I have done D the exact way mention in editorial but the difference was i am taking 2 and 3 participant instead of 1'st and 4'th participant but it gave me WA. Can you please share why only taking 1'st and 4'th participant give AC? here is my solution 167295468
well you don't have exactly same logic) for example if ans == 1 you suppose that i1 and i2+1 are the winners of their pairs, but is i2+1 always the winner? think of what this might lead to
Going with groups of four at each level: you select 2 out of 4 players based on 1 query. And in the end you do one query to pick the winner.
So 2^(n-2) queries required to remove the first half of the players. Or 1+2^(n-1) total. 1+2^(n+1)/4 is less than the limit in the problem.
Thanks for the quick editorial! I really like problem D.
And if I don't get FST, it seems that I can reach Master :)
Such a creative way of applying DSU in E! Nice DSU practice problem
Can any tell, for problem B, why the condition if(a[i] < a[i+1] && a[i] < a[i-1])print NO , is insufficient.
For ex in test:
5 1 1 1 5
Your condition would say that this array is ok, but in fact we need to do 1 + 4 + 4 = 9 operations here, while we could've sort it like
1 1 1 5 5
And we would've need only 5 operations
The input array can have duplicates (eg [2,1,1,2] is NO).
7 days ago!!!
We saved it in a draft an only public after contest, like the announcement...
The problem D is so great!I have never seen a so ingenious problem!
Problem D is one of my favourite interactive problems of all time!
Small issue in the editorial — I'm unable to open the links to the problems [such as when clicking on 1713F — Lost Array]. It shows access denied.
Issue fixed, thanks for your report.
I think D is such a beautiful problem. Thanks for setting this problem hehe
Problem D. You don't need to do the 2nd check on each level, just push two possible winners to the next level. Total queries' count: 2^(n-1)
I think it's 2^(n-1)-1 comparisons.
No, 2^(n-1). The last one is needed to get a winner.
If n=2 then there are 4 people in the bottom layer, then 2 in the second, then 1. Which means you need 2+1 comparisons (2 in bottom, 1 in second). This would give 2^n — 1. If not, what's wrong with this reasoning?
You only need 2 comparisons for n=2 (4 people): 1st query to filter out 2 people, 2nd query to choose out of 2 remaining
lol 7 days ago :))
so fast editorial! Thank you
https://codeforces.net/contest/1713/submission/167305017 Getting TLE on D but can't understand why, or this solution's complexity is not O(1<<n)?
A great contest :) Problem D is so great!!
Did my submission for D get WA due to MLE? https://codeforces.net/contest/1713/submission/167297638
i guess, its unexpected verdict — your code doesn't fit in the required number of queries, and when your code gets -1 like an answer, it must terminate, otherwise you can get any verdict cause interactor stops to read your output
Thanks for the advice! I often get confused with the verdict of the interactive problem.
Take a look at Ticket 15999 from CF Stress for a counter example.
Thanks!
I could almost have finished problem E !!! So sad:(
I like problem D. It's very awesome problem.
D is such a genius problem orz orz orz orz orz
[Deleted]
Not really, but
std::endl
does forcefully flush your output. I think maybe you meant this instead?Even without std::endl, it flushes. endl force flushes even with fast io turned on
Oh wow. That's good to know!
Here's the infamous test case on test 2 on problem D:
Your are faster than me ;)
Problem D is so good!
Amazing speed for editorial,thank you so much.
Can anyone tell me why I get wrong answer in E 167313557?
For problem B, isn't it enough to check if the sequence looks similar to a mountain or not? I mean by a mountain that it increases then decreases, or do one of them only (increases only or decreases only).
This is my submission but in no vain I got WA.
https://codeforces.net/contest/1713/submission/167261187
The weird is that my friend's submission effectively does the same but passed the pretests.
https://codeforces.net/contest/1713/submission/167257143
When you use return in your if statement, there can still be some values left to input and you're skipping them.
Here is your corrected solution: 167318731
ra pro xar
That is the faulty logic in my code. Thanks!
Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).
here are the video Solutions for A-D.
A-E video Editorial for Chinese:
Bilibili
Hi.
I need one help in D. I submitted the same solution with just a small interchange. But I couldn't get why the one that is failing is wrong. Can anyone help?
Wrong Submission: https://codeforces.net/contest/1713/submission/167301158
Correct Submission: https://codeforces.net/contest/1713/submission/167315386
Difference:
Consider the case when n = 3, # of wins for each contestant = [0, 1, 0, 3, 1, 0, 2, 0]. After first iteration, the contestants left is [2, 4, 6, 7]. i.e. # of wins = [1, 3, 0, 2]. For your next iteration, you'd compare contestants 2, 6 for your wrong submission, which will result in a wrong solution.
In more detail: if you make a query about the 1st and 3rd contestant just like in the tutorial:
If you recieve a 0: that means 2nd and 4th are guaranteed to have won the 1st round and moved on to the next stage.
If you receive a 1: that means 1st is guaranteed to have won the 1st round and moved on to the next stage, while 2nd and 3rd are guaranteed to have been eliminated at some point (4th is undecided, so we keep them in the array)
If you receive a 2: that means 3rd is guaranteed to have won the 1st round and moved on to the next stage, while 1st and 4th are guaranteed to have been eliminated at some point (2nd is undecided, so we keep them in the array)
Because we want to ask about people who actually made it to the current stage, order matters: in case you receive a 2, you should record it as [... 3, 2 ...] so that the next step asks about the 3rd player
Why is this giving TLE/ILE for problem D? I have used the same approach as given in the Editorial.My Submission..
You forget to handle when (sz(curr)==1). look at this submission 167324780
Yeah Thanks :)
Not able to understand tutorial for problem C can anybody explain with some little example please.
Try manually writing solutions for first few numbers, like upto n=10, You will observe a pattern where the last few numbers are constructed such that they a[i]+i becomes equal to the perfect square which is >=(n-1). and the problem gets reduced to a smaller problem where the same pattern is continued. Refer to my solution if it helps. 167261412
First, an obvious observation: $$$(a - i) + (b + i) = a + b$$$. Yes, this is obvious and might seem silly, but just keep this in mind.
Suppose we have $$$n = 11$$$, so the permutation needs to range from $$$0$$$ to $$$10$$$.
Start with 10. What is the next square we can reach by adding something to 10? Well, the next square is 16, which we get from adding 6, i.e., 10 + 6 = 16. So for index 10, we can place the value 6.
If the value 6 works for index 10, then the value 7 should work for index 9, because $$$9 + 7 = (10 - 1) + (6 + 1) = 10 + 6 = 16$$$. In fact, we can keep going as follows:
$$$10 + 6 = 16$$$
$$$9 + 7 = 16$$$
$$$8 + 8 = 16$$$
$$$7 + 9 = 16$$$
$$$6 + 10 = 16$$$
At this point, we have mapped indices $$$6$$$ to $$$10$$$ with a permutation of values from $$$6$$$ to $$$10$$$. We are now left with the smaller problem of mapping indices up to $$$5$$$, which we can solve the same way.
More generally, if your last value $$$L$$$ can reach a square by adding $$$k$$$ (for $$$k \leq L$$$), i.e., if $$$L + k$$$ is a square, then we can assign indices from $$$k$$$ to $$$L$$$ with the values $$$L$$$ decreasing down to $$$k$$$. We can now use $$$k - 1$$$ as our new $$$L$$$ and repeat until we eventually complete the case of $$$k = 0$$$.
(note that it's always possible to assign a value for index $$$L$$$ because there must be a square in the range $$$[L, 2L]$$$. However, even if you didn't realize this, writing a condition to print -1 if the next square is larger than $$$2L$$$ would still be accepted, since the condition would simply never be satisfied)
How would A be solved if the boxes weren't limited to the x and y axes?
I believe the problem becomes NP-hard, even with Euclidean distances and integer coordinates. What this means is that even with coordinates between $$$[-100, 100]$$$, it is believed that the most efficient algorithm would still fail the time constraints. There are some decent approximation algorithms though (only because we're considering Euclidean distances), but an exact answer cannot be found efficiently.
FYI, the Traveling Salesman Problem is a very famous problem in a class of known difficult problems (NP-complete).
I really appreciate the effort put into the "Before round starts" section. I wish in the future, more people authors would do it. It was really enjoyable to read and it made me laugh a couple of times
Why does the hint in 1713D - Отсчет турнира say that
$$$2^{n-1}$$$ solutions can't pass? Doesn't the suggested solution make more queries?
Either I haven't understood the maths behind the number of queries or I've just been baited and thought my solution was wrong as I was reading the hints.
My guess is that this is a typo that meant to say $$$2^n - 1$$$. The naive approach of checking every matchup would require $$$2^n - 1$$$ queries. Furthermore, if we assume each query as having only two possible outcomes, then an adversary argument would yield a lower bound of $$$2^n - 1$$$. One who is aware of this argument may not have realized that the assumptions do not hold here, e.g., it requires $$$n - 1$$$ comparisons to find the maximum/minimum from $$$n$$$ values, even if the comparisons are three-way, because the adversary can choose numbers such that equality is never returned, but the tournament setting does not provide such a luxury for the adversary (there must be a lot of equalities).
Anyway, I think the point is that one might naturally try a $$$2^n - 1$$$ solution, thinking that this is the best that could be done, so the hint is to nudge the reader into revisiting their assumptions and realizing that equality is necessary and can be abused.
For problem B, i found that any value in the array cannot be less than both its neighbours, otherwise when we decrease the whole array by 1, we will end up with 'holes' and we will have to do more operations to complete the remaining parts.
So i did this : if a[i] < a[i-1] -> the array is decreasing.
if the array is decreasing AND a[i] < a[i+1], print "NO"
It seems simpler to me
cool problems had fun while solving
all those hints and spoliers make it hard to read
How comes?
Hints done right is a nice idea. Hints done the way they're done are not useful, but I fail to see how they can make it hard to read.
I wonder why no one has written about the most intuitive (IMO) way of solving C yet.
Let's generate all perfect squares that is less than $$$2n$$$. Then, iterate from $$$n-1$$$ to $$$0$$$ and for each $$$i$$$, find the largest perfect square $$$x$$$ such that $$${0 \le x - i < n}$$$ and index $$${x - i}$$$ is not used. So our answer for index $$${x - i}$$$ is $$$i$$$;
Total complexity: $$$O{(n\sqrt{n})}$$$.
https://codeforces.net/contest/1713/submission/167282216
I don't know how to prove its correctness though, would be nice if anyone does.
Suppose you found a position $$$k$$$ such that for the biggest index $$$i$$$ you haven't used (initially $$$i = n - 1$$$) the sum is equal to a perfect square, i.e $$$k + i = pr[j] \iff k = pr[j] - i$$$ for some $$$j$$$.
Then I argue that for the whole range $$$[k, i]$$$ your code assigns them all to $$$pr[i]$$$ (we will later see why $$$k\leq i$$$ and why we can use all indices and positions in $$$[k,i]$$$). Since in the next iteration index $$$i^{(2)} = i - 1$$$ will get matched with position $$$k^{(2)} = k + 1$$$ (keeping the sum the same), then $$$i^{(3)} = i - 2$$$ with $$$k^{(3)} = k + 2$$$ and continuing... $$$i^{(i-k+1)} = i - (i - k) = k$$$ and $$$k^{(i-k+1)} = k + (i - k) = i$$$.
So now the problem is identical given as input $$$n' = k - 1$$$. Since we have used all indices in $$$[k,i]$$$ and all positions in $$$[k,i]$$$. What I didn't mention (but was essential for the above proof to work) was that we had used everything $$$>i$$$ (all positions and all indices) and nothing else, which obviously happens in the start and as we saw also happens after the first pile of iterations. Also you are guaranteed to find a perfect square to match with an index because of the property editorial mentions. (for a given $$$x$$$ there is a perfect square $$$y$$$ such that $$$x\leq y\leq 2x$$$)
Interestingly, that's essentially the editorial's logic but you start searching from the biggest perfect squares, which also means the respective range $$$[k,i]$$$ will be smaller if there are more than 1 perfect square in range $$$[i,2i]$$$.
Yeah, both approaches are doing the same thing, except they choose a different square to start filling out the suffixes (in the same manner). One who is able to prove the correctness of the $$$O(n\sqrt{n})$$$ approach would likely also realize that choosing the smallest square that fits the biggest index would be better (since it's also covered by the same proof of correctness), which leads to the editorial solution, which finds the square faster for an overall linear-time complexity.
I did this as well
167266697
This is one of my favorite Div. 2 rounds in a long time--the problems felt very elegant, and I particularly enjoyed the process of solving C, D, and F. (I think D took me longer than it possibly should have, but I found it somewhat surprising that the winner could be determined without effectively simulating the tournament, and figuring out how to do so was very satisfying.) The conflict with the TCO Wildcard round was unfortunate, since if I didn't have to leave midway through I think I would have had a solid chance of finishing F, but I very much enjoyed the time I was able to spend participating in the contest, and I'd love to see the authors continue writing problems.
As a bit of constructive criticism, E felt a bit standard to me--the two general ideas (transforming the problem into a graph coloring task and then solving that graph coloring problem using DSU) felt very familiar to me. Overall, though, this is a minor critique, and it didn't seem like the problem was known to too many Div. 2 competitors.
Would you be able to link some problems/resources related to the solution for E? I've never seen this technique before, and searching "graph coloring DSU" didn't lead to anything useful either...
I think "2-sat" can help.
Yeah, you're right! This is basically 2-sat with the implicit graph having all bidirectional edges, so you can use a DSU to check for SCCs. Thanks!
I think the code of B problem need to use long long.
The implemention of E is so clever!
your solution for problem F has a WA :D
Thanks for report, this is a mistake, i'll fix it now
Great round! E was one of my favorite problems I've seen:)
About the solution of problem E. Why if par[i] > 0 then the operation k=i should be performed? (sorry my English is not good)
Because as I have mentioned in the tutorial, $$$par[u]=p$$$ if $$$2$$$ operations $$$k=u$$$ and $$$k=p$$$ should have the same state. Suppose $$$p$$$ is the root of the $$$ith$$$ component, because $$$par[i] > 0$$$ and we have performed the operation $$$k = p$$$, we should perform the operation $$$k = i$$$ too ($$$2$$$ operations $$$k = p$$$ and $$$k = i$$$ should have the same state).
thanks a lot :)
Please help me with the Unsolved mystery. QAQ
I can't understand why my first submit of D can't pass test 3. I loaded the data of test 3 after contest, there is nothing wrong with it, local. What does "wrong answer ? or ! expected (test case 1)" means? I've reconstructed my code using scrolling array in contest, but the logic is nothing differerent, but it passed.
This is my WA3 code durning the contest.
https://codeforces.net/contest/1713/submission/167282903
This is debug code(with output & input).
https://codeforces.net/contest/1713/submission/167344378
This is passed code with scrolling array.
https://codeforces.net/contest/1713/submission/167298523
in WA3 code, in main function, maybe you forget '!' when output the answer for case a.size()==1
Oh you're right. Thanks! so sad, why i can make such mistake):
I cannot believe that the two comments are from the same person.
Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).
20 minutes had passed long ago and I still haven't responded yet
Solution LINK
Applied logic is similar a[i-1]>a[i]<a[i+1] but its getting failed in some edge case. It would be a great help if someone will tell me whats the test case in which it has failed. Thank You!!
it is $$$a[i] > a[j] < a[k]$$$ for $$$i < j < k$$$, not $$$a[i-1] > a[i] < a[i+1]$$$
sorry i made mistake while typing.. when i am using upper_bound in code its doing the work of a[k] if any number is greater than a[j] from the (j+1)th index to the end and i am checking this condition whenever a[j-1]>a[j] because whenever this happens we can check as one bigger value is in left side, if its present then the answer is wrong.
My intuition was to get atleast one greater number in left side and atleast one greater number in right side
Thank You for your reply, plz check the code
You can't use upper_bound if the array is not already sorted :)
Can the solution for B also be implemented using mountain array, i mean if the permutation is a mountain array(including sorted), it will have least number of operations?
Yup. The requirement for optimality is that the array can be partitioned into a non-decreasing prefix followed immediately by a non-increasing suffix. Either of the two parts can be empty, which leads to the sorted and reverse-sorted array respectively, but having both as non-empty would yield the mountain array.
The required invariant is that it must always be possible to cover all non-zero elements in a single operation, which means the 0 values only accumulate at the prefix and/or suffix of the array.
Here is another code for 1713C — Build Permutation
B can be solved in other way with two steps:
Squeeze an array (remove consecutive equal elements, leave 1)
Check if $$$a_{i-1} > a_i < a_{i+1}$$$
guys i need your help! in 1713D — Tournament Coundown my code has no output in test 3 while i check in my vs that the code is work whats worng? https://codeforces.net/contest/1713/submission/167304528
May be any kind of segmentation fault.
i was too stupid to find that
Take a look at Ticket 16005 from CF Stress for a counter example.
Jury picked n as: 2
Participant did not ask any queries.
I broke down TAT
in the C solution i don't understand this part:
int s = sqrt(2*r); s *= s;
you can consider that is a ceil function
That line means declaring a variable $$$s$$$ which is the largest perfect square number not exceeding $$$2 \times r$$$.
i found another way to solve D in only 2^(n-1) queries:)
first we ask about the players 1 3, we will have 3 Possible answers: 1 : which means 1 won the first game and since 3 can't be the last winner it dosen't matter if he won the first round or not so we will assume that 4 won which means there will be a round where 1vs4
2: same as the above but this will lead to 3vs2
0 : 1 and 3 lost the first round and there will be 2vs4
we do the same from 5 to 2^n and now we removed half the players and we do that again :)
here is the code https://codeforces.net/contest/1713/submission/167278880
This solution is wrong. Unfortunately our tests were not strong enough to kill it.
I suppose, the below numbers of wins will hack your solution: 2 0 0 1 3 0 1 0 2 0 1 0 4 0 1 0
I tried them, they does not
Yeah, you are right. Nice trick on x==2. It does matter!!
Thx, i first tried it without it but i got wa so when i changed it it work
Hi, is there any specific strategy you use when approaching problems like yesterday's C?
I got stuck with an R->L constructive solution, and wasn't able to understand why exactly it was wrong during the contest.
There is a typo in hint 1 for problem D.
Hi, my solution for B is giving me runtime error, although if I start debugging everything seems fine. I thank in advance everyone who wants to help.
Good morning!
https://codeforces.net/contest/1713/submission/167403306
btw it says that the error may be on line 35, but it says core dumped after g[p — 1] has reached a size of 4 and i process two queries.
My solution for B was to calculate in O(n), the number of operations needed to make the input array all 0's. If this was equal to the maximum element, then the answer is Yes (the maximum element in the array gives you the minimum number of moves of one of its permutations). Otherwise, the #of operations has to be greater, so the answer is No. To get the number of operations itself, I tried "extending" operations from elements before me. EX: If element i is a 5 and element i-1 is a 7, then I can extend 5 operations from the previous element for free. If element i is a 7 and element i-1 is a 5, however, then I can extend 5 operations from the previous element for free, but I'll need 2 more operations.
167242256
How dsu is applied in problem E. Can anyone explain me from basics? My mind is completely out of that negative numbers/parent idea. Thanks in advance!
You can see all the elements of the diagonal as nodes in a graph. For each of these elements, you can either leave them in their original position, or "flip" them. Each element of your diagonal has 2 possible states, so your graph will have 2*n nodes (for a n*n matrix).
Then, the edges between those nodes represents constraints. Consider this matrix:
Here, you would want to swap a[0][1] and a[1][0], So that means you either want k0 flipped, or k1, but not both (k0 being the first diagonal element, and k1 the second). So in your graph, you would have an edge between k0 and k1', AND k1 and k0' (k0' representing the flipped state of k0).
You would store these relationships using DSU, and only add constraints if ki and ki' would not end up in the same tree, because a node cannot be flipped and 'not flipped' at the same time. Try to draw the graph and the constrains by hand, it helped me understand the problem
Hope it makes more sense.
Thanks a lot! Now , I understood the approach. This was really a nice question.
Optimal reduction( B ) can be done using single iteration over the entire array, and with O(1) space complexity. This solution is too complex.
Wait B can be done in O(1)? Elaborate further pls
$$$O(1)$$$ space complexity. The best possible time complexity is $$$O(n)$$$.
Here is a much simpler way for 1713B — Optimal Reduction
First, let's find
f(a)
and then find that array's minimum f possible permutation. It can be proved that the minimum possible f is equal to the maximum element of the array. (We know that we must have at least x operation (max element). Now we give an example for that -> sort the array in reverse order and then do f on it)Now we have found the lowest f of permutations of a.
if it's equal to f(a) then all of the other permutations are greater or equal to f(a) and the answer is YES otherwise NO.
I've updated the new tutorial for B. The old tutorial is super trash that the idea is simple yet i tried to make everything so complicated.
Sorry for the inconvenience!
I wanna share my B solution, I think it can be interesting for someone.
Let's find the $$$f(a)$$$, it's equal to $$$\lfloor \frac{a_1 + a_n + abs(a_2 - a_1) + abs(a_3 - a_2) + \dots + abs(a_n - a_{n-1})}{2} \rfloor$$$.
Now we want to $$$f(a) \le f(b) \rightarrow f(a) = min(f(b))$$$. The one way to get minimum $$$f(b)$$$ is sort array $$$a$$$. Now we have to compare $$$f(sorted(a))$$$ and $$$f(a)$$$
167622000
I tried solving E with the hints but got stuck, please help!
Think of the most to the least significant cell of the matrix.
I try to fix cells least first to most significant at last to make it lexicographically smallest.
How many positions in the matrix can a cell travel to after performing the operations?
2
And for each position that that cell can travel to, how many ways are there we can make it?
2 — either swap the column or row
is my above reasoning correct, if yes how can i try 2 ways to swap efficiently?
If you have gone this far and still haven't figured out the answer yet, please read the tutorial :)
thanks for the great contest and fast editorial (even though my comment isn't so fast)
I've tried submitting a solution to problem D ------>167785392 But I get Idleness limit exceeded on test 3, I modified a small part ------>167782691, but it seems to be working Ok, how it works?it confuses me.
When n is even q1.size will never be 2 (eg for 6 on the test case you are failing q1.size will be 64 -> 16 -> 4 -> 1) and the second loop never gets run. As you've moved the print outside the loop in the second version it works.
For problem F, very interesting by the way, I get stuck in the last part, when we have array b of size n and want to expand it to b' of size m.
The editorial says: Create array c with sum over supermask, then set zeros the positions [m-n, m) and do sum over supermask again. Why sum over supermasks, and do it two times?
(I understand that sum here means xor).
Btw, why does it work?
Can somebody explain in more details, why solution for F does work? Especially, we want to find such $$$b'_i$$$ for $$$i \in [0, m - n)$$$ that subset sum will have zeros in all elements $$$\in [n, m)$$$. Why operation explained in editorial do that?
In fact, we can implement DSU in much more brute ways. Since we only need to do up to n-1 join operations, so we could join i and j by brute force over range [1,n]. The total complexity is O(n^2) despite a larger constant factor, it still fits the time limit.
F is the first 2900+ rating problem I've solved (without tutorial). Also in the contest I may not have enough time to deal with it, it's pretty easy for me (as a div2F).
We can solve F by divide and conquer. Calculate brutely to about n=7 and we can find a pattern: Let eq_i is the i-th xor equation we need to solve, then eq_1^eq_2, eq_3^eq_4, ... form a smaller equation system with size n/2, which variable are all even-indexed elements (a2,a4,...) or odd-indexed elements(a1,a3,...) and the pattern of them are completely same with the situation of n/2. Therefore we can solve it first. If n is even, then we get all odd-indexed elements, and all even-indexed equations form another equation system with size n/2, but at this time we solve for even-indexed elements. If n is odd, then we get all even-indexed elements, and all even-indexed equations form a same equation system with size (n-1)/2... but to solve for odd-indexed elements we need it's size to be (n+1)/2. We need to do xor for b_n,n and all a_k where k is even and ((n-k)&(n-1))==0, and add the result to the equations to form an array with size (n+1)/2 and solve it for odd-indexed elements.
Equations for n=7:
#1 a1^a2^a3^a4^a5^a6^a7=b1
#2 a1......^a3......^a5.....^a7=b2
#3 ......a2^a3...........^a6^a7=b3
#4 ............a3................^a7=b4
#5 ................a4^a5^a6^a7=b5
#6 .......................a5....^a7=b6
#7 ...........................a6^a7=b7
if we do #1^#2, #3^#4, #5^#6, we get:
#1' ...a2...^a4...^a6=b1^b2
#2' ...a2...........^a6=b3^b4
#3' .........a4.....^a6=b5^b6
which is same as what we get when solve for n==3.
Also, if we move even_indexed terms of #7 to the right hand side, we get:
#2 a1...^a3...^a5...^a7=b2
#4 ........a3............^a7=b4
#6 ................a5....^a7=b6
#7' .........................a7=b7^a6
which is same as what we get when solve for n==4.
For the problem C how to prove that such kind of solution will not duplicated ? what if there will be a circumstance when pi = pj = hi -i = hj — j ?
Problem E feels like 2000/2100, A simpler solution(also uses DSU):
Trivial observations:
Let us call $$$op(i)$$$ = Number of operations with $$$k = i$$$.
Now $$$A_{i, j}$$$ gets swapped with $$$A_{j, i}$$$ only if $$$parity(op(i)) \neq parity(op(j))$$$.
We will now maintain dsu sets (elements in them are all the possible choices of $$$k$$$) such that for every dsu set, for any two elements in the set, we know the relation between their parities (equal or not equal).
To generate the lexicographically smallest matrix, we will iterate over cell $$$A_{i, j}$$$ from the most significant cell to the least significant cell, and skip the cell if we already iterated over its mirror cell. Cases:
This is obviously optimal because we iterate from most significant cell to least significant cell.
Implementation: link
For problem D:
why do I get Invalid query on testcase 1 I'm asking 5 queries and the limit is 6(for n=3)
Submission link: https://codeforces.net/contest/1713/submission/260804734
UPD: Changed the compiler and it got accepted