Идея: m3tr0
Если для всех $$$i$$$ $$$(1 \leq i \leq n - 1)$$$ верно $$$|a_i - a_{i+1}| = 5$$$ или $$$|a_i - a_{i+1}| = 7$$$, ответ на задачу — "YES", иначе — "NO".
Сложность: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
bool solve(){
int n;
cin >> n;
vector<int>a(n);
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 1; i < n; i++) {
if(abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7) return false;
}
return true;
}
int main() {
int t;
cin >> t;
while(t--){
cout << (solve() ? "YES" : "NO") << "\n";
}
}
Идея: Seny
Заведем массив brand_cost
длиной $$$k$$$ и заполним его так, что brand_cost[i]
хранит стоимость всех бутылок бренда $$$i+1$$$. Затем отсортируем массив по невозрастанию и посчитаем сумму его первых min(n, k)
элементов, что и будет ответом на задачу.
Сложность: $$$O(k \cdot \log k)$$$
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> brand_cost(k, 0);
for (int i = 0; i < k; i++) {
int b, c;
cin >> b >> c;
brand_cost[b - 1] += c;
}
sort(brand_cost.rbegin(), brand_cost.rend());
long long ans = 0;
for (int i = 0; i < min(n, k); i++) {
ans += brand_cost[i];
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Идея: m3tr0
При каждом запросе, чтобы отследить изменение наличия "1100" в строке, не обязательно проходить по всей строке — можно проверить только несколько соседних клеток.
Сначала наивным способом посчитаем $$$count$$$ — количество раз, которое "1100" встречается в $$$s$$$.
Далее для каждого из $$$q$$$ запросов будем обновлять $$$count$$$: рассмотрим подстроку $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ до изменения $$$s_i$$$ и найдем $$$before$$$ — количество раз, которое "1100" встречается в ней. После этого обновим $$$s_i = v$$$ и аналогично найдем $$$after$$$ — количество раз, которое "1100" встречается в $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ после применения запроса.
Таким образом, выполнив $$$count = count + (after - before)$$$, мы получим количество раз, которое "1100" встречается в $$$s$$$ после применения запроса. Если $$$count > 0$$$, ответ на запрос — "YES", иначе — "NO".
Сложность: $$$O(|s| + q)$$$
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long l;
char buf[1000000];
l n;
bool check_1100(l i) {
if (i < 0) return false;
if (i >= n - 3) return false;
if (buf[i] == '1' && buf[i + 1] == '1' && buf[i + 2] == '0' && buf[i + 3] == '0') return true;
return false;
}
void solve() {
scanf("%s", buf);
n = strlen(buf);
l count = 0;
for (l i = 0; i < n; i++)
if (check_1100(i)) count++;
l q; scanf("%lld", &q);
while (q--) {
l i, v; scanf("%lld %lld", &i, &v); i--;
if (buf[i] != '0' + v) {
bool before = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
buf[i] = '0' + v;
bool after = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
count += after - before;
}
printf(count ? "YES\n" : "NO\n");
}
}
int main() {
l t; scanf("%lld", &t);
while (t--) solve();
}
Идея: eugenechka.boyko.2_0-0
Будем идти по всем слоям ковра, добавляя к ответу число встреченных записей $$$1543$$$ на каждом слое. Для этого можно итерироваться по, например, левым верхним клеткам каждого из слоев, имеющим вид $$$(i, i)$$$ для всех $$$i$$$ в диапазоне $$$[1, \frac{min(n, m)}{2}]$$$, после чего делать обход слоя наивным алгоритмом, записывая встреченные цифры в какой-нибудь массив. Затем пройдёмся по массиву и посчитаем вхождения $$$1543$$$ в этот слой. Также при обходе массива нужно учесть цикличность слоя, не забыв проверить возможные вхождения $$$1543$$$, содержащие стартовую клетку.
Сложность: $$$O(n \cdot m)$$$
#include <cstdio>
char a[1005][1005];
char layer[4005];
void solve() {
int n, m; scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%s", a[i]);
int count = 0;
for (int i = 0; (i + 1) * 2 <= n && (i + 1) * 2 <= m; ++i) {
int pos = 0;
for (int j = i; j < m - i; ++j) layer[pos++] = a[i][j];
for (int j = i + 1; j < n - i - 1; ++j) layer[pos++] = a[j][m - i - 1];
for (int j = m - i - 1; j >= i; --j) layer[pos++] = a[n - i - 1][j];
for (int j = n - i - 2; j >= i + 1; --j) layer[pos++] = a[j][i];
for (int j = 0; j < pos; ++j)
if (layer[j] == '1' && layer[(j + 1) % pos] == '5' && layer[(j + 2) % pos] == '4' && layer[(j + 3) % pos] == '3')
count++;
}
printf("%lld\n", count);
}
int main() {
int t; scanf("%d", &t);
while (t--) solve();
}
Идея: m3tr0
Для любых целых неотрицательных чисел выполняется $$$a \leq a | b$$$, где $$$|$$$ — операция побитового "или".
После вычисления значений $$$b_{i,j}$$$ для всех стран и регионов, мы можем заметить, что для фиксированного региона $$$j$$$ значения $$$b_{i,j}$$$ возрастают с увеличением индекса $$$i$$$. Это происходит потому, что операция побитового "или" не может уменьшить число, а только увеличивает или оставляет его неизменным. Следовательно, мы можем использовать бинарный поиск для быстрого нахождения страны, которая соответствует заданным условиям.
Для каждого запроса и для каждого требования, если знак $$$o$$$ = "<", мы ищем первую страну, где $$$b_{i,r} \geq c$$$ (это будет первая страна, не удовлетворяющая условию). Если же знак $$$o$$$ = ">", мы ищем первую страну, где $$$b_{i,r} \leq c$$$. В обоих случаях мы можем использовать стандартный бинарный поиск для нахождения индекса. Если в результате проверок осталась хотя бы одна страна, которая удовлетворяет всем требованиям, выбираем страну с наименьшим номером.
Сложность: подсчёт значений $$$O(n \cdot k)$$$, обработка каждого запроса с помощью бинарного поиска $$$O(m \log n)$$$, итого $$$O(n \cdot k + q \cdot m \cdot \log n)$$$.
#include <cstdio>
typedef long long l;
l ** arr;
int main() {
l n, k, q; scanf("%lld %lld %lld", &n, &k, &q);
arr = new l*[n];
for (l i = 0; i < n; i++) arr[i] = new l[k];
for (l i = 0; i < n; i++) for (l j = 0; j < k; j++) scanf("%lld", &arr[i][j]);
for (l i = 1; i < n; i++) for (l j = 0; j < k; j++) arr[i][j] |= arr[i - 1][j];
while (q--) {
l m; scanf("%lld", &m);
l left_pos = 0, right_pos = n - 1;
while (m--) {
l r, c; char o; scanf("%lld %c %lld", &r, &o, &c); r--;
if (o == '<') {
l le = -1, ri = n, mid;
while (le + 1 != ri) {
mid = (le + ri) / 2;
if (arr[mid][r] < c) le = mid;
else ri = mid;
}
if (le < right_pos) right_pos = le;
} else {
l le = -1, ri = n, mid;
while (le + 1 != ri) {
mid = (le + ri) / 2;
if (arr[mid][r] <= c) le = mid;
else ri = mid;
}
if (ri > left_pos) left_pos = ri;
}
}
if (left_pos <= right_pos) printf("%lld\n", left_pos + 1);
else printf("-1\n");
}
}
Идея: eugenechka.boyko.2_0-0
Обратите внимание на основание модуля
Можем ли мы быстро вычислить XOR на отрезке $$$[l, r]$$$?
Рекомендуем также красивый разбор задачи от justlm!
Введём обозначение $$$\DeclareMathOperator{\XOR}{XOR}\XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$$$ .
Первое, что приходит в голову при прочтении условия, это что мы можем вычислить XOR всех чисел на отрезке $$$(0, x)$$$ за $$$O(1)$$$ по следующей формуле:
Тогда $$$\XOR(l, r)$$$ можно найти как $$$\XOR(0, r) \oplus \XOR(0, l-1)$$$.
Теперь заметим, что для ответа нам достаточно научиться за $$$O(1)$$$ находить XOR всех неинтересных на отрезке: тогда мы сможем сделать XOR со всем отрезком и получить XOR уже всех интересных чисел.
Основание модуля, равное степени двойки, выбрано не случайно: нам достаточно "сжать" $$$l$$$ и $$$r$$$ в $$$2^i$$$ раз таким образом, чтобы в полученном диапазоне лежали все неинтересные числа, сдвинутые на $$$i$$$ битов право. Тогда вычислив $$$\XOR(l', r')$$$ мы получим в точности искомый XOR неинтересных чисел, также сдвинутый на $$$i$$$ битов вправо. Тогда, чтобы найти эти оставшиеся младшие $$$i$$$ битов, нам достаточно найти количество неинтересных чисел на отрезке $$$[l, r]$$$. Если оно будет нечётным, эти $$$i$$$ битов будут равны $$$k$$$, поскольку все они равны $$$k \mod 2^i$$$, а значит имеют одинаковые $$$i$$$ младших битов, равные собственно $$$k$$$, а значит их XOR нечетное число раз будет также равен $$$k$$$.
В противном случае младшие $$$i$$$ битов ответа будут равны $$$0$$$, так как мы сделали XOR чётное число раз. Количество неинтересных чисел на отрезке можно вычислить похожим с $$$\XOR(l, r)$$$ способом, а именно найти их количество на отрезках $$$[0, r]$$$ и $$$[0, l-1]$$$ и вычесть второе из первого. Количество чисел, равных $$$k$$$ оп модулю $$$m$$$ и не превышающих $$$r$$$ вычисляется как $$$\left\lfloor \frac{r - k}{m} \right\rfloor$$$.
Сложность решения по времени: $$$O(\mathit{\log r})$$$.
#include <iostream>
using namespace std;
#define int uint64_t
#define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
int xor_0_n(int n) {
int rem = n % 4;
if (rem == 0) {
return n;
}
if (rem == 1) {
return 1;
}
if (rem == 2) {
return n + 1;
}
return 0;
}
int xor_range(int l, int r) {
return xor_0_n(r) ^ xor_0_n(l - 1);
}
int32_t main() {
int t;
cin >> t;
while (t--) {
int l, r, i, k;
cin >> l >> r >> i >> k;
int highBits = xor_range((l - k + (1 << i) - 1) >> i, (r - k) >> i) << i;
int lowBits = k * (((r - k) / (1 << i) - (l - k - 1) / (1 << i)) & 1);
cout << (xor_range(l, r) ^ highBits ^ lowBits) << '\n';
}
return 0;
}
Идея: m3tr0
Рассмотрели ли вы те случаи, когда $$$a \oplus b \oplus c = 0$$$?
Предположим, что вы точно уверены в том, что хотя бы одно потерянное число расположено на некотором отрезке $$$[le, ri]$$$. Можете ли вы выбрать такое значение $$$mid$$$, при котором по запросам xor {le} {mid}
и xor {mid + 1} {ri}
вы сможете однозначно понять, на каком из отрезков ($$$[le, mid]$$$ или $$$[(mid + 1), ri]$$$) лежит хотя бы одно потерянное число, даже если оба эти запроса вернут $$$0$$$?
Для начало отметим, что для любого числа $$$x$$$ выполняется $$$x \oplus x = 0$$$. Поэтому запрашивая xor l r
, вы получите побитовый XOR только тех номеров томов, которые находятся в библиотеке в единственном экземпляре (в рамках запроса $$$l$$$ и $$$r$$$, конечно). Также отметим, что для двух попарно различных чисел $$$x$$$ и $$$y$$$ всегда выполняется $$$x \oplus y \neq 0$$$.
Изначально наша цель — определить наибольший бит максимального из потерянных чисел. Для этого можно пройтись по битам, начиная от наибольшего значащего бита в n. Для каждого $$$i$$$-го бита будем запрашивать xor {2^i} {min(2^(i + 1) - 1, n)}
. Заметим, что у всех чисел на этом интервале $$$i$$$-й бит равен единице. Тогда если мы получили результат не равный нулю, то этот бит является искомым наибольшим битом максимального из потерянных чисел. Если же мы получили результат равный нулю, то этот бит гарантированно не присутсвует в ни одном из чисел, т.е. все три числа меньше, чем $$$2^i$$$.
Докажем это. Если бы у нас находились одно или два числа на запрошенном интервале, то их XOR был бы не равен $$$0$$$ (см. первый абзац). Если же все три числа расположены на этом интервале, то XOR их $$$i$$$-го бита равен $$$1 \oplus 1 \oplus 1 = 1$$$, и следовательно XOR самих чисел также отличен от $$$0$$$.
Теперь, когда мы знаем наибольший бит $$$i$$$ искомого числа, мы можем найти это число любой реализацией бинарного поиска внутри интервала $$$[2^i; min(2^{i + 1} - 1, n)]$$$. По ответу на любой запрос на каком-либо интервале внутри этого мы можем однозначно понять, присутствует ли наше число на этом интервале, или нет — доказательство аналогичное выше приведённому.
Первое число найдено. Второе число можно считать уже любым бинпоиском, так как XOR двух различных чисел всегда отличен от нуля. Главное не забывать "исключать" уже найденное число из полученного результата с помощью того же XOR-а. А третье число можно найти, запросив результат всего интервала от $$$1$$$ до $$$n$$$ и "исключив" из него уже найденные два числа.
Количество запросов: $$$\approx 2 \cdot \log n \approx 120 < 150$$$.
#include <cstdio>
typedef long long l;
l n, num1, num2;
l req(l le, l ri, l num) {
if (le > n) return 0;
if (ri > n) ri = n;
printf("xor %lld %lld\n", le, ri); fflush(stdout);
l res; scanf("%lld", &res);
if (num > 1 && le <= num1 && num1 <= ri) res ^= num1;
if (num > 2 && le <= num2 && num2 <= ri) res ^= num2;
return res;
}
void solve() {
scanf("%lld", &n); num1 = 0; num2 = 0;
l start = 1LL << (63 - __builtin_clzll(n));
for (l i = start; i > 0; i >>= 1) {
l res = req(num1 | i, num1 | (i * 2 - 1), 1);
if (res) num1 |= i;
}
for (l i = start; i > 0; i >>= 1) {
l res = req(num2 | i, num2 | (i * 2 - 1), 2);
if (res) num2 |= i;
}
printf("ans %lld %lld %lld\n", num1, num2, req(1, n, 3));
fflush(stdout);
}
int main() {
l t; scanf("%lld", &t);
while (t--) solve();
}
make better pretests next time.
true
true
can anyone please explain what is logically wrong in this code: https://codeforces.me/contest/2036/submission/289551678 (it is failing on test case 35). thanks in advance!
I have just removed two break statements from ur code and it got AC. Here is the AC submission.
thanks, much appreciated!
спасибо за местечко в разборе! задача F мне очень зашла еще при тестинге, особенно, когда я решал ее вместо географии :)
алсо: чтобы название функции в $$$\LaTeX$$$ отображалось без наклона и при этом не надо было писать \text, то можно написать \DeclareMathOperator{\shortname}{displayname}
алсо 2: в русском едиториале очепятка. "Количество чисел равных $$$k$$$ ОП модулю $$$m$$$ равно ...", предлагается исправить
Ага, спасибо, поправлю
Problem F can also be solved using digit dp.
i just read your lines that was really nice in the ending
Mar Gaye Ehsaas Meray, Chubay Wo Ilfaaz Teray, Tumne Dekha Tak Na Jaty Way,
I read a little bit of that code and it seems the code cant really solve for a number NOT a power of 2 (the constant time solution doesnt either). If I understand correctly you are checking if the first i bits of the number are different or not and xorring the remaining numbers. Can you extend your solution to range xor with a similar constraint but % x where x can be anything?
Yes You are exactly correct, this code only handles when x is a power of 2. I had thought about the case when x is not a power of 2 and I could solve it for small values of x only($$$<=1000$$$) by having an additional state for the current remainder of the prefix.
I couldn't find a better solution either, the best I could do was the same as you, I guess I should attach my code in case anyone in the future wants to know.
can you explain your solution, especially how you are ensuring that the remainder is not k ?
Thanks in Advance!
A number mod power of two, $$$2^i$$$ is just the last $$$i$$$ bits in it's binary representation.
We can use digit dp in the following way: Suppose you want to build an n digit binary number. Pick a digit (0/1 in this case) and place it at the leftmost space, you are left with n — 1 digits, now you need to count how many numbers are possible to be built in total after placing those n — 1 digits. To do this simply recursively start to add digits and keep track of whether the number you have built so far is a valid number or not. When you reach the end of the number, if the build is valid you return 1, otherwise 0. You can very efficiently count the possible valid numbers you can place in those n — 1 spots.
Now if the count is odd then you know that your current digit (which you picked first) will appear in the net xor sum (If the picked digit was 1 of course, if it was 0 then it won't appear anyway), hence you can store this net xor sum by the following line:
$$$xsum_i$$$ ^= (1 << (n — i — 1)) ^ $$$xsum_{i + 1}$$$ for both the digits 0/1 which you put in ith spot. This represents the transition.
To store both the count of how many times the build starting from ith place to the end appears and xor of all such numbers can be stored separately in two different arrays or you can just use a pair or array<int, 2> like I did here: 290112812
can anyone please tell me whats wrong with this solution 289604455
BitForces
L contest , if you don't know how to make test cases don't make contests
If you don't know how to make testcases, don't make contests only for fun . L contest
289481978 why is this wrong , this is O(klogk)
https://codeforces.me/blog/entry/101817
but why did it give tle
In short, carefully constructed inputs will lead to hash collisions when inserting into/updating a dictionary in Python, and that results in a significantly worse time complexity and thus TLE (each individual insert/update can be O(n)). The link outlines how to avoid this issue. For this problem, you can also use a list/array.
289592707 why is this wrong , can someone tell ?
because you break the loop while reading, it will cause your next query reading the wrong input.
Instead of if l>=r then break, use if l<r then solve()
Alternate Solution for Problem G
Let $$$\text{XOR}(1, n)$$$ denote the XOR of all elements from the first to the $$$n$$$-th element in the array.
Case 1:
If $$$\text{XOR}(1, n) = 0$$$, the numbers are structured to cancel out in pairs, leaving us with three values: $$$x$$$, $$$y$$$, and $$$x \oplus y$$$. We then query $$$\text{XOR}(1, h)$$$ for each $$$h$$$ starting from $$$h = 1$$$ until we find the smallest $$$h$$$ such that $$$\text{XOR}(1, h) \neq 0$$$. At this point, $$$\text{XOR}(1, h)$$$ isolates the first missing element $$$x$$$ because all other numbers in this subrange occur in pairs and cancel out.Case 2:
If $$$\text{XOR}(1, n) \neq 0$$$, we aim to locate the smallest subarray where $$$\text{XOR}(1, \text{mid}) = 0$$$. We perform a binary search to identify this position, isolating the unpaired number in that range. This number, $$$x$$$, is then equal to $$$\text{XOR}(1, \text{low})$$$ where low marks the boundary.After identifying $$$x$$$, we search for $$$y$$$, the second unpaired element, starting in the range $$$[x+1, n]$$$:
We perform XOR queries from $$$a + 1$$$ to $$$\text{mid}$$$ until encountering a position where $$$\text{XOR}(x + 1, \text{mid}) \neq 0$$$. This value $$$y$$$ is isolated by $$$y = \text{XOR}(a+1, \text{low})$$$.
Finally, the third number $$$z$$$ can be computed as: $$$z = \text{total_xor} \oplus x \oplus y$$$
Nice idea ! can u tell me why u used
(in case where xor of 1 to n is 0 , I had same idea for everything else but couldnt figure out how to find first XD)
instead of
The 2nd one is giving TLE , why it is guaranteed that one of them has 1st bit set ?
when you are using former, it's guaranteed that the range has odd number of elements meaning (the pairs+the alone element), but if it has even number of elements in range the it would have (even number of pairs + 2 elements once, and would be the starting of another pair/the other removed element), so we won't really be able to find the solution via 2nd approach.
got it thanks !
please try to improve your pretests next time
Shitty testcases
ya man but entertaining to see B,C,D,E,F getting hacked
Could someone explain what went wrong for me in this submission for D?: https://codeforces.me/contest/2036/submission/289572926
The loop for going over all spirals should be till min(m, n)/2 not n/2. I changed this part of your code and submitted it. Got AC.
Oh Wow, unlucky. Thanks for helping.
I think F can be solved in O(1) time instead of O(log r) since bitwise XOR runs in constant time.
yes. similar to the prefix xor from 1 to n, prefix xor from 1*(2^i+m) to n*(2^i+m) also have a pattern. check my submission https://codeforces.me/contest/2036/submission/289710030 it can be proved by inductive reasoning
F is very nice, solved it using some bit tricks, but was thinking about some digit dp solution does it exits ? like dp(n, tight, flag) building n digit number with tight telling us that it is smaller than (say r) and flag telling us about if to take the new string number formed?
So my code gets accepted when I use a
2D char array
but not when I usevector<string>
(Fails on testcase 2)
Any idea what might be causing this?
Thanks!
A chad for doing it in C
UPD: Figured. I was breaking out of the loop at the end, which was skipping inputs.
For Problem E, the code works fine for test 9 (and gives correct output) on my PC as well as custom invocation (attached) but it gives RTE (on test 9) when I submit it. I am not able to find any undefined behaviour in my code. Can someone help me where the potential RTE could be in my code?
Submission
Can someone point out the logical errors in my code? Thanks. It's wrong on test 4, case 51.
Seeing that many hacks in div3, especially in ABCDE problems is hilarious. I hope next time pretests will be much better. Great contest anyway.
can anyone help me... i really dont understand why should this be giving a wrong answer https://codeforces.me/contest/2036/submission/290070503
A simpler solution to the problem D. Hope this helps!!!
---CODE---
Сan someone explain why this formula for calculating XOR(0;x) works? Why are we looking on x (mod 4)???
For problem C, I'm getting AC on the one given in the tutorial, and TLE in the code, which I've written. Thing is, both codes are exactly the same except for the format for input taking. Someone see to it. AC — https://codeforces.me/contest/2036/submission/291926108 TLE — https://codeforces.me/contest/2036/submission/291925987 infact, this one too gives TLE — https://codeforces.me/contest/2036/submission/291924193
In the check function, you are directly passing string s which results in a new copy everytime the function is called. Use pass by reference instead. Your Submission. The other one uses a global buffer.
Thanks a lot man, it really made me learn something new
For problem E, why Complexity:O(n⋅k+q⋅m⋅logn) won't TLE, (q is 1e5 and m is 1e5)