Спасибо за участие! Надеюсь задачи вам понравились.
Один из тестировщиков (redpanda) сделал прекрасный видео разбор задач A-C, очень рекомендую посмотреть.
Разбор
Tutorial is loading...
Решение (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 is loading...
Решение (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;
}
Подсказка 1
Все числа $$$a_{i}$$$ положительные, может ли это как то помочь?
Подсказка 2
Попробуйте воспользоваться динамическим программированием.
Разбор
Tutorial is loading...
Решение 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;
}
Решение 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)
Подсказкa 1
Как изменяется разница между высотами, если мы выберем конкретную подматрицу?
Подсказкa 2
Стоит свести задачу к математической конструкции. Может что-то из теории чисел может помочь?
Разбор
Tutorial is loading...
Решение (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 - Количество k-хороших подотрезков
Подсказкa
Попробуйте использовать подход "разделяй и властвуй".
Разбор
Tutorial is loading...
Решение (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;
}
1982F - И снова задача о сортировке
Подсказкa
Если поддерживать множество таких индексов $$$i$$$, что $$$a_{i} \lt a_{i - 1}$$$, то может ли это как то помочь?
Разбор
Tutorial is loading...
Решение (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:)
...
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://mirror.codeforces.com/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.
can you help me understand why my approach isn't working? I used a queue and accordingly performed operations. for the three cases- sum>r, sum<=r&&sum>=l , sum<l let me know if theres a tc where it fails. https://mirror.codeforces.com/contest/1982/submission/271534137
The issue lies in the initial node judgment. For example, when n=3, l=4, r=5, and the array is 2 1 3, should your output be 0? The answer is 1, because the last element 3 is not within the range [l, r], so you did not update temp_sum.
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
Well done! Very fun contest and good problem set.
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$$$.
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 \lt r \lt 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 \gt 0,r \lt 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 \lt r \lt a$$$". Here it should be $$$0 \lt r \lt d$$$. Similarly for "Thus $$$r \in S$$$, and $$$r \gt 0,r \lt a$$$".
Corrected, thanks again.
Wow :)
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
Question C : Detailed Video Editorial https://youtu.be/zAMyp0dXCKk
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)
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://mirror.codeforces.com/contest/1982/submission/267424514
Can someone please help point out the mistake or even a testcase where my solution would fail.
If I read your code correctly, it seems like you are translating the problem into the coin change problem. i.e. you have coins of denomination $$$a_1, a_2,\ldots$$$, check if there is a way to produce change of value $$$x$$$.
Firstly the translation is not right. For example if you have $$$x=1$$$ and coin values $$$\{2, 3\}$$$ the coin change problem says no, but the answer should be
YESas you can go from $$$1\Rightarrow -2 \Rightarrow 0$$$.But even if the translation is correct it's well known such greedy method as you use will not work for all kinds of coin systems, it only works for a subset of coin system called "canonical" (I do not know much about it but it seems interesting). Here's an example that is not canonical (fails greedy): $$$a=\{3, 5\}, x=8$$$. So greedily adding $$$3$$$ gets you to $$$6$$$ which fails, but adding $$$3$$$ once then adding to $$$5$$$ gives $$$8$$$.
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.
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.
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 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!
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
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]
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
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 \lt 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 \gt 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$$$.
Ohh, now got it. Thanks a lot.
Also the TC will be o(log^3n) right ?
It's $$$O(M \cdot (\log^2n + T\log n))$$$, where $$$M$$$ denotes $$$map$$$ runtime. But note that it can be easily rewritten without map to be clear $$$O(\log^2n + T\log n)$$$. Here $$$O(\log^2 n)$$$ to calculate answers for all cases where $$$n$$$ is a power of two, and after this single testcase will take $$$O(\log n)$$$. The upside of using a $$$map$$$ is that you don't need to think about those special states, you can just write all transitions as it is, and $$$map$$$ will optimize it for you, for the cost of $$$map$$$ runtime. In this problem constraints and TL are pretty generous luckily, therefore $$$map$$$ is safe to use.
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 :)
please explain how I can withdraw my earnings Nears?
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 \gt 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
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://mirror.codeforces.com/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 \lt 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^{j + 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
Thank you very much for the detailed explanation. dp(i, j) = g(2^(k + 1) — 1) + ... should be dp(i, j) = g(2^(j + 1) — 1) + ...
Yes, thank you. I will correct it.
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?
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?
Can someone share the greedy solution of problem C
Or you can show the mistake of my solution
Link to submission
267918536
Here you go Hope it helps.
Any help with this?? https://mirror.codeforces.com/blog/entry/130850
For E problem - In the given test case 576460752303423268 59 (The last one)
int mod = 1e9+7; The answer is just (C(n, 2)%mod + n%mod)%mod But I think my code is doing something wrong while calculating C(n, 2)%mod
And the final answer that I'm getting is 777901708. If anyone has solved it, can they tell me if there is some catch or a different method to calculate this?
PS: I took help from stack overflow for getting the (nCr % p) value for big values of n.
Thank You
Good round
Can someone tell me how to do problem E using technique meet in the middle?
can somebody explain in 1st problem why there can't be a moment in 3rd testcase where the scores can't be equal at all mean reaching from (1,2) to (4,5) 1 can first go to 2 so there will be a moment right??
There can be a moment, you are right. The question is whether it's certain that there was such a moment. If there 100% was a moment, where the scores were equal, print NO, otherwise(like in 3rd case) if it isn't certain, print YES.
okay okay so how does you make it certain ??
I actually don't understand it still I can't understand why the editorial solutions works still
For it to be certain, one of the teams had to have made a comeback. For example, if the score is 1:2, and when he returns it's 3:2. There is only one possible scenario and that is for the first team to score a goal and make it 2:2, and then score another goal and make it 3:2. In that scenario(which is the only possible one), there was a time where the scores were equal. If you write down a few more examples where a team made a comeback, you will see that in any scenario you come up with, at some point, their scores had to be equal. And in the opposite example where the team that was in the lead, stayed in the lead you can always find a scenario where they weren't equal at any point.
In problem D why don't we manually check for some values and directly see if gcd divides ?
according to chicken nugget if ax+by=c, then c needs to be calculated manually upto lcm(a,b)-a-b.
after this value onwards its a multiple of gcd(a,b).