Idea: m3tr0
If for all $$$i$$$ $$$(1 \leq i \leq n - 1)$$$ is true $$$|a_i - a_{i+1}| = 5$$$ or $$$|a_i - a_{i+1}| = 7$$$, the answer to the problem is “YES”, otherwise it is “NO”.
Complexity: $$$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";
}
}
Idea: Seny
Let's create an array brand_cost
of length $$$k$$$ and fill it so that brand_cost[i]
stores the cost of all bottles of brand $$$i+1$$$. Then sort the array by non-growing and calculate the sum of its first min(n, k)
elements, which will be the answer to the problem.
Complexity: $$$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;
}
Idea: m3tr0
With each query, to track the change in the presence of “1100” in a row, you don't have to go through the entire row — you can check just a few neighboring cells.
First, in a naive way, let's count $$$count$$$ — the number of times “1100” occurs in $$$s$$$.
Then for each of $$$q$$$ queries we will update $$$count$$$: consider the substring $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ before changing $$$s_i$$$ and find $$$before$$$ — the number of times that “1100” occurs in it. Then update $$$s_i = v$$$ and similarly find $$$after$$$ — the number of times that “1100” occurs in $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ after applying the query.
Thus, by doing $$$count = count + (after - before)$$$, we get the number of times that “1100” occurs in $$$s$$$ after the query is applied. If $$$count > 0$$$, the answer to the query is “YES”, otherwise it is “NO”.
Complexity: $$$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();
}
Idea: eugenechka.boyko.2_0-0
We will go through all layers of the carpet, adding to the answer the number of $$$1543$$$ records encountered on each layer. To do this, we can iterate over, for example, the top-left cells of each layer having the form $$$(i, i)$$$ for all $$$i$$$ in the range $$$[1, \frac{min(n, m)}{2}]$$$, and then traverse the layer with a naive algorithm, writing the encountered digits into some array. Then traverse the array and count the $$$1543$$$ occurrences in that layer. Also, when traversing the array, we should take into account the cyclic nature of the layer, remembering to check for possible occurrences of $$$1543$$$ containing a starting cell.
Complexity: $$$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();
}
Idea: m3tr0
For any non-negative integers, $$$a \leq a | b$$$, where $$$|$$$ is the bitwise “or” operation.
After computing the values of $$$b_{i,j}$$$ for all countries and regions, we can notice that for a fixed region $$$j$$$, the values of $$$b_{i,j}$$$ increase as the index $$$i$$$ increases. This is because the bitwise “or” operation cannot decrease a number, but only increase or leave it unchanged. Hence, we can use binary search to quickly find the country that matches the given conditions.
For each query and for each requirement, if $$$o$$$ = “<”, we search for the first country where $$$b_{i,r} \geq c$$$ (this will be the first country that does not satisfy the condition). If sign $$$o$$$ = “>”, we look for the first country where $$$b_{i,r} \leq c$$$. In both cases, we can use standard binary search to find the index. If the checks leave at least one country that satisfies all the requirements, we choose the country with the lowest number.
Complexity: counting values $$$O(n\cdot k)$$$, processing each query using binary search $$$O(m \log n)$$$, total $$$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");
}
}
Idea: eugenechka.boyko.2_0-0
Note the base of the module
Can we quickly compute XOR on the segment $$$[l, r]$$$?
We also recommend the beautiful tutorial by justlm!
Let us introduce the notation $$$\DeclareMathOperator{\XOR}{XOR}\XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$$$ .
The first thing that comes to mind when reading the condition is that we can compute XOR of all numbers on the segment $$$(0, x)$$$ for $$$O(1)$$$ by the following formula:
Then $$$\XOR(l, r)$$$ can be found as $$$\XOR(0, r) \oplus \XOR(0, l-1)$$$.
Now note that for the answer we only need to learn for $$$O(1)$$$ to find XOR of all uninteresting on the segment: then we can do XOR with the whole segment and get XOR of all interesting numbers already.
The base of the modulus, equal to the degree of two, is not chosen by chance: we only need to “compress” $$$l$$$ and $$$r$$$ by $$$2^i$$$ times in such a way that the resulting range contains all uninteresting numbers shifted $$$i$$$ bits to the right. Then computing $$$\XOR(l', r')$$$ we get exactly the desired XOR of uninteresting numbers, also shifted $$$i$$$ bits to the right. Then, to find these remaining lower $$$i$$$ bits, we just need to find the number of uninteresting numbers on the segment $$$[l, r]$$$. If it is odd, these $$$i$$$ bits will be equal to $$$k$$$, since they are all equal to $$$k \mod 2^i$$$, and so have the same $$$i$$$ minor bits equal to $$$k$$$ proper, and so their XOR an odd number of times will also be equal to $$$k$$$.
Otherwise, the lower $$$i$$$ bits of the answer will be $$$0$$$, since we have done XOR an even number of times. The number of uninteresting numbers on the segment can be calculated in a similar way to $$$\XOR(l, r)$$$, namely find their number on the segments $$$[0, r]$$$ and $$$[0, l-1]$$$ and subtract the latter from the former. The number of numbers equal to $$$k$$$ modulo $$$m$$$ and not exceeding $$$r$$$ is calculated as $$$\left\lfloor \frac{r - k}{m} \right\rfloor$$$.
Time complexity of the solution: $$$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;
}
Idea: m3tr0
Have you considered the cases where $$$a \oplus b \oplus c = 0$$$?
Suppose you are certain that at least one lost number is located on some segment $$$[le, ri]$$$. Can you choose a value $$$mid$$$ such that the queries xor {le} {mid}
and xor {mid + 1} {ri}
you can unambiguously understand on which of the segments ($$$[le, mid]$$$ or $$$[(mid + 1), ri]$$$) lies at least one lost number, even if both of these queries return $$$0$$$?
To begin with, we note that for any number $$$x$$$, $$$x \oplus x = 0$$$ is satisfied. Therefore, by querying xor l r
, you will get bitwise XOR of only those volume numbers that are in the library in a single copy (within the scope of querying $$$l$$$ and $$$r$$$, of course). Also note that for two pairwise distinct numbers $$$x$$$ and $$$y$$$, $$$x \oplus y \neq 0$$$ is always satisfied.
Initially, our goal is — to determine the largest bit of the maximum of the lost numbers. To do this, we can go through the bits starting from the largest significant bit in n. For each $$$i$$$-th bit, we will ask xor {2^i} {min(2^(i + 1) - 1, n)}
. Note that all numbers on this interval have $$$i$$$-th bit equal to one. Then if we get a result not equal to zero, then this bit is the desired largest bit of the maximum of the lost numbers. If we get a result equal to zero, then this bit is guaranteed not to be present in any of the numbers, i.e. all three numbers are less than $$$2^i$$$.
Let's prove it. If we had one or two numbers on the requested interval, their XOR would not be $$$0$$$ (see the first paragraph). If all three numbers are on this interval, then the XOR of their $$$i$$$-th bit is $$$1 \oplus 1 \oplus 1 = 1$$$, and hence the XOR of the numbers themselves is also different from $$$0$$$.
Now that we know the largest bit $$$i$$$ of the desired number, we can find this number by any realization of binary search inside the interval $$$[2^i; \min(2^{i + 1} - 1, n)]$$$. By the answer to any query on any interval within that interval, we can unambiguously know whether our number is present on that interval or not — the proof is similar to the one above.
The first number is found. The second number can be found using any bin search, since XOR of two different numbers is always different from zero. The main thing is not to forget to “exclude” the already found number from the obtained result using the same XOR. And the third number can be found by requesting the result of the whole interval from $$$1$$$ to $$$n$$$ and “excluding” the already found two numbers from it.
Number of requests: $$$\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!
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
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!
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)