Thank you for participating! I hope you enjoyed the tasks.
One of the testers (redpanda) did a wonderful video analysis tasks A-C, I highly recommend watching it.
Tutorial
Tutorial is loading...
Solution (74TrAkToR)
t = int(input())
for T in range(t):
la, lb = map(int, input().split())
ra, rb = map(int, input().split())
if la > lb:
la, lb, ra, rb = lb, la, rb, ra
if la < lb and rb < ra:
print("NO")
else:
print("YES")
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include <bits/stdc++.h>
using namespace std;
void solve(){
long long x, y, k;
cin >> x >> y >> k;
while (k > 0 && x != 1) {
long long ost = (x / y + 1) * y - x;
ost = max(1ll, ost);
ost = min(ost, k);
x += ost;
while (x % y == 0) {
x /= y;
}
k -= ost;
}
cout << x + k % (y - 1) << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Hint 1
All the numbers $$$a_{i}$$$ are positive, can it help somehow?
Hint 2
Try using dynamic programming.
Tutorial
Tutorial is loading...
Solution 1 (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000007;
void solve(){
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
vector<long long> pref(n + 1);
for (int i = 0; i < n; i++){
pref[i + 1] = pref[i] + a[i];
}
vector<int> dp(n + 1);
int s = 0;
int j = -1;
for (int i = 0; i < n; i++){
dp[i + 1] = max(dp[i + 1], dp[i]);
if (j < i){
j = i;
s = 0;
}
while(j < n && s < l){
s += a[j++];
}
if (s >= l && s <= r){
dp[j] = max(dp[j], dp[i] + 1);
}
s -= a[i];
}
cout << dp[n] << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Solution 2 (74TrAkToR)
t = int(input())
for T in range(t):
n, l, r = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
cur = 0
L, R = 0, 0
while L < n:
while R < n and cur < l:
cur += a[R]
R += 1
if l <= cur and cur <= r:
ans += 1
L = R
cur = 0
else:
cur -= a[L]
L += 1
print(ans)
1982D - Beauty of the mountains
Hint 1
How does the difference between heights change if we choose a specific submatrix?
Hint 2
It is worth reducing the problem to a mathematical construction. Maybe something from number theory can help?
Tutorial
Tutorial is loading...
Solution (FelixArg)
import math
def solve():
n, m, k = map(int, input().split())
a = [[int(x) for x in input().split()] for j in range(n)]
s = [input() for i in range(n)]
pref = [[0 for i in range(m + 1)] for j in range(n + 1)]
diff = 0
for i in range(n):
cur = 0
for j in range(m):
if s[i][j] == '1':
cur += 1
diff += a[i][j]
else:
diff -= a[i][j]
pref[i + 1][j + 1] = pref[i][j + 1] + cur
if diff == 0:
print("YES")
return
g = 0
for i in range(n - k + 1):
for j in range(m - k + 1):
f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j]
f = abs(k * k - 2 * f)
g = math.gcd(g, f)
if g == 0 or diff % g != 0:
print("NO")
else:
print("YES")
if __name__ == "__main__":
t = int(input())
for _ in range(t):
solve()
1982E - Number of k-good subarrays
Hint
Try using the divide-and-conquer approach.
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
map<pair<long long, int>, tuple<int, long long, long long>> mem;
tuple<int, long long, long long> calc(long long n, int k){
if (k < 0){
return tuple{0, 0ll, 0ll};
}
if (n == 1){
return tuple{1, 1ll, 1ll};
}
int bit = 63 - __builtin_clzll(n);
long long mid = (1ll << bit);
if (mid == n){
mid >>= 1;
if (mem.count({n, k})){
return mem[{n, k}];
}
}
auto [f1, s1, e1] = calc(mid, k);
auto [f2, s2, e2] = calc(n - mid, k - 1);
int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD;
f1 = (f1 * 1ll - sub1 + MOD) % MOD;
int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD;
f2 = (f2 * 1ll - sub2 + MOD) % MOD;
long long p = (e1 + s2) % MOD;
int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD;
long long s_cur = s1;
long long e_cur = e2;
if (s1 == e1 && s1 != 0){
s_cur = (s1 + s2);
}
if (s2 == e2 && s2 != 0){
e_cur = (e1 + e2);
}
if ((mid << 1) == n){
mem[{n, k}] = tuple{f_cur, s_cur, e_cur};
}
return tuple{f_cur, s_cur, e_cur};
};
void solve(){
long long n;
int k;
cin >> n >> k;
cout << get<0>(calc(n, k)) << '\n';
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Hint
If you maintain a set of such indexes $$$i$$$ that $$$a_{i} <a_{i - 1}$$$, then can this help in any way?
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000007;
struct SegTree{
vector<int> mn, mx;
int n;
SegTree(int _n): n(_n){
mx.assign(2 * n, -inf);
mn.resize(2 * n, inf);
}
void upd(int pos, int val){
mx[pos + n] = val;
mn[pos + n] = val;
pos = (pos + n) >> 1;
for (;pos > 0; pos >>= 1){
mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]);
mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]);
}
}
pair<int,int> get(int l, int r){
pair<int,int> res = {-inf, inf};
l += n;
r += n + 1;
for (;l < r; l >>= 1, r >>= 1){
if (l & 1) {
res.first = max(res.first, mx[l]);
res.second = min(res.second, mn[l++]);
}
if (r & 1) {
res.first = max(res.first, mx[--r]);
res.second = min(res.second, mn[r]);
}
}
return res;
}
};
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
SegTree tree(n);
set<int> st;
for (int i = 0; i < n; i++){
tree.upd(i, a[i]);
if (i > 0 && a[i] < a[i - 1]){
st.insert(i);
}
}
function<int(int, int)> find_pref = [&](int pos, int x){
if (pos < 0){
return 0;
}
int l = 0, r = pos;
while(l <= r){
int m = l + (r - l) / 2;
if (a[m] > x){
r = m - 1;
}
else{
l = m + 1;
}
}
return r + 1;
};
function<int(int, int)> find_suff = [&](int pos, int x){
if (pos >= n){
return n - 1;
}
int l = pos, r = n - 1;
while(l <= r){
int m = l + (r - l) / 2;
if (a[m] >= x){
r = m - 1;
}
else{
l = m + 1;
}
}
return r;
};
function<void()> query = [&](){
if (st.empty()){
cout << -1 << ' ' << -1 << '\n';
return;
}
int l = *st.begin() - 1;
int r = *(--st.end());
auto [mx, mn] = tree.get(l, r);
cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n';
};
query();
int q;
cin >> q;
for (int i = 0; i < q; i++){
int pos, val;
cin >> pos >> val;
pos--;
if (pos > 0 && a[pos] < a[pos - 1]){
st.erase(pos);
}
if (pos + 1 < n && a[pos + 1] < a[pos]){
st.erase(pos + 1);
}
a[pos] = val;
tree.upd(pos, val);
if (pos > 0 && a[pos] < a[pos - 1]){
st.insert(pos);
}
if (pos + 1 < n && a[pos + 1] < a[pos]){
st.insert(pos + 1);
}
query();
}
}
int main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
for (int test = 0; test < tests; test++){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
First. good problems I think.
I'm sorry that the good problems failed to appear in the contest, hope that we can see the problems later:)
Thank you fast editorial
C. Most of the people have done this using dp. I didn't get the dp logic, but I tried it another way. For each position i, check the nearest position(let's say idx) on the right side which gives sum>=l (this can be done with lower bound and prefix sum, and also check if sum<=r). So you will have several i,idx intervals. Put them in a vector. Now all you need to do is find maximum non overlapping intervals, which is a standard leetcode problem.
that's cool! simple sliding window would suffice too
I can't figure out why my solution wrong? Please help me. My submission link. 267434800
Please try this dataset: 5 6 8 5 5 1 2 5 The correct answer is 2 by 5+1 and 2+5, but your program outputs 1?
Note that it does not input the number of test cases T.
Can you please figure out which test case my code isn't passing .Here is the submission id. 267473714
I don't quite understand Java programming, but your error seems similar to the original poster's error, both involving incorrect starting positions in a sliding window. For example, in this dataset (without T): 3 6 8 3 1 5, your output is 0, but actually 1 + 5 would achieve 1.
thanks i got it
can you tell me what is wong in my approach it seems correct to me https://codeforces.net/contest/1982/submission/267490137
This still seems to be an issue with handling the starting point, such as this group still lacking data for T: 5 6 8 4 1 4 1 9 The correct answer is 1, obtained by 1+4+1. However, in your program, when it first detects a sum greater than r, it encounters 4+1+4 during the process of moving the left pointer rightward, but since there is no value satisfying the condition within the [l, r] range, the left pointer moves to position 3, which is where the value 4 is located, instead of 1. This results in an incorrect answer of 0. In such problems, the left pointer typically moves to points that do not satisfy the current condition. Specifically, in this question, it should move to points that do not satisfy the condition of the interval sum > r, correct?
I understood what's the issue , and fixed the code , it's AC , but one thing i wanted to ask , that how do should i proove my greedy approach and check it is correct for every case , while doing greedy this is the mistake i do everytime i either do not take a case into consideration or i overthink cases and gets confused , btw thank you for your help
It is possible to write a brute-force program to generate some data and compare the results with a non-brute-force program. This might take some time, but it can be quite useful in certain situations.
okay the problem is that when the sum > r you are sliding the left side which is fine but you are not taking care — if after all the sliding the sum ends up lower than "l" and now your "sum =0" at the begining will discard the sum which could have been used
Thanks for the help. Got accepted 267452661
:)np
cool name.
thanks :)
Well done! Very fun contest and good problem set.
Thanks, it was a fun contest and nice problems + fast editorial
Can someone please tell me what is the flaw in the logic of my solution for C (like a corner test case on which it fails). It shows WA on 475th case.
Thanks for the help !
Example : 1 3 5 6 1 2 4 Using your code, the output will be 0, but the output must be 1 because your code will compare vec[i]=4. Asn will not increase, but you must use two pointers so that you subtract vec[le]=1, so the sum will become 6 and increase by ans.
Ohhh got it now. Thanks a lot bro.
Your example is not valid, you are taking 1 3 5 6 1 2 4, if we try this then n=1, l=3, r=5. The cards will be only 6. 6 is greater than 5, hence 0 should be the output.
test_cases=1,n=3,l=5,r=6
Why would you set $$$n=5\cdot 10^5$$$ to a $$$O(n\log n)$$$ data structure problem?
Trying to differentiate log factor lol
Great mathforces round! + fast editorial
Can anyone explain (?) me, In B,
Why k%(y-1) and not k%y ?
because y/y = 1
and to go from 1 to y you need y-1 operations
The number in the last part of the problem changes as follows:
2-3-...-(y-1)-1-2-3-...-(y-1)-1-2-3-...-(y-1)
The reason why $$$(y-1)$$$ is followed by $$$1$$$ is that the number is automatically divided by $$$y$$$ when it becomes $$$y$$$.
Imagine you have y = 3, for example. If you get x to be 1, you spend two (y-1) more operations to come from 1 to 3 (and then to 1 again)
Because once you reach 1 the value of x repeats every y-1 operations.
Under what category does problems like 1982B - Collatz Conjecture come under?
I always fail at making proper observations to such problems.
Can anyone please suggest me a list of such past problems?
Btw, I solved 1982C - Boring Day using sliding window technique. Code is quite simple and easily understandable.
I think it's just that if you dry run for some cases you can see a cycle forming and then optimise
I understand that. I just want few such problems to practice!!!
In problem D, the generalized version of Bézout's identity is used. If you haven't already heard about Bézout's identity, it states that the equation $$$\begin{equation} \ ax + by = d \ \end{equation}$$$ has integer solutions if and only if $$$\displaystyle gcd(a,b)\mid d$$$.
There are two ways to prove this: you can either use the extended Euclidean algorithm, or prove it via an existence proof that can be extended for $$$n$$$ variables instead of just $$$2$$$ (see the generalized version's statement here)
Here's the proof for three variables (heavily inspired by the proof for two variables from MONT) which can be easily extended for an arbitrary number of variables:
Let $$$S = { ax + by + cz \mid a, b, c \in \mathbb{Z} }$$$. Consider the smallest positive element $$$d \in S$$$, $$$d=ax_0+by_0+cz_0$$$. We want to show that $$$d=gcd(a,b,c)$$$. It is sufficient to show that $$$d\mid gcd(a,b,c)$$$ and $$$gcd(a,b,c) \mid d$$$. The second part is true since all of $$$\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$$$. For the first part, we need to show that $$$d \mid a,b,c$$$.
Let us do the following for each of $$$(a,b,c)$$$ (I will only do it for $$$a$$$): Assume that $$$d \nmid a$$$. Then $$$a=qd+r, 0<r<d$$$, and $$$r=a-qd$$$. $$$a$$$ is a linear combination of $$$(a,b,c)$$$ and so is $$$d$$$, which implies that $$$a-qd$$$ is too. Thus $$$r \in S$$$, and $$$r>0,r<d$$$. This contradicts our assumption that $$$d$$$ is the smallest positive element in the set. So $$$d \mid a$$$. Repeating a similar process for $$$b,c$$$ shows that $$$d \mid b, d \mid c$$$. Combining these, we get $$$d\mid gcd(a,b,c)$$$.
$$$\blacksquare$$$
Small correction: $$$gcd(a,b)|d$$$
Thank you, corrected!
Also I don't think "The second part is true since $$$a, b, c | d$$$" is correct. For example $$$2x + 3y + 5z = 1$$$ does have integer solutions but neither a,b nor c divide 1. But the gcd part is correct because we can factor out $$$gcd(a, b, c)$$$ from $$$ax+by+cz$$$.
Oops lol, I had meant to type $$$\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$$$, but instead ended up typing $$$(a,b,c)$$$ and using $$$\mid$$$. Corrected this as well, thank you; please let me know if you find any other mistakes.
I think you can just use the result of 2 variable to proof $$$n$$$ variable by induction, which would be more brain-dead to do so.
Hey another small correction: "Then $$$a=qd+r,0<r<a$$$". Here it should be $$$0 < r < d$$$. Similarly for "Thus $$$r \in S$$$, and $$$r>0,r<a$$$".
Corrected, thanks again.
A solution to a Diophantine equation is not unique, because we can form an infinite number of solutions if we know one solution. If a pair $$$(x, y)$$$ is a solution, then also all pairs $$$(x+ kb/gcd(a,b) ,y− ka/gcd(a,b) )$$$ are solutions, where $$$k$$$ is any integer.
what happens when $$$n$$$ variables instead of 2?
That will also have infinitely many solutions since $$$c_1 x_1 + c_2 x_2 + ... + c_n x_n = 0$$$ has at least $$$1$$$ solution since $$$gcd(c_1,c_2,...,c_n) \mid 0$$$, and all scalar multiples of this solution will also be valid solutions. Then you can add any scalar multiple of any solution for $$$0$$$ to any solution for $$$c_1 x_1 + c_2 x_2 + ... + c_n x_n = d$$$.
I mean for 4 variables suppose I have a solution (a,b,c,d) then how do you form other solutions?
(Note that this doesn't use a given solution to form infinitely many solutions, but instead directly forms infinitely many solutions)
I guess one option you have is to reduce it to a diophantine.
Like, for example, say I had $$$5a+15b+10c+25d=5$$$. Set $$$a=b=1$$$, then we have $$$10c+25d=-15$$$ and $$$c=-5n-4,d=2n+1$$$. We can choose any values we want for $$$a,b$$$ since $$$5a+15b$$$ will always be a multiple of the greatest common divisor of the coefficients.
ok thanks for help
Problem C : Detailed Video Explanation (Greedy + Two Pointer) https://youtu.be/zAMyp0dXCKk
D is using something called Diophantine equation which I am very much unaware of
From where should I learn these things and is it as scary as it sounds like
You will find it in math olympiad books.
So should I just learn this identity and move on or should I go deep into this like looking for proofs and similar equations?
I would say learn and move on (also do understand the proof imo, but it’s up to you)
If you want to learn via Youtube. You can learn it from Vivek Gupta(As you are comfortable in Hindi). He has covered it
thanks for the fast editorial :)
can anyone tell me the test case where my code fails in prblm 3??
267372328
1
4 5 5
3 1 2 3
Yaa.. Got it missed one if condition.
didn't aware the fact that gcd of set of integer S divides x iff x $$$\in$$$ span(S) 😭 cost me problem D
how people solve this without knowing this fact?
Proof by AC works i believe.
proved it to myself during the contest by trying out some small cases
I have been trying problem D for quite a while now, I am using a 2D sliding window approach to calculate the number of "ones" that each submatrix would have. I observed that the difference changes by (k*k — 2*numberOfOnes) for each submatrix and can be either a positive or a negative change.
However I do not understand where I am going wrong. Here is my submission https://codeforces.net/contest/1982/submission/267424514
Can someone please help point out the mistake or even a testcase where my solution would fail.
I did not understand the D solution with GCD. I came out with the solution of finding the difference of ones and zeros for each submatrix using prefix sums (not fast enough to code it in the contest time though).
What I thought is that if I have d1, d2, d3... dn, and I can find c1d1 + c2d2 + ... + cndn that is equal to D, than I can satisfy the conditions.
Anyone can give some link to the proof of the last equation?
Check out: https://en.wikipedia.org/wiki/B%C3%A9zout's_identity#Generalizations
Bezout's lemma, you can look it up here- Wiki
I have shown how to prove it in my comment above here.
Hey, I saw your explanation and it makes sense.
I had however used the following to check whether or not it will be possible to make the difference zero.
vector<int>v; for(auto &it: reduceBy) { v.push_back(it); } while(diff > 0 && !v.empty()) { if(v.back() != 0) diff -= (diff/v.back()) * v.back(); v.pop_back(); } if(diff == 0) cout << "YES" << endl; else cout << "NO" << endl;here the reduceBy is a set which contains the different impacts we can have on the difference. This however gives me a wrong answer and I don't understand why.
Thanks, guys! I haven't realized that the constants c1, ..., cn could be negative, so I was confusing this with the coin problem (determine if N is achievable with coins [c1, ..., cn]).
Can someone explain why my submission for problem D (267400465) gives runtime error? It works correctly on my local machine.
It does not work on cf but works on your machine due to undefined behaviour, in the end you have done *(s.begin()) assuming there are elements in s but that may not be true, in this case it's undefined behaviour as far as I am aware since whatever value is there may be picked up or a seg fault could occur. In your particular case it could have randomly turned up correct on your machine but on cf it could have given a seg fault or the random value could have been 0 giving a mod by 0 error.
I am sorry, i got my mistake
No the error is indeed correct. You have added an if statement in your loop with a break the lack of which made the error happen in the first place and is the reason your after contest submission is correct while during contest is not.
After the contest I have seen the GCD approach to solve problem D. However I don't understand what's wrong with the following approach:
I have used the following to check whether or not it will be possible to make the difference zero.
vector<int>v; for(auto &it: reduceBy) { v.push_back(it); } while(diff > 0 && !v.empty()) { if(v.back() != 0) diff = diff % v.back(); v.pop_back(); } if(diff == 0) cout << "YES" << endl; else cout << "NO" << endl;here the reduceBy is a set which contains the different impacts we can have on the difference. Hence v is a sorted vector in increasing order.
This however gives me a wrong answer and I don't understand why.
v = [3,2] diff = 5 5%2 = 1 1%3 = 1 but it is possible
I apologize I forgot to mention that reduceBy is sorted in increasing order and as we are traversing from the last index, it would pass as v = [2,3] diff = 5%3 = 2 2%2 = 0
I’ll update the original comment that reduceBy is a set and v would be sorted in ascending order.
well increase v to be [2,3,4] and diff=5. Now it does not pass.
What you are doing is greedily trying to reach 0, however in this problem the greedy approach is not valid since firstly you are not accounting for negative values of c: For example let v=[4,7] and diff=3 you would assume this is impossible but you can do 3+4-7 to reach 0
Secondly it isn't necessary that the biggest number will indeed be reduced from diff to reach 0, think coin dp problem.
That makes so much sense, and I feel dumb for not getting it myself. Thank you very much it’s clear to me why my submission was wrong.
In E there exists a solution with time complexity $$$O(T\log^2 n)$$$，using only DP. The main idea is trying to find every starting point of consecutive ones ($$$a_x=1$$$ if x is valid). You can see the implementation here.
Can you please explain the states of your dp and recurrence relation. I have been trying to think of a dp solution from 3 hours but i am not able to.
Can someone please let me know me where my submission to problem C might be failing ?
267403795
edit: I got it..
Hi everyone!
Can someone please point out why my submission 267373128 might be failing on the 475th test case of Test 2 of problem C. The following is the approach:
Any help will be appreciated!
I also got the same WA on 475th case. Try your code for input n=3,l=5,r=6 and value of array as 1,2,4. The output should be 1 but my code was giving 0.
In your 4th point, when a[i]<=r you can still win with that element if you move your left pointer to the right by some amount (possibly). That is to say, if I'm taking the sum from index 0 to index i and it's larger than r, I could take from index 1 to i and that could maybe work.
Edit: a[i]<=r instead of >
in the first problem, the score if x1 > y1 and x2 > y2 and y2 > x1 in that case there is a possiblity that at some point the yt would have been equal to xt ??
if x1 > y1 and x2 > y2 you could always increment x all the way and than y , remember we have to reach x2 and y2 eventually not that y2 is already there to hinder with x
hey , there are many telegram groups where solutions got leaked during contest please take some action. below is one groups where solutions and code was sharing during contest : https://t.me/codeforces_cp
yup, i to know a few grps A to D were discussed and shared during the contest :(
ur prefix sum condition is wrong . it should be :-
prefix[i][j]=prefix[i−1][j]+prefix[i][j−1]−prefix[i−1][j−1]+arr[i][j]
Ayo can someone help my code debug for Problem D. It says Wrong Answer on 4th Test Case. 242nd Token differ. 267451989
The problem is when both i>0 and j>0 you need to add v[i-1][j-1]
Thanks!! You a big help. Totally forgot about that
Yo, in qA, the third test case, why cant the 1st team score a goal and then the score would have been equal??
Yeah, Maybe But the problem is asking for "NO" iff you are sure the goals were equal at one point of time
can someone please give the 475th test case for problem C with n l and r?
It is n=3 , l=3 , r=3 array : [1 1 2]
thanks garlic_bread_0204
Can someone please check what is wrong with this submission for D ?
267454158
You are missing a parenthesis when defining each pref1[i][j], just compare with the line above
Just corrected it.. Also,how did you manage to come up with this gcd idea during the contest ? Is there any speicifc source from where you came to know about this Diophantine equation ?
I have a background in math olympiads so when I started to get a picture of what the solution looked like it just came to mind. As someone else mentioned you can look at this https://en.wikipedia.org/wiki/B%C3%A9zout's_identity#Generalizations
I am getting a TLE(Case 10) in Problem C. https://codeforces.net/contest/1982/submission/267454949
Your solution is O(n^2). Try to optimize it by using prefix sums
Could someone explain the editorial of E for me. It is still unclear for me, and what is the main point of the approach?
Note that "Bit sequence" can be generated by following infinite process:
i.e $$$[0] \to [0, 1] \to [0, 1, 1, 2] \to [0, 1, 1, 2, 1, 2, 2, 3]$$$ and so on.
It's not hard to see that it's actually a bit sequence: on the $$$i$$$-th step, we record all integers from $$$[2^i, 2^{i+1})$$$. These integers have one bit for $$$2^i$$$, and the rest of the bits correspond to the number of bits in $$$[0, 2^i)$$$, which is indeed the current sequence. Therefore, on the $$$i$$$-th step, we clone our sequence with an increment to the end of the sequence.
From this point of view, the periodic nature of this sequence is clearly visible. Imagine $$$x$$$ is a maximum integer, such that $$$2^x < n$$$. Then we can split the sequence $$$0...n-1$$$ into $$$0..2^x-1$$$ and $$$2^x...n-1$$$. As we can see, the second part is also a prefix of the sequence but with a +1 increment. Therefore, if $$$x > k$$$, we can just solve for the two parts independently and then sum up the answers (since no good segment crosses $$$2^x-1$$$). And if $$$x \leq k$$$, the answer is simply $$$\frac{n(n+1)}{2}$$$, except for the case when $$$x = k$$$ and $$$n = 2^{x+1}$$$, then it is $$$\frac{n(n-1)}{2}$$$. With these formulas, you can write a simple memoization solution. It's not hard to see that it works fast because there are $$$O(\log^2 n)$$$ special states, where $$$n$$$ is a power of two, and we are always recalculating from a special state and a state that lowers $$$n$$$ at least twice.
Code: 267468663
Nice Approach. But could you explain why you did k — 1 for the second array that is from [2^x to n — 1] ?
Like I get it that for the array [2^x to n — 1], there is an 2^xth extra bit and just this set bit is added to the sequence [0 to 2^x — 1] and it becomes the same sequence. But why k — 1 ? Should it not be k + 1 as we increased one bit to the original problem ?
Yes we increased one bit. Therefore condition turned to $$$bit(a_i)+1 \leq k \to bit(a_i) \leq k-1$$$.
Like, after reduction to prefix we will actually have one bit more than on prefix. And in our world we want to count $$$\leq k$$$ therefore after reduction to prefix we need to count $$$\leq k-1$$$, so that with this extra bit it will be $$$\leq k$$$.
This round helps a lot with my rating :)
The problem D is pretty interesting I think.
True , generally i am not able to get to D but this time it was from number theory which i am pretty comfortable with , hence got it done....
Well,I think the problem D is more likely to be some ideas added together. Actually, These ideas are pretty common if you do more maths problems :)
https://codeforces.net/blog/entry/130861 Help me guys
please explain how I can withdraw my earnings Nears?
In soccer question 3rd example the output should be NO but it's given yes .
for the test case 1 2 4 5 there will be a time when score will be 2 : 2 . so the output should be No , plz clarify my doubt.
Read the Note provided in the question
could not understand, plz explain
Just wondering, what's the point of having multiple test cases in F if $$$t$$$ is so small ($$$t \leq 10$$$) and there are only three tests (#1, #2, #3) where $$$t > 1$$$? Personally, I prefer problems with only one test case, as I don't have to care about re-initializing variables.
FelixArg , My solution for D shouldn't have passed the Final system test cases, but it did.
I knew the current difference between type1Sum, and type0Sum. ( let's call it
RequiredDifference)I knew for each of the sub-rectangle of size k*k, what are achievable differences. Lets call them (d1, d2, d3 ... dk).
I knew that I had to do a1 * d1 + a2 * d2 + a3 * d3 + ... ak * dk = RequiredDifference
I didn't know how that gcd ( d1 , d2 ... dk ) | requiredDiff .
But I knew, for ax + by = z , then gcd(x, y) | z. So I used this two variable equation property and passed test cases. Refer to my solution.
The test cases were weak for D. Ideally my solution shouldn't pass. Thanks to djm03178, it was later hacked.
Also, I honestly felt helpless during the contest because I didn't know this property
gcd ( d1 , d2 , d3 ... dk ) | requiredDiff.I wonder, does that solution have an actual counterexample? I'm stress testing a bunch of small cases but none are found yet. Anyways, to explain the TL hack, it looks something like this:
$$$n=m=8$$$, $$$k=4$$$
Expanding this pattern to $$$n=m=500$$$, $$$k=250$$$ makes 15281 distinct possible differences, so it's not feasible to perform gcd on every pair in 2 seconds. Since $$$k$$$ is even, the differences can only be even as well, so having an odd sum of $$$a_{ij}$$$ makes it impossible to find a possible way and therefore it can only realize that the answer is
NOafter running the whole loop.I got a counterexample, a=42 b=70,c=30, pairwise gcd are 14, 10,6 leaving out say 8 but gcd of all is 2 so all even numbers work.
I mean, finding three numbers for the counterexample is easy, but making an actual test for that is another story, because of how hard it is to obtain only the desired values and not undesired ones with the 'windows'.
I think I have a brief idea for this though. We can have large enough $$$k = n \lt m$$$, and control the difference with each column, so only each pair of columns of distance $$$k$$$ can affect the values and nothing else.
Ohhh, I think it works but the other hack seems to be already doing the same thing. I didn't realize because the hacked solution has a slightly different approach, but I guess it essentially has the same condition.
Here's the one I made:
Damn I'll come back to this 6 months later when I am hopefully a little better equipped to learn this stuff, haven't dipped into hacking yet and coming up with test cases rather than numbers immediately feels much harder. Either way cool that you were able to come up with this.
Anyone Can please figure out which test case my code isn't passing on 3rd.Here is the submission id. 267473714
See this Testcase
4 11 11
1 2 3 6
Your program considering
1+2+3+6 > rthen debunking all 1,2,3 and considering just 6 which gives 0 as answer.But what it should do is just take
1in the first round and lose and take2+3+6=11on the 2nd Round which gives 1 as a answeri tried to solve C problem by using prefix sum but i do not get what is wrong in my approach below i will attach my submission
https://codeforces.net/contest/1982/submission/267490137
include <bits/stdc++.h>
using namespace std; using namespace chrono;
define ll long long
define mod 1000000007
define nn "\n\n"
define pb emplace_back
define sz(x) int(x.size())
define all(x) x.begin(), x.end()
define watch(x) cout << #x << " = " << x << '\n'
define endl '\n'
int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
auto ssss = high_resolution_clock::now(); int T; cin >> T; for (int tc = 1; tc <= T; ++tc) { cout << "Test Case #" << tc << ":" << endl; int n , l , r; cin >> n >> l >> r; ll ans = 0 , sum = 0; vector<int> a(n); for(auto& x : a) cin >> x; int index = -1; for(int i = 0; i < n; ++i) { sum += a[i]; if(sum >= l && sum <= r) { sum = 0 , ans++; continue; } else { index = (index == -1) ? i : index; i++; while(i < n && sum < l) { sum += a[i]; i++; } while(index < i && sum > r) { sum -= a[index]; index++; } if(sum >= l && sum <= r) { sum = 0; ans++; index = -1; } i--; } } cout << ans << endl; cout << nn; }auto eeee = high_resolution_clock::now(); duration duration_sec = duration_cast<duration>(eeee — ssss); cout << "Total time taken: " << duration_sec.count() << " seconds" << endl; return 0; }
Can anyone tell me why this code is not getting selected o 3rd ??
In problem C my code 267502094 is showing TLE on 17th test case. My logic is simply to iterate till the segment sum is >= l. If its becomes greater than r then i'll just take nly the first card of that segment and chose to lose the round... starting the next round from the next card thus. Help me in finding my mistake.
just think of a case where l=1e6 and r=1e6 and the array be like 1.......(1e5) times and one more element at the end is 1e9 in this case your code will check and remove the first element step by step and by checking again whole segment to the last value will become o(n*n).
Okkk... got it. Thank you so much.
Hey, For problem C I was trying to write a dp solution in the contest but I was getting WA on test 2, eventually had to go without dp. Can anyone please help me in finding the error? I have wasted a lot of time finding a bug :(
Please help, my submission: 267511316
Replace lower_bound() with upper_bound()
That fails in the first test case itself :( I have possible tried everything.
https://codeforces.net/contest/1982/submission/267525140
An alternative way to calcute the DP in E goes like this. P. S. the length of the text might seem daunting but it is because I tried to explain the logic behind every step.
Again, $$$dp(i, j)$$$ represents the number of subarrays for the first $$$2^i$$$ numbers if we can have at most $$$j$$$ bits. It is easy to notice that this formulation is equivalent to the number of subarrays formed by the numbers for which only the first $$$i$$$ bits can be non-zero. This might be useful for some for later intution. To make things a bit easier to write down, let's denote $$$g(x)$$$ as the number of subarrays contained in an array of length $$$x$$$, so $$$g(x) = \frac{x(x + 1)}{2}$$$.
If $$$j \geq i$$$, then the answer is simply $$$g(2^i)$$$, because no number smaller than $$$2^i$$$ has more than $$$i$$$ bits.
if $$$j=0$$$ then the answer is 1 because there is only one possible subarray (the one containing just a zero).
Now for the general case, $$$ 1 \leq j < i$$$, we need to notice something. The smallest number with more then $$$j$$$ bits will be one that looks like $$$1...1$$$ in binary, where there are a total of $$$j + 1$$$ bits (equal to $$$2^{j+1} - 1$$$). In this case all the subarrays formed by these numbers will be included in the dp. The number of these subarrays is $$$g(2^{j + 1} - 1)$$$. It is also important to note that these numbers form a sequence of continous good numbers which don't neighbour the other good numbers because of $$$2^{j+1} - 1$$$.
The number after $$$2^{j+1} - 1$$$ is $$$10..0$$$ or $$$2^{j + 1}$$$ where there are $$$j + 1$$$ zeros. We can notice that the number of subarrays formed by numbers where this lone bit is the highest one is just $$$dp(j + 1, j - 1)$$$, $$$j + 1$$$ because that is the number of zeros we have to work with and $$$j - 1$$$ because we need to account for the extra bit. In a similar fashion we include the numbers for which the $$$(j + 2)rd$$$ (0-indexed) bit is the highest one, the answer for which will be $$$dp(j + 2, j - 1)$$$. If we continue this pattern for every bit, we will have $$$dp(i, j) = g(2^{k + 1} - 1) + dp(j + 1, j - 1) + dp(j + 2, j - 1) + ... dp(i - 1, j - 1)$$$. The reason why we can sum up these states is because the sequence of numbers considered by each state are seperated by at least one bad number. E.g. $$$2^{j+1} - 1$$$ seperates the first sequence of numbers from the others. Similarly we can be sure that the numbers considered in the second term are seperated by the number $$$2^{j+2} - 1$$$ (the binary representation of this number is just $$$j + 1$$$ ones so this number is bad). For the third term the guaranteed bad number is $$$2^{j+3} - 1$$$, for the fourth its $$$2^{j+4} - 1$$$ and so on. This was also my intution for this dp. To somehow formulate the formula for dp such that all the terms are seperated by bad numbers. This dp yields a complexity of $$$O(log(n)^3)$$$ and it can be optimized to $$$O(log(n)^2)$$$ with prefix sums but it is not necessary to pass the TL.
You can use this DP to solve the rest of the problem in the same way as the authors did but my approach is a bit simpler in my opinion (though I think they are fundementally the same).
Step one: check if the smallest number with more than $$$k$$$ bits ($$$2^{k+1} - 1$$$) is greater than $$$n$$$, if that is true, then add add $$$g(n)$$$ to the answer and terminate.
Otherwise we go to the highest bit of $$$n$$$. Let's say that is the $$$b$$$-th bit. We add the subbarays not containing the bit to the answer, the number of which is $$$dp(b, k)$$$. Then, we reduce $$$k$$$ by 1 and $$$n$$$ by $$$2^b$$$ since every other solution will include the $$$b$$$-th bit. Now we go back to step one and repeat until $$$n$$$ is zero or code is terminated in step one. We can be sure that the numbers included in the subbarays for each step are not neighbouring because of similar reasoning to the DP. The biggest number considered in the range (which is just a sequence of $$$1$$$-s in binary), seperates them. If there aren't more than $$$k$$$ bits the code terminates at step one, so we can be sure that everything is nice and seperated.
Here is my code. code
In problem D, it is mentioned that, checking D mod gcd(d1,d2,…,dq)=0 is sufficient to test the existence of the solution for the equation c1⋅d1+c2⋅d2+⋯+cq⋅dq=D. Is it any proved theorem or intuition? Can any one explain this?
problem c) https://codeforces.net/contest/1982/submission/267544904 why is it failing on other tests
Please someone explain what the below lines do in code of solution E?
Am i the only one who found F very easy for its position?
I have been accounted for cheating in question B. I am really not aware that using third party websites as code editor is a violation. I just came to know that once I have received mail regarding plagiarism. I assure that this will not repeated and I kindly request not to skip me in the upcoming contests. I hope my request will be considered.
include<bits/stdc++.h>
define ll long long
using namespace std;
int main(){ int t; cin>>t; while(t--){ ll n,l,r; cin>>n>>l>>r; vectorv(n); for(ll i=0;i<n;i++){ cin>>v[i]; } reverse(v.begin(),v.end()); stackst; for(ll vl:v)st.push(vl);
ll sum=0,cnt=0;
while(!st.empty()){
sum+=st.top(); if(sum>r){ sum=st.top(); } if(sum>=l&&sum<=r){ sum=0; cnt++; }st.pop();
} cout<<cnt<<endl;
}
} help me to get the corner case
Can someone share the greedy solution of problem C
Or you can show the mistake of my solution
Link to submission
please help me to understand why equation in problem D looks like that
c[1] * d[1] + c[2] * d[2] + c[i] * d[i] = D
shouldn`t it be:
c[1] * d[1] + c[2] * d[2] + c[i] * d[i] = -D
because D is equal heights of mountains without snowy caps — heights of mountains with snowy caps and we want D to be 0, therefore, when we go through an n X m matrix considering every k X k submatrix we count how many there are mountains without snowy caps and we add that quantity multiplied by some c[i], after that we substract quantitiy of mountains with snowy caps multiplied by c[i]
that means we want
D + NOT_SNOWY * c[i] — SNOWY * c[i] = D + (NOT_SNOWY — SNOWY) * c[i] = D + d[i] * c[i] to be equal to 0
hence
D + d[1] * c[1] + d[2] * c[2] + d[2] * c[2] = 0 => d[1] * c[1] + d[2] * c[2] + d[i] * c[i] = -D
where am I making a mistake?
Is there any other way to solve this problem besides the method provided in the editorial? If you are not from a math background, guessing that method is pretty difficult. Are there any other possible solutions, like using dynamic programming?
I realized that if we calculate the net difference of the types of mountains in each k*k matrix, then the question can be the same as finding the sum of h (total difference between the height of two types of mountains) using n(net difference between types of mountain in each k*k matrix) values, which can be added or subtracted to make the sum of h.
Any help with this?? https://codeforces.net/blog/entry/130850