All editorial codes contain solutions wrapped in classes. I'll only paste the important part (namespace solution in C++, class Solution in Python 3) as plaintext in the solution code section (along with the corresponding AC submission link). You might want to see the code template here.
#include <bits/stdc++.h>
using namespace std;
namespace solution {
bool hasMultipleTests = true;
void preprocess() {
// something
}
void input(int testcase) {
// something
}
void solve(int testcase) {
// something
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solution::preprocess();
int t = 1;
if (solution::hasMultipleTests) cin >> t;
for (int testcase=1; testcase<=t; testcase++) {
solution::input(testcase);
solution::solve(testcase);
}
return 0;
}
import sys
input = sys.stdin.readline
class Solution:
hasMultipleTests = True
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
pass
@classmethod
def solve(cls, testcase):
pass
# end Solution
if __name__ == '__main__':
Solution.preprocess()
t = int(input()) if Solution.hasMultipleTests else 1
for testcase in range(1, t+1):
Solution.input(testcase)
Solution.solve(testcase)
Also, per my own custom ever since 2019, solution codes will only be published after system testing, to ensure all codes used here guarantee AC. Thank you for your patience.
Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni
In which cases would a light be on?
Imagine that you have $$$x$$$ white socks and $$$y$$$ black socks. What would you do to make the maximum pairs of matched socks?
Imagine that you have $$$x$$$ white socks and $$$y$$$ black socks. What would you do to make the maximum pairs of unmatched socks?
Submission link: 289291089
namespace solution {
bool hasMultipleTests = true;
int n;
vector<int> a;
void preprocess() {
}
void input(int testcase) {
cin >> n;
a.clear();
a.resize(n * 2);
for (auto &z: a) cin >> z;
}
void solve(int testcase) {
int cnt0 = 0;
for (auto &z: a) {
cnt0 += z;
}
cout << (cnt0 & 1) << " " << min(cnt0, n * 2 - cnt0) << endl;
}
}
Submission link: 289291082
class Solution:
hasMultipleTests = True
n: int = None
a: list = None
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
cls.n = int(input())
cls.a = list(map(int, input().split()))
@classmethod
def solve(cls, testcase):
cnt0 = sum(cls.a)
print(cnt0 & 1, min(cnt0, cls.n*2 - cnt0))
# end Solution
Author: Kuroni
Development: AkiLotus
Hinter: Kuroni
Editorialist: AkiLotus, Kuroni
There is always exactly one solution for $$$n = 1$$$. For $$$n \ge 3$$$, for which $$$k$$$ should there be no solution at all?
Try to find a solution with $$$k = 2$$$ and $$$k = 4$$$, assuming $$$n$$$ allows at least one solution to exist. Can you find a pattern and generalize it for all even $$$k$$$?
Try to find a solution with $$$k = 3$$$ and $$$k = 5$$$, assuming $$$n$$$ allows at least one solution to exist. Can you find a pattern and generalize it for all odd $$$k$$$?
Submission link: 289291698
namespace solution {
bool hasMultipleTests = true;
int n, k;
void preprocess() {
}
void input(int testcase) {
cin >> n >> k;
}
void solve(int testcase) {
if (n == 1) {cout << "1\n1\n"; return;}
if (k == 1 || k == n) {cout << "-1\n"; return;}
int p2 = k - k % 2;
int p3 = k + 1 + k % 2;
cout << "3\n1 " << p2 << " " << p3 << endl;
}
}
Submission link: 289291693
class Solution:
hasMultipleTests = True
n: int = None
k: int = None
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
cls.n, cls.k = map(int, input().split())
@classmethod
def solve(cls, testcase):
if cls.n == 1: return(print('1\n1'))
if cls.k in {1, cls.n}: return(print(-1))
p2, p3 = cls.k - cls.k % 2, cls.k + 1 + cls.k % 2
print(f'3\n1 {p2} {p3}')
# end Solution
Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni
Without loss of generality, you can rewrite the triangle inequality into a much more compacted form if the side lengths are properly ordered.
Given four integers $$$a \le b \le c \le d$$$, if $$$(a, b, d)$$$ are side lengths of a non-degenerate triangle, so does $$$(a, b, c)$$$.
Given four integers $$$a \le b \le c \le d$$$, if $$$(a, b, d)$$$ are side lengths of a non-degenerate triangle, so does $$$(a, c, d)$$$.
Given four integers $$$a \le b \le c \le d$$$, if $$$(a, b, d)$$$ are side lengths of a non-degenerate triangle, so does $$$(b, c, d)$$$.
To make a sorted array $$$[b_1, b_2, \ldots, b_m] \space (m \ge 3)$$$ satisfy the problem, we must ensure that $$$b_1 + b_2 > b_m$$$.
Fix the result array to have two minimas and one maxima at respectively $$$a_x$$$, $$$a_y$$$ and $$$a_z$$$. How many operations are required to do so?
Is there a fast and optimal way to try all possible $$$(a_x, a_y, a_z)$$$ triplets?
Submission link: 289292343
namespace solution {
bool hasMultipleTests = true;
int n;
vector<int> a;
void preprocess() {
}
void input(int testcase) {
cin >> n;
a.clear();
a.resize(n);
for (auto &z: a) cin >> z;
}
void solve(int testcase) {
sort(a.begin(), a.end());
int l = 0, ans = n - 2;
for (int r = 2; r < n; r++) {
while (r - l >= 2 && a[l] + a[l+1] <= a[r]) l++;
ans = min(ans, n - (r - l + 1));
}
cout << ans << endl;
}
}
Submission link: 289292338
class Solution:
hasMultipleTests = True
n: int = None
a: list = None
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
cls.n = int(input())
cls.a = list(map(int, input().split()))
@classmethod
def solve(cls, testcase):
cls.a.sort()
l, r, ans = 0, 2, cls.n - 2
while r < cls.n:
while r - l >= 2 and cls.a[l] + cls.a[l+1] <= cls.a[r]: l += 1
ans = min(ans, cls.n - (r - l + 1))
r += 1
print(ans)
# end Solution
Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni
There are many specific constraints on the system tree.
First, notice that $$$1 \le x \le y \le n-1$$$ if and only if $$$p_x \le p_y$$$. Draw a few trees with this constraint and start pointing your finger on the nodes from $$$0$$$ to $$$n-1$$$. Notice the pattern your finger is making.
Incorporate hint #1 with the fact that the "tentacles" of the Genokraken are just paths. Try to draw more detailed conclusion about that pattern.
Is there a way to know how many tentacles there are?
What use could we make of the fact that node $$$1$$$ has exactly two adjacent nodes?
The query limit is very small. Is there a way to query that the information obtained in each query should (at least partially) determine a node?
For each "tentacle", can we know when its path has ended? How many queries should it take?
Submission link: 289292866
namespace datastruct {
// A doubly-linked list that only supports modify and (pseudo) deletion at pointer
class DeleteOnly_DLL {
public:
vector<int> values;
vector<int> prev;
vector<int> next;
int pointer;
DeleteOnly_DLL(int size) {
values.resize(size);
prev.resize(size);
next.resize(size);
for (int i = 0; i < size; i++) {
prev[i] = (i + size - 1) % size;
next[i] = (i + 1) % size;
}
pointer = 0;
}
int current() {
return values[pointer];
}
// Set value at pointer and move pointer to next
void set_and_move(int val) {
values[pointer] = val;
pointer = next[pointer];
}
// "Delete" node and move pointer to next
void erase() {
if (prev[pointer] != -1) {
next[prev[pointer]] = next[pointer];
}
if (next[pointer] != -1) {
prev[next[pointer]] = prev[pointer];
}
int next_id = next[pointer];
prev[pointer] = next[pointer] = -1;
pointer = next_id;
}
};
}
namespace solution {
bool hasMultipleTests = true;
int n;
int ask(int a, int b) {
cout << "? " << a << " " << b << endl;
cout.flush();
int res; cin >> res;
return res;
}
void answer(vector<int> &p) {
cout << "!";
for (int i=1; i<n; i++) {
cout << " " << p[i];
}
cout << endl;
cout.flush();
}
void preprocess() {
}
void input(int testcase) {
cin >> n;
}
void solve(int testcase) {
vector<int> p(n, -1);
p[1] = 0;
int r = 2;
while (true) {
int response = ask(1, r);
if (response == -1) exit(2226);
if (response == 1) {
p[r] = 0;
r++;
}
else break;
}
int tentacle_count = r - 1;
datastruct::DeleteOnly_DLL tentacles = datastruct::DeleteOnly_DLL(tentacle_count);
for (int i = 0; i < tentacle_count; i++) {
tentacles.set_and_move(i + 1);
}
p[r] = tentacles.current();
tentacles.set_and_move(r);
r++;
while (r < n) {
int response = ask(tentacles.current(), r);
if (response == -1) exit(2226);
if (response == 1) {
tentacles.erase();
}
else {
p[r] = tentacles.current();
tentacles.set_and_move(r);
r++;
}
}
answer(p);
}
}
Submission link: 289292865
class DeleteOnly_DLL:
def __init__(self, size: int):
self.values = [None for _ in range(size)]
self.prev = [(i + size - 1) % size for i in range(size)]
self.next = [(i + 1) % size for i in range(size)]
self.pointer = 0
def current(self):
return self.values[self.pointer]
# Set value at pointer and move pointer to next
def set_and_move(self, val):
self.values[self.pointer] = val
self.pointer = self.next[self.pointer]
# "Delete" node and move pointer to next
def erase(self):
if self.prev[self.pointer] != -1:
self.next[self.prev[self.pointer]] = self.next[self.pointer]
if self.next[self.pointer] != -1:
self.prev[self.next[self.pointer]] = self.prev[self.pointer]
next_id = self.next[self.pointer]
self.prev[self.pointer] = self.next[self.pointer] = -1
self.pointer = next_id
# end DeleteOnly_DLL
class Solution:
hasMultipleTests = True
n: int = None
@classmethod
def ask(cls, a: int, b: int):
print(f'? {a} {b}', flush=True)
return int(input())
@classmethod
def answer(cls, p: list):
print(f'! {" ".join(map(str, p[1:]))}', flush=True)
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
cls.n = int(input())
@classmethod
def solve(cls, testcase):
p = [-1 for _ in range(cls.n)]
p[1] = 0
r = 2
while True:
response = cls.ask(1, r)
if response == -1: exit(2226)
if response == 1:
p[r] = 0
r += 1
else: break
tentacle_count = r - 1
tentacles = DeleteOnly_DLL(size = tentacle_count)
for i in range(tentacle_count):
tentacles.set_and_move(i + 1)
p[r] = tentacles.current()
tentacles.set_and_move(r)
r += 1
while r < cls.n:
response = cls.ask(tentacles.current(), r)
if response == -1: exit(2226)
if response == 1:
tentacles.erase()
else:
p[r] = tentacles.current()
tentacles.set_and_move(r)
r += 1
cls.answer(p)
# end Solution
Author: thanhchauns2
Development: thanhchauns2, Sagita_Phoenix
Hinter: AkiLotus
Editorialist: Kuroni, AkiLotus
Why is $$$n$$$ odd? Does it imply anything of the availability of a solution?
$$$n = 1$$$ is trivial. Try to solve this problem if $$$n = 3$$$ and $$$a_1 = a_3$$$.
Try to solve this problem for any array with $$$n = 3$$$. Is there any way to solve this without going pass a state of $$$a_1 = a_3$$$ (or $$$a_1 = a_2$$$ or $$$a_2 = a_3$$$)?
Assume that $$$n = 5$$$, $$$a_1 = a_5$$$ and $$$a_2 = a_3 = a_4$$$. Now refer to hint #2, can you see any similarity in the solution?
Refer to hint #4. What would happen if we apply an operation to index $$$2$$$ and another to index $$$4$$$?
For any array with $$$n = 5$$$, how would you convert it into the form stated in hint #4?
Refer to hint #6. How would you make $$$a_1 = a_5$$$ and $$$a_2 = a_4$$$? Does the fact that $$$n$$$ is odd help in any way?
Can you draw a generalized conclusion?
Submission link: 289293300
namespace solution {
bool hasMultipleTests = true;
int n;
vector<int> a;
void apply_prefixes(vector<long long> &prefixes, vector<long long> &v) {
for (int i = 2; i < n * 2; i++) {
prefixes[i] += prefixes[i - 2];
}
for (int i = 0; i < n * 2; i++) {
v[i % n] += prefixes[i];
}
}
void construct_trench(vector<long long> &arr, vector<long long> &v) {
vector<long long> prefixes(n * 2, 0LL);
vector<long long> delta(n, 0LL);
for (int i = 0; i < n / 2; i++) {
long long diff = arr[n - 1 - i] - (arr[i] + delta[i]);
delta[i] += 2 * diff;
delta[i + 1] += diff;
prefixes[n - i] += diff;
prefixes[n + i + 2] -= diff;
}
apply_prefixes(prefixes, v);
for (int i = 0; i < n; i++) {
arr[i] += v[i] * 2;
arr[(i + 1) % n] += v[i];
arr[(i + n - 1) % n] += v[i];
}
}
void construct_plateau(vector<long long> &arr, vector<long long> &v) {
vector<long long> prefixes(n * 2, 0LL);
vector<long long> delta(n, 0LL);
for (int i = n / 2 - 1; i >= 0; i--) {
long long diff = arr[i] - (arr[i + 1] + delta[i + 1]);
delta[i] += diff;
prefixes[i + 1] += diff;
prefixes[n - i] -= diff;
}
apply_prefixes(prefixes, v);
}
void preprocess() {
}
void input(int testcase) {
cin >> n;
a.clear();
a.resize(n);
for (auto &z: a) cin >> z;
}
void solve(int testcase) {
if (n == 1) {
cout << "0\n";
return;
}
vector<long long> v(n, 0LL);
vector<long long> arr(n);
for (int i = 0; i < n; i++) {
arr[i] = 1LL * a[i];
}
construct_trench(arr, v);
construct_plateau(arr, v);
long long offset = *ranges::min_element(v);
for (auto &z: v) cout << z - offset << " ";
cout << endl;
}
}
Submission link: 289293299
class Solution:
hasMultipleTests = True
n: int = None
a: list = None
@classmethod
def apply_prefixes(cls, prefixes, v):
for i in range(2, cls.n*2):
prefixes[i] += prefixes[i - 2]
for i in range(cls.n*2):
v[i % cls.n] += prefixes[i]
@classmethod
def construct_trench(cls, arr, v):
prefixes = [0 for _ in range(cls.n * 2)]
delta = [0 for _ in range(cls.n)]
for i in range(cls.n // 2):
diff = arr[cls.n - 1 - i] - (arr[i] + delta[i])
delta[i] += 2 * diff
delta[i + 1] += diff
prefixes[cls.n - i] += diff
prefixes[cls.n + i + 2] -= diff
cls.apply_prefixes(prefixes, v)
for i in range(cls.n):
arr[i] += v[i] * 2
arr[(i + 1) % cls.n] += v[i]
arr[(i + cls.n - 1) % cls.n] += v[i]
@classmethod
def construct_plateau(cls, arr, v):
prefixes = [0 for _ in range(cls.n * 2)]
delta = [0 for _ in range(cls.n)]
for i in range(cls.n // 2 - 1, -1, -1):
diff = arr[i] - (arr[i + 1] + delta[i + 1])
delta[i] += diff
prefixes[i + 1] += diff
prefixes[cls.n - i] -= diff
cls.apply_prefixes(prefixes, v)
@classmethod
def preprocess(cls):
pass
@classmethod
def input(cls, testcase):
cls.n = int(input())
cls.a = list(map(int, input().split()))
@classmethod
def solve(cls, testcase):
if cls.n == 1:
return(print(0))
v = [0 for _ in range(cls.n)]
cls.construct_trench(cls.a, v)
cls.construct_plateau(cls.a, v)
offset = min(v)
v = list(map(lambda x: x - offset, v))
print(*v)
# end Solution
We have some observations here. Our only allowed operation is $$$[1, 2, 1]$$$, but by stacking it in the right way (and normalizing the differences) we could obtain simpler operations. In details:
- We can apply operation $$$[-1, -1]$$$ to index $$$i$$$ (decrease values at index $$$i$$$ and $$$i+1$$$ by $$$1$$$) by applying operation $$$[1, 2, 1]$$$ to index $$$i+2$$$, $$$i+4$$$, and so on until $$$i-1$$$ (please treat these addition/subtraction of indices in a cyclic array context). Doing so will increase every index's value by $$$2$$$, except $$$i$$$ and $$$i+1$$$ only get increase by $$$1$$$, so relatively, indices $$$i$$$ and $$$i+1$$$ got their values lowered by $$$1$$$ compared to the rest.
- We can apply operation $$$[1]$$$ to index $$$i$$$ (increase value at index $$$i$$$ by $$$1$$$) by applying operation $$$[-1, -1]$$$ to index $$$i+1$$$, $$$i+3$$$, and so on until $$$i-1$$$. Proof for this is trivial.
Author: MofK
Development: MofK, AkiLotus
Hinter: AkiLotus
Editorialist: MofK, AkiLotus
Try to solve if all pockets are in the same box. Does the problem seem familiar?
There's one kind of cases for a box that its game has a fixed move sequence, and thus a fixed outcome. What is it?
Let's take the cases found in hint #2 out of the equation from here on. Is there any way for a player to win in two consecutive boxes?
If a player can win a box if both play optimally to win, can they also lose it if both play optimally to lose?
Submission link: 289293663
namespace solution {
bool hasMultipleTests = true;
int n;
vector<int> a;
const int MAXN = 1000000;
const int MOD = 998244353;
int pow2[MAXN];
void preprocess() {
pow2[0] = 1;
for (int i = 1; i < MAXN; i++) {
pow2[i] = (2LL * pow2[i-1]) % MOD;
}
}
void input(int testcase) {
cin >> n;
a.clear();
a.resize(n);
for (auto &z: a) cin >> z;
}
void solve(int testcase) {
if (*ranges::max_element(a) == 1) {
cout << (n & 1 ? pow2[n-1] : 0) << endl;
return;
}
int ans = 0;
// The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control
// if and only if before it is an even amount of pockets
int alice_at_critical = 1;
int prefix_1 = 0;
while (a[prefix_1] == 1) {
prefix_1++;
if (prefix_1 % 2 == 0) {
alice_at_critical = (alice_at_critical + pow2[prefix_1 - 1]) % MOD;
}
}
int grundy = (prefix_1 & 1);
for (int r = prefix_1; r < n; r++) {
grundy ^= a[r];
if (!grundy) continue;
int post_critical = (r < n - 1 ? pow2[n - 2 - r] : 1);
int pre_critical = (grundy == 1 ? pow2[prefix_1] : alice_at_critical);
ans += (1LL * pre_critical * post_critical) % MOD;
ans %= MOD;
}
cout << ans << endl;
}
}
Submission link: 289293585
class Solution:
hasMultipleTests = True
n: int = None
a: list = None
MAXN: int = 1000000
MOD: int = 998244353
pow2: list = None
@classmethod
def preprocess(cls):
cls.pow2 = [None for _ in range(cls.MAXN)]
for i in range(cls.MAXN):
cls.pow2[i] = 1 if i == 0 else (2 * cls.pow2[i-1]) % cls.MOD
@classmethod
def input(cls, testcase):
cls.n = int(input())
cls.a = list(map(int, input().split()))
@classmethod
def solve(cls, testcase):
if max(cls.a) == 1:
return(print(cls.pow2[cls.n-1] if cls.n & 1 else 0))
ans = 0
# The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control
# if and only if before it is an even amount of pockets
alice_at_critical = 1
prefix_1 = 0
while cls.a[prefix_1] == 1:
prefix_1 += 1
if prefix_1 % 2 == 0:
alice_at_critical = (alice_at_critical + cls.pow2[prefix_1 - 1]) % cls.MOD
grundy = prefix_1 & 1
for r in range(prefix_1, cls.n):
grundy ^= cls.a[r]
if grundy == 0: continue
post_critical = cls.pow2[cls.n - 2 - r] if r < cls.n - 1 else 1
pre_critical = cls.pow2[prefix_1] if grundy == 1 else alice_at_critical
ans = (ans + pre_critical * post_critical) % cls.MOD
print(ans)
# end Solution
Problem D can be solved in $$$\mathcal{O}(n)$$$ with a queue quite easily as well, which is implemented directly into the stl so it's easier. The idea stays the same, just replace the double linked list with a queue
I believe there is an even lighter ( implementation wise ) sol to D. I keep track of the next parent to be considered ( stored in variable bp initiated at N-2 ) and the current node ind ( initiated at N-1) who's parent we're looking for, we (decrement ind iff bp is its parent) and decrement bp at each iteration till its 0
That's quite brilliant, though it feels less intuitive to me
put an explanation below big dog
Tutorial of D definitely proves that the problem setter group had Asian influence ..
W contest.
For D, there also exists n — 3 query soln instead of 2 * n — 6 query solution.
Here is the solution.
can someone pls prove the fact that the smallest two elements will always have to be continuous in the original array as well ? I am refering to problem C here
what do you mean by continuous?
it is evident that when the array is sorted, let's say a_1 <= a_2, ...., <= a_n, then of course, when you choose a_1 and a_2, and let's just say there exists a number a_k so that a_1, a_2, a_k are the sides of a non degen triangle, then a_1, a_3, a_k is still acceptable (with 3 < k) because the triangle equality still holds. In other words, the way we choose 2 consecutive elements has set a lower bound to all the answers with bigger number.
another solution to E, although after reading the alternate solution, I think that is better
we can apply operation [-1,-1,1,1] to index i (e.g. a[i]--,a[i+1]--,a[i+2]++,a[i+3]++) by applying operation [-1,-2,-1] to i, and [1,2,1] to i+1
now, we can apply operation [-1,0,1] to index i by applying operation [-1,-1,1,1] to indexes i,i+2,...,until i-1
we can apply operation [-1,1] to index i by applying operation [-1,0,1] to indexes i,i+2,... until i-1
now applying operation [-1,1] keeps the sum constant, so we just need apply arbitrary operations [1,2,1] until (sum of a)%n==0 which is always possible
289298093
same, and yet it's much simpler. 289315539
Alternate solutions for E
Write the equations A[i+1] + V[i] + 2 * V[i+1] + V[i+2] = T. [eqn1] Taking differences, (A[i+2] — A[i+1]) + (V[i+3] + V[i+2]) — (V[i+1] + V[i]) = 0 [eqn2]
Solution 1. https://codeforces.me/contest/2032/submission/289289897 Write W[i] = V[i] + V[i+1]. eqn2 is W[i+2] = W[i] + A[i+1] — A[i+2], so we can fill all W[i]'s in terms of W[0], and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0]. Now we want to solve for V in terms of W, which is easy by taking alternating sums of V[i+1] = W[i] — V[i].
Solution 2. https://codeforces.me/contest/2032/submission/289297804 Notice a solution for T=0 implies a solution for T=4k (V[i] += k). So, guarantee a solution for T=0 by first shifting A, then we can assume T=0. Now V[0] and V[1] determine V. By chasing eqn1, we will get 2 equations and 2 unknowns.
wice city
and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0].
Could you elaborate more on this line? Thank you.
For C, I sorted then binary search on the minimum number of elements to reassign. 289211192
I thought about binary search during the race, but I didn't finish it
You might need some WuXing.
Could you please explain what you did inside the binary search? I used binary search too but i only kept comparing the sum of two values with the last element, which got WA for the test case "1 1 1 2". I understood that my approach was wrong but confused about the correct one. TIA.
Why was n forced odd in E?
if n is even operation doesnt change the parity of the difference between sum of even and odd position elements. so if the parity is odd there is no solution
Yes, then you would output -1 according to the statement
in problem C whats the proof that ax and ay should be consecutive elements of the array in sorted order ? suppose we have x as operations needed using consecutive a[i] and a[i+1] lets say max we can reach is j , now if we let ax to be a[i] and ay to be a[i+2] then j can be much more than the original isnt if we have a[i]+a[i+2]>a[i]+a[i+1]? whats the proof that checking with consecutive elements does the job? AkiLotus
Without that condition, you can't ensure that all triplets are valid.
One counterexample: $$$[3, 4, 5, 7]$$$. If you used $$$a_i$$$ and $$$a_{i+2}$$$ for pivoting, you'd conclude that $$$0$$$ operations are required, which is not true, as $$$(3, 4, 7)$$$ are invalid.
For your example i will consider the array two minimums be 3,5 now j will reach 7 so we have 3,5,7 max so total ops needed is 4-3=1 because i will change the one (i have not taken) like 4 between 3 and 5 to ay that is 5, so that validity is maintained.
I see, you wanna pick $$$a_i$$$ and the range $$$[a_{i+2}, a_j]$$$. Then... why don't you simply pivot $$$a_{i+1}$$$ and $$$a_{i+2}$$$ for a clearly not-lower upper bound $$$a_{j'}$$$?
okay yeah makes sense thanks
Finally Pupil
Congrats!
D was very fun, and F seems very interesting as well, thank you for the contest and +100 delta :D
orz, you almost reach CM now.
Thank you for such detailed Editorial. I wish, other authors could also write editorials in such a way.
You can solve problem E by constructing matrix, as this comment pointed out. Its also not necessary to use FFT to solve this. The matrix inverse $$$M^{-1}$$$ is easy to observe, and each element of the inner product $$$(M^{-1}a)_i = -(M^{-1}a)_{i-1} + b_i$$$ where $$$b_i$$$ is a term easy to maintain ($$$b_i = -b_{i-1} + 4a_i$$$).
my sol for E:
+[1 2 1] can be converted to +[1 1] by doing these operations:
[start = 1] 1 0 1 0 1 0 ... 1 0 1 0 1 0
(the start is the first index that gets affected by the +[1 1])
this can be performed with a prefix sum on odd/even indices
+[1 1] can be converted to +1 by doing these +[1 1] operations:
[start = 1] 0 1 0 1 0 1 ... 0 1 0 1
solving the problem with +1 is free
so great tutorial with lots of hints!
Interesting...
Alternate solution to D by observation alone with ZERO DATA STRUCTURES knowledge required:
We find parents from max to min node, noting that each parent we look for must be less than the minParent we have assigned thus far. i.e if a previous(greater) node had the parent 4, no new nodes can have the parent 4 or greater, since this violates the tree. We can say is that we will never ask for more than n times, because the minParent decreases by 1 for every query(note that two nodes cannot have the same parent besides zero). So maybe we ask in the worst case for n-2 to 1, which is just n-2. 2n-6<n-2 becomes n<4(which is given), so this solution always works. Hope someone like it!
Now onto understanding the actual editiorial...
Yeah I have the same solution and you can actually do in n-3 instead of n-2.
https://codeforces.me/blog/entry/135622?#comment-1214687
Also if we count the number of valid tree for any n it comes out to be $$$2^{n-3}$$$ so n-3 is also the minimum number of queries.
I feel like this should be the way every editorial should be written with good hints and simple language tutorial . Nice ;
It was a really great contest, thank you
Can someone hack this Problem C solution? https://codeforces.me/contest/2032/submission/289342682
I'm quite positive this is wrong but can't find a counterexample. Thank you!
I think your solution is correct, because when we meet $$$a[l]+a[r]\le a[i_0]$$$ we must replace either $$$a[l]$$$ with something greater or $$$a[i_0]$$$ with something smaller. But if we again meet $$$a[l]+a[r]\le a[i_1]$$$ where $$$l=i_0$$$ we again must replace either $$$a[l]$$$ with something greater or $$$a[i_1]$$$ with something smaller. So, we can not replace only $$$a[i_0]$$$ to save one operation.
But what about the case
1 1 1 2? Here, we can't increase $$$a[l]$$$ to 2 because1 2 1 2wont make a triangle. Instead, we need to decrease $$$a[i_0]$$$So, what is wrong? You need EITHER increase $$$a[l]$$$ OR decrease $$$a[i_0]$$$. You would need to increase $$$a[l]$$$ only if you further would need to increase $$$a[i_0]$$$.
For C, I just want to clarify some terminologies. When is it called sliding window instead of two pointers (or vice versa)? For me C sounded like it's a sliding window problem and not two pointers.
This is just my opinion, for a disclaimer.
I'll usually call something "sliding window" when it involves a fixed interval/range/subarray, and the updates of the window involves removing the leftmost and adding the rightmost per step.
for c i guess for 1st test case value is 2 for 7 1 2 3 4 5 6 7 for this test case 2 is minimum since array can become 7 7 3 4 5 6 7
7 7 3 4 5 6 7 is not valid since 3+4=7. You would have to replace the 3 with something else as well
Cool solution to E:
Let $$$b$$$ be an array of operations such that you "add 1" to the first position.
Let $$$c$$$ be the array of how many operations each position needs (i.e. $$$c_i = max(a) - a_i$$$).
The solution is the coefficients of $$$(\sum_{n=0}^{n-1} b_i x^i) (\sum_{n=0}^{n-1} c_i x^i)$$$, you can use FFT or any similar algorithm.
Details of the solution:
WLOG, assume the "Add 1" process is applying to the middle element $$$(i.e. a_{\frac{n+1}{2}})$$$ for easier calculation
Observe that
For $$$n = 5$$$ the array $$$b$$$ will be $$$[1,0,2,0,1]$$$
For $$$n = 7$$$ the array $$$b$$$ will be $$$[1,2,0,3,0,2,1]$$$
For $$$n = 9$$$ the array $$$b$$$ will be $$$[2,1,3,0,4,0,3,1,2]$$$
For $$$n = 11$$$ the array $$$b$$$ will be $$$[2,3,1,4,0,5,0,4,1,3,2]$$$
Hence we can guess that for any n. This code can geneate a array that add 1 to the middle element. (I will skip the proof here)
Then by rotating the array, we can get the desired $$$b$$$ that add 1 to the first element
e.g. $$$[2,0,1,1,0]$$$ for n = 5
My submission in contest : 289280927
Problem D. Can someone help me explain why the vertices is indexed in accordance to a BFS?
bfs order is (0, 1, 2, ..., m, m+1, m+2, m+4, m+5, m+3), but i dont see controdictions to px <= py iff x <= y
There is a contradiction in your graph, as the parent of m+3 is m+2, while the parent of m+4 is 3. Clearly, m+2 > 3, while m+3 < m+4.
Hi Naman!
AkiLotus hi! for problem c, why's the answer for the tc "1 1 2" one? shouldn't the answer be zero (because no pairwise distinct triplets exist?)
thank you for writing this round, it was fun!
"Pairwise-distinct" here applies for indices, not values.
Oops. Thank you for your quick reply.
I know I'm late, but i have a nice solution for E.
Look at the differences between adjacent elements. If you sum them you get 0 because the array is circular. You can notice that an operation adds [1, 1, -1, -1] to a subarray of the differences. The goal is to make this array 0, to make the original array constant.
After using this operation many times on alternating positions this happens (the parentheses are the center of the operation)
With these operations it's possible to move an unit from a point to another at distance -2. Since the length of the array is odd, then it's possible to move an unit to any other cell of the differences array by just repeating this process
290156342