Thank you for participating!
1979A  Guess the Maximum
Let $$$m$$$ be the maximum among the numbers $$$a_i, a_{i + 1},\ldots, a_j$$$. Notice that there always exists such $$$k$$$ that $$$i \le k < j$$$ and $$$a_k = m$$$ or $$$a_{k + 1} = m$$$. Therefore, we can assume that Bob always chooses the pair of numbers $$$p$$$ and $$$p + 1$$$ ($$$1 \le p < n$$$) as $$$i$$$ and $$$j$$$.
Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $$$min$$$ be the found minimum, then it is obvious that the answer is equal to $$$min  1$$$.
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t) {
int n;
cin >> n;
int a[n];
for (int& i : a) {
cin >> i;
}
int mini = max(a[0], a[1]);
for (int i = 1; i < n  1; i++) {
mini = min(mini, max(a[i], a[i + 1]));
}
cout << mini  1 << "\n";
}
}
1979B  XOR Sequences
Look at samples.
Consider two numbers $$$v$$$ and $$$u$$$ such that $$$x \oplus v = y \oplus u$$$. Then consider the numbers $$$x \oplus (v + 1)$$$ and $$$y \oplus (u + 1)$$$. Let's look at the last bit of $$$v$$$ and $$$u$$$. Possible scenarios:
 Both bits are equal to $$$0$$$ — adding one will change the bits at the same positions, therefore $$$x \oplus (v + 1) = y \oplus (u + 1)$$$;
 Both bits are equal to $$$1$$$ — adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit;
 Bits are different — adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that $$$x \oplus (v + 1) \neq y \oplus (u + 1)$$$.
It is clear that we need to maximize the number of zeros in the maximum matching suffix of $$$u$$$ and $$$v$$$. Obviously, this number is equal to the maximum matching suffix of $$$x$$$ and $$$y$$$. Let $$$k$$$ be the length of the maximum matching suffix of $$$x$$$ and $$$y$$$, then the answer is $$$2^k$$$.
This can be calculated in $$$O(\log C)$$$ time for one test case, where $$$C$$$ is the limit on $$$x$$$ and $$$y$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t) {
int a, b;
cin >> a >> b;
for (int i = 0; i < 30; i++) {
if ((a & (1 << i)) != (b & (1 << i))) {
cout << (1ll << i) << "\n";
break;
}
}
}
}
1979C  Earning on Bets
Try to come up with a condition for the existence of an answer.
Let $$$S$$$ be the total amount of coins placed on all possible outcomes. Then, if the coefficient for winning is $$$k_i$$$, we have to place more than $$$\frac{S}{k_i}$$$ on this outcome.
We can obtain the following inequality:
Dividing both sides by $$$S$$$, we obtain the necessary and sufficient condition for the existence of an answer:
This check can be performed by reducing all fractions to a common denominator. Notice that the numerators of the reduced fractions correspond to the required bets on the outcomes.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
void solve() {
int n;
cin >> n;
vector <int> k(n);
for (int i = 0; i < n; i++) {
cin >> k[i];
}
int z = 1;
for (int i = 0; i < n; i++) {
z = lcm(z, k[i]);
}
int suma = 0;
for (int i = 0; i < n; i++) {
suma += z / k[i];
}
if (suma < z) {
for (int i = 0; i < n; i++) {
cout << z / k[i] << " ";
}
cout << "\n";
} else {
cout << 1 << "\n";
}
}
signed main() {
int t;
cin >> t;
while (t) {
solve();
}
}
1979D  Fixing a Binary String
Let's consider the block of characters at the end. Notice that their quantity cannot decrease. Let $$$x$$$ be the number of identical characters at the end; there are three possible cases:
 $$$x = k$$$ — it is enough to find any block of length greater than $$$k$$$ and separate a block of length $$$k$$$ from it;
 $$$x > k$$$ — obviously, there is no solution;
 $$$x < k$$$ — find a block of length $$$k  x$$$ or $$$2k  x$$$ and separate a block of length $$$k  x$$$ from it.
This solution works in $$$O(n)$$$, but it is not the only correct one. Your solution may differ significantly from the one proposed.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int x = 0;
for (int i = n  1; i >= 0; i) {
if (s[i] == s[n  1]) {
x++;
} else {
break;
}
}
auto check = [&]() {
for (int i = 0; i < k; i++) {
if (s[i] != s[0]) return false;
}
for (int i = 0; i + k < n; i++) {
if (s[i] == s[i + k]) return false;
}
return true;
};
auto operation = [&](int p) {
reverse(s.begin(), s.begin() + p);
s = s.substr(p, (int)s.size()  p) + s.substr(0, p);
if (check()) {
cout << p << "\n";
} else {
cout << 1 << "\n";
}
};
if (x == k) {
int p = n;
for (int i = n  1  k; i >= 0; i) {
if (s[i] == s[i + k]) {
p = i + 1;
break;
}
}
operation(p);
} else if (x > k) {
cout << 1 << "\n";
} else {
bool was = false;
for (int i = 0; i < n; i++) {
if (s[i] != s.back()) continue;
int j = i;
while (j + 1 < n && s[i] == s[j + 1]) {
j++;
}
if (j  i + 1 + x == k) {
operation(j + 1);
was = true;
break;
} else if (j  i + 1  k + x == k) {
operation(i + k  x);
was = true;
break;
}
i = j;
}
if (!was) {
operation(n);
}
}
}
}
1979E  Manhattan Triangle
In every Manhattan triangle there are two points such that $$$x_1  x_2 = y_1  y_2$$$.
Note this fact: in every Manhattan triangle there are two points such that $$$x_1  x_2 = y_1  y_2$$$.
Let's start with distributing all points with their $$$(x + y)$$$ value.
For each point $$$(x; y)$$$ find point $$$(x + d / 2; y  d / 2)$$$ using lower bound method in corresponding set. Then we have to find the third point: it can be in either $$$(x + y + d)$$$ or $$$(x + y  d)$$$ diagonal. Borders at $$$x$$$ coordinate for them are $$$[x + d / 2; x + d]$$$ and $$$[x  d / 2; x]$$$ — it can be found using the same lower bound method.
Then, distribute all points with $$$(x  y)$$$ value and do the same algorithm.
Total time complexity is $$$O(n \log n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 1e5;
const int MAXD = 4e5 + 10;
set <pair <int, int>> diag[MAXD];
void solve() {
int n, d;
cin >> n >> d;
vector <int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
x[i] += MAXC;
y[i] += MAXC;
}
bool found = false;
{
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, 1});
if (it1 == diag[x[i] + y[i]].end()  it1>first != x[i] + d / 2) continue;
if (x[i] + y[i] + d < MAXD) {
auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, 1});
if (it2 != diag[x[i] + y[i] + d].end() && it2>first <= it1>first + d / 2) {
cout << i + 1 << " " << it1>second + 1 << " " << it2>second + 1 << "\n";
found = true;
break;
}
}
if (x[i] + y[i]  d >= 0) {
auto it2 = diag[x[i] + y[i]  d].lower_bound({x[i]  d / 2, 1});
if (it2 != diag[x[i] + y[i]  d].end() && it2>first <= it1>first  d / 2) {
cout << i + 1 << " " << it1>second + 1 << " " << it2>second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].erase({x[i], i});
}
}
if (!found) {
for (int i = 0; i < n; i++) {
y[i] = 2 * MAXC;
diag[x[i]  y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i]  y[i]].lower_bound({x[i] + d / 2, 1});
if (it1 == diag[x[i]  y[i]].end()  it1>first != x[i] + d / 2) continue;
if (x[i]  y[i] + d < MAXD) {
auto it2 = diag[x[i]  y[i] + d].lower_bound({x[i] + d / 2, 1});
if (it2 != diag[x[i]  y[i] + d].end() && it2>first <= it1>first + d / 2) {
cout << i + 1 << " " << it1>second + 1 << " " << it2>second + 1 << "\n";
found = true;
break;
}
}
if (x[i]  y[i]  d >= 0) {
auto it2 = diag[x[i]  y[i]  d].lower_bound({x[i]  d / 2, 1});
if (it2 != diag[x[i]  y[i]  d].end() && it2>first <= it1>first  d / 2) {
cout << i + 1 << " " << it1>second + 1 << " " << it2>second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i]  y[i]].erase({x[i], i});
}
}
if (!found) {
cout << "0 0 0\n";
}
}
int main() {
int t;
cin >> t;
while (t) {
solve();
}
}
1979F  Kostyanych's Theorem
Let's consider the following recursive algorithm. We will store the Hamiltonian path as a doubleended queue, maintaining the start and end.
In case there are only $$$1$$$ or $$$2$$$ vertices left in the graph, the problem is solved trivially.
Suppose we know that the current graph has $$$n$$$ vertices, and there are at most $$$(n  2)$$$ edges missing. Then the total number of edges in such a graph is at least
Let all vertices in the graph have a degree of at most $$$(n  3)$$$, then the total number of edges does not exceed
which is less than the stated value. Hence, we conclude that there is at least one vertex with a degree greater than $$$(n  3)$$$.
If there exists a vertex $$$v$$$ with a degree of $$$(n  2)$$$, then it is sufficient to run our recursive algorithm for the remaining graph. Since $$$v$$$ is only not connected by an edge to one vertex, $$$v$$$ is connected either to the start or the end of the maintained path in the remaining graph. Thus, we can insert the vertex $$$v$$$ either at the beginning or at the end of the path.
Otherwise, let $$$u$$$ be the vertex with a degree of $$$(n  1)$$$. There is at least one vertex $$$w$$$ with a degree not exceeding $$$(n  3)$$$. Remove $$$u$$$ and $$$w$$$ from the graph. Notice that the number of edges in such a graph does not exceed
The invariant is preserved, so we can run the algorithm for the remaining graph. Then, we can arrange the vertices in the following order: $$$w$$$ — $$$u$$$ — $$$s$$$ — ..., where $$$s$$$ — the start of the Hamiltonian path in the remaining graph.
It remains to understand how to use queries.
Make a query $$$d = (n  2)$$$. Let $$$u$$$ be the second number in the response to our query. If $$$u \neq 0$$$, the degree of vertex $$$v$$$ is $$$(n  2)$$$. Run our recursive algorithm, and then compare the start and end of the obtained path with $$$u$$$.
Otherwise, if $$$u = 0$$$, it means the degree of vertex $$$v$$$ is $$$(n  1)$$$. In this case, ask about any vertex with a low degree (this can be done with a query $$$d = 0$$$). Then simply arrange the vertices in the order mentioned above.
We will make no more than $$$n$$$ queries, and the final asymptotic will be $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
pair <int, int> ask(int d) {
cout << "? " << d << endl;
int v, u;
cin >> v >> u;
return {v, u};
}
pair <int, int> get(int n, vector <int>& nxt) {
if (n == 1) {
int v = ask(0).first;
return {v, v};
}
if (n == 2) {
int u = ask(0).first;
int v = ask(0).first;
nxt[u] = v;
return {u, v};
}
pair <int, int> t = ask(n  2);
int v = t.first;
int ban = t.second;
if (ban != 0) {
pair <int, int> res = get(n  1, nxt);
if (ban != res.first) {
nxt[v] = res.first;
return {v, res.second};
} else {
nxt[res.second] = v;
return {res.first, v};
}
} else {
int u = ask(0).first;
nxt[u] = v;
pair <int, int> res = get(n  2, nxt);
nxt[v] = res.first;
return {u, res.second};
}
}
void solve() {
int n;
cin >> n;
vector <int> nxt(n + 1, 1);
pair <int, int> ans = get(n, nxt);
int v = ans.first;
cout << "! ";
do {
cout << v << " ";
v = nxt[v];
} while (v != 1);
cout << endl;
}
int main() {
int t;
cin >> t;
while (t) {
solve();
}
}
C can be solved with Binary search,in case you have not thought of solution and still solved C using youtube and telegram,then it might help you.
U really want to help such cunts ?
i know its useless but still i want them to know their place.
I wrote the binary search solution but then I noticed that the for the second test case in the test case 1 there was a valid answer for sum = 4 but not for sum = 3. So I did not submit it. I eventually came up with the solution(without cheating) but I dont think we can use binary search here.
check my solution,you will get it
Nah bro It just worked out cause there are too many values of sum that satisfy the problem.
for the test case: n = 2; k1 = 3 and k2 = 3
clearly sum = 2 gives a valid answer sum = 3 does not give a valid answer sum = 4 gives a valid answer So the conditions to use binary search are not met
https://codeforces.net/contest/1979/submission/264505456
I just tried submitting my old solution too (binary search) and it got accepted but I still think this is wrong and can be hacked. what do you think?
.
I don't think binary search is the correct approach. It might have worked due to numerous values of sum satisfying the condition.
If you modify the binary search range and pick the lower end to be the sum of all the k values the solution will always work.As per the condition in the official solution we can characterize the 1/k summation as a Harmonic mean, and we always know that arithmatic mean is greater than harmonic mean. Also for any valid solution in the above constraint all the values above any valid solution are also valid as every k is atleast 2 and as we increase the total bet the gain will increase if we just keep adding to the previously found arrangement.
actually, if there exists a solution for the given set of numbers then we can use any value as a numerator and distribute accordingly take for example 3, 2, 7 has a solution so any number can be used to generate a valid distribution the catch is that it won't be an integer always, like if you take 1 then 1/3 1/2 and 1/7 are also valid distribution because they give sum as 41/42 and each winning return is 1 but this won't be accepted as a solution because it is not integer so we find a value such that it gives integer for all ki divisions and lcm happens to be the smallest such value. and for the binary search to work after a certain point, the values become big and we can increase mid/ki values by 1 and they give valid distributions
I really struggle with binary search problems, how to identify it in specific, can you help me some resources
Binary Search by Adtiya Verma is a great playlist if you are comfortable with Hindi.
I liked this: https://usaco.guide/silver/binarysearch
check my code: I just checked sum 10^9 and it is AC. 264511010
So many downvotes,did I offend the cheater community here.
get your concepts clear greenie
Surely i did.
actually no need to use binary search (as the upper bound values can always be used as sum of all elements and it will always suffice an answer if solution exists), just use sum = 1e9 and some necessary conditions for the answer to be true.
Yeah i wrote the same code
yeah but anyways the optimal choice of sum is LCM(k) — 1 if this does not work nothing will. Also I suggest you to actually solve the problem rather than taking shortcuts.
There is no such thing as shortcuts, LOL! AC is AC, and clever AC is even better.
I came up with the exact same implementation but it doesn't work for some reason, keeps giving me WA verdict on the 341st case of pretest 2. But glad to see that I had the right idea.
ya, solved using binary search only
haven't thought of binary search. simple observation was to find LCM ( it will factor all the elements and sum of all factors are always <=sum of numbers).
An alternate solution for D using hashing: the final string will be of form $$$s_{p+1}\dots s_n s_p\dots s_1$$$ and must either start with a block of $$$k$$$ 0s or $$$k$$$ 1s. Generate the two possible final strings ($$$111\dots000\dots$$$ or $$$000\dots111\dots$$$), then iterate over $$$i$$$ and check if either of the two answer strings match this condition:
Using hashing, each of these checks can be done in $$$O(1)$$$ for every position.
Thanks! Found it to be more intuitive than the posted solution
How to hash string? can you share some resources?
https://cpalgorithms.com/string/stringhashing.html
yes i also thought of same solution, but poor implimentation skills mine
Same, Indeed ! Way down we go!!!
correct me if i am wrong but for problem D, in the examples, i think for the last test case, p=5 is possibly a correct solution but the online judge says its wrong?
if you choose p = 5 then final string will be 110011000011 but this aint 2 proper coz there are 4 consecutive 0s at i=6, but the resulting string should be 001100110011
oh i get it, thanks, should have read the problem better
Thanks bananasaur for two possible final strings (111…000… or 000…111…).
I use this in a previous question of Atcoder, but here, my mind is not thinking in that direction, although it's trivial ; I only do work for finding p.
finally became green
justice for 6k rank for doing 3 problems in div2:(
what's up was this problem copied from somewhere??
I think the problems are less intense for a div 2.
Visual for 1979E
Animation showing valid points for pairs of points (in red and blue) that are $$$d=6$$$ Manhattan distance away from each other. The black dots are points that are both $$$d$$$ Manhattan distance away from both red and blue points. The black line shows how there always exists a pair of points in a triangle such that they are $$$(d/2,d/2)$$$ or $$$(d/2,d/2)$$$ off.
Here's a Desmos graph with draggable points if you want an interactive version. https://www.desmos.com/calculator/na6auayf25
This is very cool! What did you use to make the animation?
I used the processing.js library on Khan Academy's coding environment with the following code.
Sorry for the code messiness.
Then I recorded screen and exported as gif.
Any idea how I can improve my logic? some questions just don't click sometimes. I seem to be practicing consistently, but the results are not showing. I don't know why
you're either doing practice with too hard or too easy problems, try changing the difficulty and solve problems on multiple platforms other than codeforces
However, improvement takes a long time to see and you should not give up
if i am bouncing between, 12001300,what should be the ideal rating to solve?
https://codeforces.net/contest/1979/submission/264505456
Hey guys this is a solution for C using binary search but I think this approach is wrong and inconsistent with the problem If you agree Please someone hack the solutions that used this approach. If I am wrong please explain why this works?
somehow, the code only checks the sums x/2, 3x/4, 7x/8, so on... (here, x=n*10^9) at most +32 checks.
[as the k
i
is small enough maybe after a certain range any value matches the condition]check my code: I just checked sum 10^9 and it is AC. 264511010
simple o(n) solution of D : https://codeforces.net/contest/1979/submission/264506463 BASIC BRUTEFORCE WITH SOME OPTIMISATION
also c sol: https://codeforces.net/contest/1979/submission/264445819
Does anyone have a proof of why the hint for E is true?
First, draw the graph from $$$(x, y)$$$ to all the points which can be at distance $$$d$$$. It will look like a square rotated by $$$45°$$$. Now, if one of the point of our answer is one of the diagonal points $$$(x \pm d / 2, y \pm d / 2)$$$, then we are done (the condition satisfies). Now, after some observation on the graphs (and drawing pairs on the square which have distance d in them). You can notice that if none of the diagonal points are used then the other $$$2$$$ points are on the same side/line (there are $$$4$$$ sides of the square). And thus, the condition is again satisfied. (since if we take the square from any one of them, the other would be diagonal point).
F is just mind blowing, very elegant and very nice : )
Can someone explain the hint of E? Why/How is it true?
Assume on $$$x$$$ axis sides give projections of $$$n,m,n+m$$$. Then on $$$y$$$ axis we must have $$$dn,dm,dnm$$$. Two of them sum to the third, so $$$2d2nm=dm$$$, so $$$n=\frac{d}{2}$$$, which is what we wanted.
First, draw the graph from $$$(x, y)$$$ to all the points which can be at distance $$$d$$$. It will look like a square rotated by $$$45°$$$. Now, if one of the point of our answer is one of the diagonal points $$$(x \pm d / 2, y \pm d / 2)$$$, then we are done (the condition satisfies). Now, after some observation on the graphs (and drawing pairs on the square which have distance d in them). You can notice that if none of the diagonal points are used then the other $$$2$$$ points are on the same side/line (there are $$$4$$$ sides of the square). And thus, the condition is again satisfied. (since if we take the square from any one of them, the other would be diagonal point).
Another approach in problem E, which reduces the amount of code to write: 264470284
Solution
Let's observe that all the points on the distance d(in Manhattan metrics) from a fixed point make up a square with a diagonal of length 2d. With this knowledge we can rotate the plain by 45° and scale it, so that the sides of those squares are parallel to the axises and have integer lengths.
After that the solution is easy: we have to find two points on a vertical or horizontal line, the distance between which is d. Let's call those points A and B. The third point has to lie on CD, where ABCD is a square.
Can anyone explain me problem D using bitmask
Really shameful, I couldn't solve anything after A
just checking sum=10^9 gives AC in problem C.
264511010
same lol that is what i did as well
Why? Can you explain the intution why this works please
Can anyone explain why for D in the following sample case
the verdict is
1
.Can't we take
p = 1
, the transformation would then be1101
which is 2proper as s1 = s2 = '1' and s1 != s3it not matching the k
Sorry, can you be more specific?
For example, with k=3 , the strings 000, 111000111, and 111000 are k proper, while the strings 000000, 001100, and 1110000 are not.
Do you mean that the second condition $$${s_{i+k} \neq s_i}$$$ should hold for every $$${i}$$$ in the range $$${1 \le i \le n  k}$$$. But in the problem statement, it says the second condition should hold for any i in that range. iNNNo, if that's the case, shouldn't the second condition be $$${s_{i+k} \neq s_i}$$$ for every $$${i}$$$ ($$${1 \le i \le n  k}$$$)?
Bro read the problem again
I've read it many times, still I am not able to understand. Can you explain why 1101 is not 2proper?
1011
i
1
=1i
2
=1i
3
= i1+k
= 0i
4
= i2+k
= 1you can see that i
2
=i4
. so that it is not a k proper.2proper: 110011, 1100, 0011, 001100.
non2proper: 1001, 1101, 1011
Thank you Mamun01. I also got confused with the word 'any'.
Welcome, Bro..
264505361. My sol to B.
What is the logic behind the code? What observation of yours lead to this solution? BTW I was not able to solve the B problem.
I just look into the examples and notice that the answer is the last bit of the difference and make sense to me, then I proof it by accepted.
D can be solved with FFT:
(note that polynomials are $$$0$$$indexed while arrays are $$$1$$$indexed and this is a somewhat overengineered solution)
first the nonfft part: if a p is "ok", then first_k($$$a[p + 1; n] + rev(a[1; p])$$$) (i.e. the first k elements in the new array) must be equal;
we can simply count it in an array $$$e$$$ with $$$e_i = \text{maximum number}$$$ s.t. $$$a[i; i + e_i]$$$ are all equal
for every i it must hold that $$$new_a[i] \ne new_a[i + k]$$$. this can be precomputed for all indices except for the indices in $$$[i  k; i)$$$ with $$$rev((p  k; p])$$$ (since $$$new_a = a_{p+1} a_{p+2} ... a_n a_p a_{p  1} ...$$$, we need to check that $$$a_n \ne a_{p  k}, a_{n  1} \ne a_{(p  k)  1}$$$) Note that while the lhs is decreasing, the rhs is increasing.
now we can use fft to check whether that conditions holds for all indices: Let $$$P_1 = c_1 * x^k + c_2 * x^{k + 1} * ... * c_n * x^{k + n}$$$ be a polynomial of degree $$$n + k$$$ and $$$P_2 = c_{n  k + 1} * x^0 + c_{n  k + 2} * x^1 + ... + c_n * x^k$$$ a polynomial of degree $$$k$$$.
If we multiply both polynomials we get the following polynomial:
Each coefficient should represent "how different" $P_1$ and $$$P_2$$$ are (at that position), so we can choose $$$c_i = 1$$$ if $$$a_i = 1$$$, $$$c_i = 1$$$ otherwise. If we multiply two equal numbers, i.e. $$$1 * 1$$$ or $$$1 * 1$$$, we both get the result $$$1$$$, while the result of two different numbers is $$$1 * 1 = 1$$$. So a "more negative" result means a bigger difference in the strings. In the "middle" of the string ($$$k \le p \le n  k$$$), it is enough to check whether $$$[x^{k + i  1}] P_{res} = k$$$ ($$$[x^{k + i}]$$$ is the coefficient of $$$x^{k + i}$$$), since that means that all values in a are different.
If e.g. $$$k = 2$$$ and $$$p = 2$$$, the resulting bitstring is: $$$a_3 a_4 a_5 ... a_n a_2 a_1$$$, i.e. we only need to check whether $$$a_n \ne a_1$$$. Luckily $$$P_1$$$ "starts with" $$$x^k$$$, i.e. $$$[x^k] P_{res}$$$ is $$$c_1 * c_n$$$, which is the check of "is $$$a_n \ne a_1$$$"; exactly what we need! So in that case we only have to check whether $$$[x^{k + i  1}] P_{res} == i$$$
But what about $$$p \in (n  k; n]$$$? Similar to the case where $$$p$$$ is small, we have to consider less than k values; e.g. for $$$p = n  1, k = 2: a_n a_{n  1} a_{n  2} ....$$$
Here we have to compare $$$a_n$$$ and $$$a_{n  2}$$$, but $$$[x^{k + (n  2)  1}] P_{res} = c_{n  2} * c_n + c_{n  1} * c_{n  1}$$$. Since we are now additionally comparing $$$a_{n  1}$$$ and $$$a_n$$$ (and for other $$$p/k$$$ the last $$$k  (n  p)$$$ values are compared "within the array itself"), we have to "correct" this by "undoing" the fft ops (add $$$1/+1$$$ depending on whether two of these duplicate comparisons match).
With this information it is enough to iterate over all possible $$$p$$$ and check in $$$O(1)$$$ if all conditions hold. (we also have to exit early if we encounter some $$$a[p] \ne a[p  k]$$$ since some $$$p$$$ is only "ok" if all indices after it in the new sequence still "match" (and reversing $$$a_1 a_2 ... a_p$$$ doesn't really change that condition, so $$$a[p] \ne a[p  k]$$$ is enough)
since fft runs in $$$O(n \log n)$$$ and the rest is $$$O(n)$$$ the total runtime is $$$O(n \log n)$$$
Proof by AC: https://codeforces.net/contest/1979/submission/264505623
Edit: Formatting
For problem C :
I used Binary Search.
I guessed total number of coins. For every mid, I go through all bets and calculated minimum coins are needed to be bet on ith position. Then if total number of required coins is less or equal than my mid then it’s okay to bet that amount of coins.
If no valid mid found then simply it’s impossible.
Using this strategy, I calculated the minimum possible coins that satisfies the conditions.
After that I distributed the coins for every ith bet such a way that if I win ith bet I get at least tootal coins. If some coins stays unused, then I distributed the remaining coins among all bets almost equilibrium way.
Finally I checked wheather any position I bet more than 1e9 or not. If yes, then I said it’s impossible otherwise this is the answer. (I don't know is it required to check, it may not affect the solution but I remained in safety).
I think this binary search approach is more easy to understand with less mathmatical calculation .
My submission : 264454935
I also used binary search during contest, but after it I came up with easier solution: https://codeforces.net/contest/1979/submission/264516424
The main idea is that if it is solvable, then your overall coins should be maximized
Yes, It's more easy and simple solution
Can you explain the solution ??
So, the observations I made:
x
coins, then for each outcome you should bet(x / multiplier[i]) + 1
to have your winnings strictly greater than your initial coins.1
.x
coins, then it is also possible to do it withx+1
coins (because the multipliers make the winnings greater, not smaller). That is why binary search comes in handy.x
big. So there is. A solution that always usesx
as10^9
.Hope it was useful.
No you are wrong For test case n = 2; k1 = 3 k2 = 3 sum = 2 and sum = 4 give valid answers but sum = 3 does not. Binary search approach may have worked but it wont work for all constraints. The optimal choice of sum is (LCM(k1,k2,k3 .....) — 1) if this is not a valid sum then sum does not exist. True for all constraints!!!
E: https://usaco.org/current/data/sol_triangles_platinum_feb20.html
D: Suppose we split s into a+b where a has p characters. Then, the end result is b+rev(a). I find it helpful to take note that if s is proper where k is a factor of n (in other words the string ends with a block of length k), then so rev(s), so we just need rev(b+rev(a))=a+rev(b) to be proper.
But how do you check if a + rev(b) is k proper or not in O(n) for every possible suffix b?
Guessforces on problem B. The fourth test case was a huge giveaway when I saw it was a power of two.
Samee
very good contest,adds me 200 points
if i changed "int" into "long long" in C, my solution will be accepted...still lack of experience :(
Can someone explain more intuitively why checking for 1e9 and lcm works in problem C?
1e9 > simply if this does not work for max number of coins then it will never work, Probability of the condition working increases with increase in number of coins as Multiplication function rises faster than addition.
LCM > just use basic algebra on ki*xi > Sum(xi), you eventually reach 1 > Sum(1/ki). Common thing between 1/ki and LCM is that in both cases you ignore common factors or take their frequency as 1.
I can only explain both mathematically because I am used to doing everything this way, maybe writing it out will help you, write the equation down and use a rough graph in 1e9 case if you are comfortable with basic algebra and drawing rough graphs, hope this helps.
Still the 1e9 condition does not guarantee that if there is a sum>=1e9 then there will always be a sum for numbers <1e9(let's consider the number to be x) for whom sum>x. There might be numbers<1e9 for which there exist a solution even though there does not exist a solution for 1e9.
For example let's take {2,3,7} as the given array and let's take our value of x as 43. so for 43 the bet array will be{(43/2)+1,(43/3)+1,(43/7)+1}={22,15,7} and their sum is 22+15+7 which is greater than 43. So there exist no solution according to the 1e9 logic it means. But if we take 42 there exist an answer.
So I think the testcases are so designed that this logic works but it will not work for more precise testcases I guess.
but your k1*x1 does not match in case 1, 22*2 != 43, 15*3 != 43 and 7*7 != 43. Main condition of the problem is ki*xi > sum(xi). You assumed ki*xi to be 43 but your calculations show otherwise.
The multiplication function increases much faster than addition, using 43 as a sample input is flawed checking, 1e9 is a much larger number than 43 and will be much larger than any xi unless ki == 1 in which case there is no solution.
You need to think of a test case where your sum == ki*xi and ki*xi > sum(xi). forgoing one condition to prove another is not the right way. I used LCM btw and not 1e9 but I myself still cannot find anything wrong with 1e9 solution considering the given constraints. It would be great if you could point out the error in the math but as of your comment using sum = 43 is a mathematically incorrect example.
I have some intuition for E I would like to share including one way you could have proved the hint.
Let's map our original coordinate system from $$$(x,y)$$$ to $$$(x+y,xy)=(x',y')$$$. This makes the manhattan distance between two points $$$max(x1'x2',y1'y2')$$$.
The idea of rotating coordinates this way is mentioned on page 73 of the competitive programmer's handbook which is where I got the idea from. There isn't an explanation to why it works, so I'll explain that here.
One important insight about absolute values like $$$x1x2$$$ is how you can decompose it into only two different possibilities $$$(x1x2)$$$ or $$$(x2x1)$$$. When determining the absolute value, all you simply need to do is take the maximum of the two possibilities. There are many problems where decomposing absolute values into their possibilities can help solve the problem. Using this insight you can try to solve 1859E  Maximum Monogonosity if you also know some dp.
The Manhattan distance between any two points is $$$x1x2+y1y2$$$. Using the above statement, we can decompose $$$x1x2$$$ and rewrite the statement as $$$max(x1x2+y1y2,x2x1+y1y2)$$$. If we do the same for $$$y$$$, we can see that to find the Manhattan distance we only need to choose the maximum of one of four options:
$$$max(max(x1x2+y1y2,x1x2+y2y1),max(x2x1+y1y2,x2x1+y2y1))$$$
If we rearrange the terms:
$$$max(max((x1+y1)(x2+y2),(x1y1)(x2y2)),max((x2y2)(x1y1),(x2+y2)(x1+y1)))$$$
And then swap which values get maxed together:
$$$max(max((x1+y1)(x2+y2),(x2+y2)(x1+y1)),max((x1y1)(x2y2),(x2y2)(x1y1)))$$$
We can now compose each inner max as an absolute value: $$$max((x1+y1)(x2+y2),(x1y1)(x2y2))$$$
This is sometimes a nice way to look at Manhattan distance because we can now process each dimension independently if we convert the points from $$$(x,y)$$$ to $$$(x+y,xy)$$$.
Based on this definition, when two points have a manhattan distance of d, that means that one of $$$x1'x2'$$$ or $$$y1'y2'$$$ equals $$$d$$$ and the other is less than or equal to $$$d$$$. For my insight, I like to think of the manhattan distance as "using" either the $$$x'$$$ distance or $$$y'$$$ distance, whichever is bigger.
When looking at a manhattan triangle, at least one point in the triangle will either use $$$x'$$$ twice or use $$$y'$$$ twice when finding the distance with its neighbors. We can prove this by considering a triangle ABC. Let edge AB use $$$x'$$$. For A to not use $$$x'$$$ twice, edge AC must use $$$y'$$$. Once you've done this, however, there will be a vertex that either uses $$$x'$$$ twice or uses $$$y'$$$ twice no matter what dimension that we choose for our third edge BC.
Let's fix point $$$(x1',y1')$$$ as a point in the triangle that uses the same dimension twice. Given the dimension used twice is the $$$x'$$$ dimension (the following holds for $$$y'$$$ too), we know that the following holds:
$$$x2=x1+d$$$ or $$$x2=x1d$$$
and
$$$x3=x1+d$$$ or $$$x3=x1d$$$
If we choose one point to have an $$$x'=x1'+d$$$ and the other to have an $$$x'=x1'd$$$, that means that the $$$x'$$$ distance between points 2 and 3 will be at least $$$2*d$$$ which fails the triangle condition. This means that we have to choose $$$x2'$$$ and $$$x3'$$$ to both be $$$x1' + d$$$ or both be $$$x1'  d$$$. This therefore proves that $$$x2'=x3'$$$ which is incredibly useful.
The hint suggests that there must exists two points such that $$$x1x2=y1y2$$$. In my proof I suggest that there must exist two points such that either $$$x1'=x2'$$$ or $$$y1'=y2'$$$. If I were to undo the transformation for my coordinates, my statement is: $$$x1+y1=x2+y2$$$ or $$$x1y1=x2y2$$$. We can transform my statement to $$$x1x2=y1y2$$$ or $$$x1x2=(y1y2)$$$. This means that $$$x1x2$$$ is either equal to or is the inverse of $$$y1y2$$$. When you take the absolute value of both sides, the sign for both becomes positive and therefore they must be equal.
$$$x2'=x3'$$$ clearly indicates $$$x2'x3'=0$$$, so for there to be a valid Manhattan triangle we must use the other dimension $$$y'$$$ such that $$$y2'y3'=d$$$. Let $$$y2$$$ be the smaller value of $$$y2$$$ and $$$y3$$$. To solve this problem from here, what I did is look at all possible values of $$$(x2',y2')$$$ and see if any point exists such that $$$x2'$$$=$$$x3'$$$ and $$$y2' + d = y3'$$$. With those two points, all you need to check is if there exists a point with $$$x1'$$$ equal to $$$x2'd$$$ or $$$x2'+d$$$ such that $$$x'$$$ is the used dimension (i.e. the $$$y'$$$ distance of the original point is not greater than $$$d$$$ which is true iff $$$y2' <= y1' <= y3'$$$). Once we do this we can switch $$$x'$$$ and $$$y'$$$ and run the algo again for the case where point 1 uses $$$y'$$$ twice. Once I fixed a given point $$$(x2',y2')$$$, I was able to search for the other points using maps and binary searches which all took logarithmic time.
You can see my solution here: 264520131
very very elegant explanation!
Can someone explain C to me again? I mean, why the condition SUM(S/ki) < S ??
we have to find x1,x2,...,xn such that
x1 + x2 + ... + xn = S
x1*k1 > S > x1 > S/k1
x2*k2 > S > x2 > S/k2
....
xn*kn > S > xn > S/kn
thus S = x1 + x2 + ... + xn > S/k1 + S/k2 + ... + S/kn (or SUM(S/ki) < S)
I guessed B and C. in B answer was 2^lowestbiton(a xor b) in C numbers just turned out to be lcmofwholearray/arr[i] (and if it does not work print1 )
In the editorial of C, where is the mention of LCM? You just can't expect everything to be understood beforehand. Please try to write editorial in a proper way.
Can you explain the editorial for C please ??
How I see problem E, is that if there is a Manhattan triangle, it can always be seen as having a first point $$$(x, y)$$$ and two other points having in a certain common relative direction to that first point — one of the two is on
diag1
, the other is ondiag2
(just the segment, not the infinite line), and the two diagonals intersect at, WLOG, assuming the common direction is to the right, $$$(x+d, y)$$$. The image looks something like this:I actually managed to forget that without an anchor at either $$$(x + \frac{d}{2}, y + \frac{d}{2})$$$ or $$$(x + \frac{d}{2}, y  \frac{d}{2})$$$, the two ondiagonal points may not have the distance to each other at $$$d$$$. Silly me, this costed my chance for a quick jump to 19502000ish given that I solved ABCD absurdly quickly, and I AC'd E in like 3 minutes after figuring out the mistake. :(
Well, another lesson to take anyway.
Some $$$O(n^2)$$$ Solutions(264481866) passed problem D easily.
Why $$$n \le 10^5$$$?
Hey, could u please share the O(n^2) solutions that u r stating? For some reasons, I can't open the link.
Sorry, fixed.
Uphacked. ~1s solutions are the fastest ones I could hack, I guess.
Can you please hack my submission? I want to test my solution. Here's the link: link Thanks!
Python solutions aren't hackable because $$$\mathcal{O}(n^2)$$$ solutions wouldn't have passed in the first place. I don't see anything in your code that would make it $$$\mathcal{O}(n^2)$$$ and the current time seems reasonable for a $$$O(n)$$$ solution with large constant of hashing and Python.
Well, I tried and it only took 999 ms.
Thanks a lot! I used mod value as 2**64 1 which made python use big int and hence it was little slow. Changing it to 10**9 + 7 (a 32 bit integer) made it significantly quicker. To be safe, I'll consider using double hash with 2 32 bit integer mod values in future.
I had solved C at the 25 minute mark and could not approach D for a long time. I was trying to find the first point where the string deviates from being k proper, coded it and just before I could submit,the contest ended. Some days you just can't win
Nice copied code :0
Love how you project your insecurities on everyone around here.I am willing to prove how I coded it myself, contact me privately if you want more clarification
Bro could you tell me how to figure our the solution for B? It seems so random to me
Just check how many bits in the binary representation of x and y are same from the right.To further explain it xor of a series of numbers would be same for both x and y values till the binary representation is same and when it differs the subsequence will not exist. I just checked if (x%2)==(y%2) and increased count. Then printed pow(2,cnt)
Could someone please explain how the condition given in solution of C is sufficient? We have not taken into account that the bet placed on any outcome needs to be an integer right?
But if we do take that into account, the necessary and sufficient condition then looks like (sigma 1/ki)+(n/S) <= 1, where we don't know S.
If the condition is met, you can always choose an
S
that is multiple of any of thek
's by picking S =LCM(k_1, k_2, ... k_n)
. Thus anyS/k_i
will result in an integer making the equation trivial.Thanks a lot.
It was quite a nice contest! Altough it would've been better if some losers didnt cheat problem C. Very good contest!
Earning on bets detailed video editorial
https://youtu.be/tipb5tYyHAQ?feature=shared
F is a good problem, but there are a few issues in the solution!
"at least (n−2) edges missing" should be "at most".
$$$\dfrac{n(n  1)}{2}  (n  2)  (n  1)  (n  3) + 1$$$ should be $$$\dfrac{(n  2)(n  3)}{2}  (n  4)$$$ (not $$$n  3$$$), thus the invariant is keeped!
Thanks!
in problem F, imagine the following case that 5 vertices have degree = n — 1. And when solving the problem recursively say we needed to query "? d" {d <= n — 3} and imagine no vertices have degree between [d , n — 2]. Clearly the answer to any such query will be the same as answer of "? n — 1" . How will we proceed in such a case , as we have no way to know which vertex had degree >=d ? {There will be uncertainty}
The problem C can be solved using a big number instead of LCM too. It was AC by my guess, without using LCM. A totally guessforces round!
Guessforces!!
can any one give me a proof about this fact from tutorial
Note this fact: in every Manhattan triangle there are two points such that x1−x2=y1−y2.
a lot of users solved B using:
how does that work?
A computer sees negative numbers using the 2's complement method. Basically, it flips all the bits, then adds one to the result. For example:
001 becomes 110, then 111 after adding one.
You can observe that this operation preserves the state of all zeros until the first one, then flips all the other bits. Because of this, the result will have a shared one in the least significant bits only. If you perform a bitwise AND operation on these two numbers, you will get the least significant bit
d & d
computes the least significant (set) bit, i.e. the "rightmost (least significant)" bit set to one. this is also used in fenwick trees: see here (wikipedia article)I did D by finding the first index( dentoed by j in my solution) where the string is not kproper. Shifting it to the left if the condition in the last test case happens ( I am not able to explain it properly. Sorry for that.)
{In this test case  110001100110. I check if there are k 0's from j so that it forms a valid if I perform the operation.}
But My solution is not working on 2010 test case in 2nd Test. I have hit a roadblock here. Can anybody help
I have the same problem!! Do you have solved it? I can't find where the mistake is.
My expert frnd just said my approach is incorrect
But why (ToT) How can we find some counterexample
I have been accepted!! Look at this→ https://codeforces.net/contest/1979/submission/266091447 It's in python
Nice!
I am trying to understand ur code. Can you tell what mistake u found? Was your code also getting stuck at 2010th testcase?
After the change, my code looks like this: judge the length of each substring that consists of all 1s or 0s, and if it's less than k, then cut it at the end; if it's equal to k, then judge the next substring; if it's greater than k, then cut it at the k positions before the end, and then finally judge whether the changed string is compliant or not. In fact, it looks like I only added some breaks to my previous code.
Thanks, I also made a silly error. Got it now.
For the C why the all possible winnings outcome must be the same. Is there any logic behind that assertion?
Edit : got it, have not read well the editorial.
For problem C, I made a deadly mistake. The lcm of a and b equals a*b/gcd(a,b), so I think the lcm of a,b,c and d is a*b*c*d/gcd(a,b,c,d).In fact, it only works in two nums.
e.g.:
4 5 8
lcm: 40
而 gcd(8,5,4) == 1
8*5*4 == 160[尴尬]
Even if it was correct, you can't store 20^50 and then divide it
Yeah..Thanks,I also make a mistake: 2^64 is not 1e64 ..hh
I didn't AC this promblem is the reason.
In problem C, I get that if the coefficient for winning is k_i, we have to place more than S/k_i on this outcome. For each i=1 to n , this should hold...so summing should give the inequality ∑S/k_i< n* S But then how are we getting the inequality ∑S/k_i<S ?
Also, what's the logic behind taking lcm as the total no of coins to bet?
1) S is the total amount placed on all bets. Since each bet is larger than S/k_i, summation of all bets is larger than summation of S/k_i, that is, S is larger than summation of S/k_i.
2) LCM is not taken as total number of coins to bet, rather it is a value greater than total number of coins to bet. The return we get on any of the outcomes is equal to the LCM, and is thus greater than the total (enforced by the check ∑(1/k_i) < 1), hence this distribution of bets is an acceptable solution.
Thanks a lot.
solution for problem c with the binary search

For some reason, I guessed the solution for B and C and they were right! Here's how I did it:
B: I noticed that the last testcase's answer is 33554432, which i remembered as a power of two (2^25), and so are the other testcases' answers. After this exploration, I tried to find how were the last testcase were related to 2^25, and finally found that the difference between x and y was divisible by 2^25, but not 2^26. So I concluded that the answer must be the largest power of two that is a divisor of abs(x — y). I then submitted the solution and got an AC. The entire process took 8 minutes.
C: What had catched my attention was the really weird constraints on n and k. My immediate thought was that it was related to the answer of the problem not surpassing 1e9 (x limit) somehow. After that, I think it must be somehow related to the LCM of the array, and it was right, after me testing my theory on the example testcases. I submitted and got AC without proving that my solution was right.
I did D afterwards, really enjoyed the problems, good contest!
For me, B came after I decided not to give up and just keep trying until the end of the contest. I realized that both sequences would be 0 at some point, and at this point, we would continue increasing the index by 1 each time. So here, I just did
I would really like to know if I got any real benefit from this because I'm not sure. I mean, it took almost an hour of brainstorming, and I just want it to take 45 minutes the next time.
Hi all, I am new here on codeforces.
I tried solving the last contest's (Div2 951) problems and was easily able to solve problem A, but I couldn't come up with a solution for problem B. Can anyone please help me understand the approach, as my mind was completely blank on what to do? What was your guys intuition behind the approach? I also couldn't understand the editorial's hint and solution. Your help would be much appreciated. Sorry, I'm not very good at Codeforces and am a beginner just trying to understand things.
For people who did not understood editorial of problem C maybe this will help
Essentially what the editorial is this for Problem C
let coins we place in bet be c1,c2,c3,c4, ... ,cn and c1 + c2 + c3 +...+ cn = S
then the following inequalities are formed based on conditions proposed by the question
divide by k on both sides
add them all up the ineqality still holds
fraction addition
let lcm = lcm(k1,k2,k3,...,kn) then (lcm/k1 + lcm/k2 + lcm/k3 + ... + lcm/kn) / lcm < 1
multiply by lcm on both sides
(lcm/k1 + lcm/k2 + lcm/k3 + ... + lcm/kn) < lcm
and this is your final condition for answer
please correct me if my calculations are wrong
Perfect proof... first of all thanks for providing this.All the authors should learn from this proof that they should provide the detailed step by step proof in laymen language, that would be great for people who struggles to proof in their initial days!!
nice. finally understood. thank you
for C, I understood that 1>(1/a1+1/a2.....1/an) as the sum will cancel out from both sides undoubtedly and we have to just select the sum so that it yields an integer by every array element division hence it's the LCM. But can someone explain me what happens if one element of the array is LCM itself? It is clearly visible that it would be wrong but proof it if someone can please
A short straight forward implementation using 2 pointers for D : 264776035
Can someone please explain intuition and proof for hint of problem E?
In every Manhattan triangle there are two points such that x1x2 = y1y2
For C, I think it's testing such a thing:
In fact, for 1/k1 + 1/k2 + 1/k3 + ... + 1/kn, we need to unify the denominators when we sum them up, which means multiplying each k by a different number.
For example:
2 3 6: 1/2 + 1/3 + 1/6 = (3+2+1)/6 = 6/6
2 3 7: 1/2 + 1/3 + 1/7 = (21+14+6)/42 = 41/42
Similarly, the numerators represent the amount of money allocated to each position, but the denominator is always greater than the total amount of money.
21*2>41 ; 14*3>41 ; 6*7>41
Testing: Whether the sum of fractions with numerators of 1 is greater than or equal to 1
I solved C using binary search here is my intuition let say a1,a2,a3,a4,a5,a6,a7....n are the multipliers given for each position in a sorted order and c1,c2,c3,c4,c5...cn are coins used by us at each position in an optimal way , now let say S is the total sum of coins used here. a1 is the minimum multiplier we have from this I observed that S < a1*c1 so S can be at max a1*c1 — 1 so I did binary search on c1 coins but here as we don't need to find the minimum possible coins and we just need to find whether it is possible or not I just continued my mid towards right end.please excuse me for my poor english and if my approach is wrong please let me know. My submission(264463858)
Thanks for Editorial very much! But can u see my code for C, i think it's also a good way for this problem: 264471661
in problem C code why z/k[i] and not k[i]/z ??
check this comment. He have explained it clearly. https://codeforces.net/blog/entry/130213#comment1157423
thanks man
I just learnt from problem C after reading 20 different code and watching 3 youtube videos that if you encounter an array and math problem just randomly think about LCM and no intuition needed
ok
Ok
In D there may be such case: s = "1011", p = 4 As I understood the string will be: "1101", this means that the length of the last block will reduce, which contradicts first statement in the author's solution. Somebody tell me, where I made a mistake?