Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

Negationist's blog

Is there an n^2 solution to this?

By Negationist, history, 10 days ago, In English

In this problem, https://mirror.codeforces.com/contest/1433/problem/F, instead of doing the holistic n^4 dp, i instead did a n^3 dp for every row, effectively(n^4 anyway), however I am wondering if this subproblem can be solved in faster than n^3? The subproblem is this, given an array of n integers, what is the maximum sum i can make of each modulo k without taking more than x items, my dp was 3d where dp[i][j][cnt] was the best answer with the first i numbers, that was congruent to to j mod k and used cnt items — so the complexity was O(n*k*x), but i cant help but wonder if there is a faster way to do it? Would that just reduce to np complete? I'm very curious.

Full text and comments »

Negationist
10 days ago
0

Dealing with inconsistency

By Negationist, history, 3 weeks ago, In English

I'm sure at some point, perhaps when I hit candidate master, my ability to actually think of solutions will matter more than other things. For now however, I am seeking advice on how to be a consistent problem solver. There are two main problem I have once I get the idea. 1: implementation(efficiently), there is no shortcut I will work on it. 2: effort, if I don't like a problem, my active mind will not only barely help, but actively fight against me, on most(maybe 85%) problem's I have to look at the editorial for, usually what happens is, I look at the editorial and see something that I thought of(not just like a little piece, the whole thing), but just didn't pursue or just disregarded. Like, when I don't like the problem I do some really bad things. Today for example, I didn't do k-- before converting to binary(when I was testing the samples in my head), and so even though I had the right construction I just gave up, because I thought I had found a maximal construction(which I had) but it wasn't working. If I had even taken a second to go an code it or even think about it, I would have realized immediately what my mistake was. I feel like I never makes these kinds of mistakes when I'm at a good mental spot/like the problem(and it mostly has nothing to do with the topic, except for certain constructives which I know I don't like, in case you think its just about me solving topic that I already know). Does anyone have any advice? If I could fix this alone, even with my bad implementation, I feel like I could push 100-200 points past my peak.

Full text and comments »

Negationist
3 weeks ago
2

dangerous behavior

By Negationist, history, 3 weeks ago, In English

The problem is Adventurers(https://mirror.codeforces.com/contest/2046/problem/C). This code is cooked. Even just printing the contents of the container changes the output completely. For anyone who's up for it, what sort of magic is even going on? How do I fix it?

My Code

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define print(x) cout << (x) << endln
#define each(a, x) for(auto &&a : x)

using namespace std;

void solve(){
    int n;
    cin >> n;
    vii points(n);
    for(int i=0;i<n;i++){
        cin >> points[i].ff >> points[i].ss;
    }
    sort(points.begin(),points.end());
    vi x(n),y(n);
    for(int i=0;i<n;i++){
        x[i] = points[i].ff;
        y[i] = points[i].ss;
    }
    int ans = 0;
    pii d = {0,0};
    multiset<int> left,right;
    int l = 1, r= n/4;
    while(l<=r){
        int mid = l+(r-l)/2;
        bool found = false;
        right.clear();
        left.clear();
        for(int i=0;i<n;i++){
            right.insert(y[i]);
        }
        for(int i=0;i<n;i++){
            left.insert(y[i]);
            right.erase(right.find(y[i]));
            while(i+1<n && x[i+1]==x[i]){
                left.insert(y[i+1]);
                right.erase(right.find(y[i+1]));
                i++;
            }
            if(left.size()<2*mid || right.size()<2*mid) continue;
            int u1,d1,u2,d2;
            int lo = *(left.begin()), hi = *(--left.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = left.lower_bound(_mid);
                int num = distance(left.begin(),prev)+1;
                if(num>=mid && left.size()-num>=mid){
                    prev++;
                    d1 = *prev;
                    hi = _mid-1;
                } else{
                    lo = _mid+1;
                }
            }
            lo = *(left.begin()); hi = *(--left.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = left.upper_bound(_mid);
                int num = distance(prev,left.end());
                if(num>=mid && left.size()-num>=mid){
                    lo = _mid+1;
                    u1 = *prev;
                } else{
                    hi = _mid-1;
                }
            }
            lo = *(right.begin()), hi = *(--right.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = right.lower_bound(_mid);
                int num = distance(right.begin(),prev)+1;
                if(num>=mid && right.size()-num>=mid){
                    prev++;
                    d2 = *prev;
                    hi = _mid-1;
                } else{
                    lo = _mid+1;
                }
            }
            lo = *(right.begin()); hi = *(--right.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = right.lower_bound(_mid);
                int num = distance(prev,right.end());
                if(num>=mid){
                    if(right.size()-num>=mid){
                        u2 = *prev;
                    }
                    lo = _mid+1;
                } else{
                    hi = _mid-1;
                }
            }
            int top = min(u1,u2), bottom = max(d1,d2);
            if(top>=bottom){
                found = true;
                if(mid>ans){
                    ans = mid;
                    d = {x[i]+1,top};
                }
                break;
            }
        }
        if(found){
            l = mid+1;
        } else{
            r = mid-1;
        }
    }
    cout << ans << "\n" << d.ff << " " << d.ss << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Full text and comments »

Negationist
3 weeks ago
0

Off by one?

By Negationist, history, 2 months ago, In English

In the problem: https://mirror.codeforces.com/contest/2022/problem/C. My implementation involves pushing the strings one character forward to fix the off by one. In the official solution, they push the votes in a different way, here is a link: https://mirror.codeforces.com/blog/entry/135095. Look for "vot[k][i+1]=1;." why does my way not work? Here is the code:

My Code

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int vote(char x, char y, char z){
    int res = 0;
    res+=(x=='A'?1:0);
    res+=(y=='A'?1:0);
    res+=(z=='A'?1:0);
    return (res>1);
}

void solve(){
    int n;
    cin >> n;
    string s[2];
    for(int i=0;i<2;i++){
        cin >> s[i];
        s[i] = "+"+s[i];
    }
    vector<vector<int>> dp(n+10,vector<int>(3,-1));
    dp[0][0] = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(dp[i][j]==-1) continue;
            if(j==0){
                dp[i+3][0] = max(dp[i+3][0], dp[i][0] + vote(s[0][i+1],s[0][i+2],s[0][i+3]) + vote(s[1][i+1],s[1][i+2],s[1][i+3]));
                dp[i+1][1] = max(dp[i+1][1], dp[i][0] + vote(s[0][i+1],s[1][i+1],s[0][i+2]));
                dp[i+1][2] = max(dp[i+1][2], dp[i][0] + vote(s[0][i+1],s[1][i+1],s[1][i+2]));
            } else if(j==1){
                dp[i+3][1] = max(dp[i+3][1], dp[i][1]+vote(s[0][i+2],s[0][i+3],s[0][i+4])+vote(s[1][i+1],s[1][i+2],s[1][i+3]));
                dp[i+2][0] = max(dp[i+1][0], dp[i][1]+vote(s[1][i+1], s[1][i+2], s[0][i+2]));
            } else{
                dp[i+3][2] = max(dp[i+3][2], dp[i][2]+vote(s[0][i+1],s[0][i+2],s[0][i+3])+vote(s[1][i+2],s[1][i+3],s[1][i+4]));
                dp[i+2][0] = max(dp[i+2][0], dp[i][2]+vote(s[0][i+1], s[0][i+2], s[1][i+2]));
            }
        }
    }
    cout << dp[n][0] << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Full text and comments »

-1

Negationist
2 months ago
0

Can anyone put a name on this type of question?

By Negationist, history, 2 months ago, In English

I feel like there are certain questions which have a specific type of implementation(maybe I am just thinking of implementation tho i feel like this may be different) where, even though you may know exactly what pattern you want to create, finding an implementation that is simple and doesn't was time with potential bugs and corner cases and such is hard. For example, I was just doing the problem: https://mirror.codeforces.com/contest/1898/problem/C.

In this problem, even though I found the conditions for a solution and the cycles in my graph that I needed, I struggled to put it together into code and went and looked at jiangly's code for it: https://mirror.codeforces.com/contest/1898/submission/233522554.

It was elegant as expected, but it made me realize am I missing this critical skill of sleek implementation that he has for annoying problems. Does any one know what I'm talking about or how to improve at this. Thanks!

Full text and comments »

Negationist
2 months ago
7

What is wrong with this algorithm?

By Negationist, history, 3 months ago, In English

Problem: Array Game — https://mirror.codeforces.com/contest/1904/problem/C Idea of the code, consider all possible combinations of 2 elements to make diff, mn = min of, mn, diff, [first element greater than diff]-diff, [one element left of the first element greater than diff]-diff. Thanks so much.

My Code

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

void solve(){
    int n,k;
    cin >> n >> k;
    vi a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    if(k >= 3){
        cout << "0\n";
        return;
    }
    sort(a.begin(), a.end());
    if(k==2){
        int mn = a[0];
        for(int i=0;i<n-2;i++){
            for(int j=1; j+i <n; j++){
                int diff = a[i+j]-a[i];
                int l=0, r=n-1;
                while(l<=r){
                    int mid = l +(r-l)/2;
                    if(a[mid]<=diff){
                        l = mid+1;
                    } else{
                        r = mid-1;
                    }
                }
                if(r>=0) {
                    mn = min(mn, diff-a[r]);
                }
                if(r+1<n) {
                    mn = min(mn, a[r+1] - diff);
                }
                mn = min(mn, diff);
            }
        }
        cout << mn << "\n";

    }
    if(k==1){
        int mn = a[0];
        for(int i=0;i<n-1;i++){
            mn = min(mn, a[i+1]-a[i]);
        }
        cout << mn << "\n";
        return;
    }

}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Full text and comments »

Negationist
3 months ago
7

I don't like most editorials

By Negationist, history, 3 months ago, In English

Is it just me or do editorials kind of suck? Often, the methods they present are overly complicated and/or not made with idea of improving the reader's intuition in mind. It's gotten to the point that I only look for broad ideas and never look for specific implementation. And I always leave them kind of annoyed.

Example Problem: https://mirror.codeforces.com/contest/2008/problem/G (sakurako's task) What I don't like: "Now, we can find where the mexk should be in linear time. Firstly, if it is before the first one, then the answer is k, otherwise, we can assign k=k−a1. Then let's look at the second element. If a1+k<a2, then answer should be a1+k and otherwise we can assign k=k−a2+a1−1. In other words, when we look if our k can be in range from ai to ai+1, we know that number of elements that were not in the array and less than ai equal to k+ai. Then, when we find such i, we can output the answer."

This is dumb and overcomplicated. What they should have said was something like this. "Assume the array is empty, then, mex = k-1. For every array element(0 to n-1) check if mex >= i*GCD. If so, it means the mex is influenced by this array element. Thus we should do mex++. Otherwise do nothing." I went to bed trying to understand the editorial and sleeping frustrated. It seems to me like the tutorial writer care more about showing off then actually developing useful intuition.

I understand making contests and tutorials is hard but still. Some editiorials just seem so disconnected. idk. Anyone else feel this way?

Full text and comments »

Negationist
3 months ago
4

Problem with rolling hash? (solved)

By Negationist, history, 3 months ago, In English

Why does my rolling hash never work?

hash implementation

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

int A;
int B = ((1LL<<61) - 1);

using namespace std;

void computehash(string &s, vi &h){
    int n = s.size();
    h[0] = s[0];
    for(int i=1;i<n;i++){
        h[i] = (h[i-1]*A + s[i])%B;
    }
}

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    vi h(n);
    computehash(s, h);
    vi pow(n);
    pow[0] = 1;
    for(int i=1;i<n;i++){
        pow[i] = (pow[i-1]*A)%B;
    }
    for(int l=n-1;l>1;l--){
        int a = l-1;
        int b = n-l;
        if(a<b) break;
        cout << "\n";
        int hash1 = h[a];
        int hash2 = (h[n-1] - h[b-1]*pow[n-b])%B;
        if(hash1 ==  hash2){
            cout << "YES\n";
            cout << s.substr(1,l);
            return;
        }
    }
    cout << "NO\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dist(1,B-1);
    A = dist(rng);
    solve();
    return 0;
}

Full text and comments »

Negationist
3 months ago
11

Failing to build a greedy countercase(solved)

By Negationist, history, 3 months ago, In English

I hate being the guy that spams questioning blogs but... On the problem, Did We Get Everything Covered?, I did the solution but in reverse kind of. Just look at my code and you'll see what I mean, but something is wrong. What?

Code

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

void solve(){
    int n,k,m;
    string s;
    cin >> n >> k >> m >> s;
    string out;
    int cnt[k] = {};
    int total = 0;
    for(int i=0;i<m;i++){
        bool good = true;
        if(s[i] < 'a'+k){
            cnt[s[i]-'a']++;
        }
        for(int j=0;j<k;j++){
            if(cnt[j]<1){
                good = false;
                break;
            }
        }
        if(!good) continue;
        out.pb(s[i]);
        for(int j=0;j<k;j++){
            cnt[j] = 0;
        }
        total++;
    }
    if(total>=n){
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
    cout << out;
    for(int i=0;i<k;i++){
        if(cnt[i]==0){
            for(int j=0;j<n-out.size();j++){
                cout << (char)('a'+i);
                cout << "\n";
                return;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Edit: I failed test case 140 in test 2.

Full text and comments »

Negationist
3 months ago
7

Why is the STL failing?

By Negationist, history, 3 months ago, In English

Here is an AC submission:

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Here is an WA submission:

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

The only difference is a custom sqrt function. This was my worse contest ever because of this. Wasted like 40 mins trying figure this out and needed like 1 more min to solve C. Someone please explain because this is so weird and frustrating.

Full text and comments »

Negationist
3 months ago
7

Why is this solution sufficient for the problem "Speedbreaker"?

By Negationist, history, 3 months ago, In English

In the speedbreaker question, why do we need to do: c++ mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);

Full Code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],mn[200005],mx[200005],l,r;
void solve(){
	cin>>n;
	for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0;
	for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i);
	for(int i=1;i<=n;i++){
		mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);
		if(mx[i]-mn[i]>=i){cout<<"0\n";return;}
	}
	l=1,r=n;
	for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1);
	cout<<r-l+1<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}

Also, I get why the first condition is necessary for there to be a solutions and I get why the second part of the code finds that good interval, but I'm having a little trouble piecing together the sufficiency of the two to guarantee the right answer. Perhaps this is also why I font understand why you have to do the operations on the mins and maxes too.

Full text and comments »

Negationist
3 months ago
5

Speedbreaker

By Negationist, history, 3 months ago, In English

In the speedbreaker question, why do we need to do: c++ mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);

I (mostly) get everything besides that. Thanks in advance!

Full submission by Zqr123456 on Div 2 contest:

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],mn[200005],mx[200005],l,r;
void solve(){
	cin>>n;
	for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0;
	for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i);
	for(int i=1;i<=n;i++){
		mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);
		if(mx[i]-mn[i]>=i){cout<<"0\n";return;}
	}
	l=1,r=n;
	for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1);
	cout<<r-l+1<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}

Full text and comments »

Negationist
3 months ago
6

Interesting thing on Codeforces Round 932 (Div. 2)B

By Negationist, history, 3 months ago, In English

In the editorial, they use prefix sums to find the MEXs, but we can actually calculate the final MEX of the subsegments directly. This is based on the fact that if an element is in the array, there MUST be a subsegment that does NOT have it as the MEX. Thus, the final MEX(for all subsegments) must be just the MEX of the original array. With this knowledge we can simply find the first subsegment with that MEX as the MEX. From there, we look for one more subsegment with this as the MEX, if found, we are done. If not, we know it must be impossible. Please note this is my first real blog, let me know if I did something wrong.

Code: https://mirror.codeforces.com/contest/1935/submission/282863993

Full text and comments »

Negationist
3 months ago
2

How to improve implementation skills?

By Negationist, history, 3 months ago, In English

On many problems, I think of the solution very quickly but often spend a long time fixing and debugging the code to do what I want. For https://mirror.codeforces.com/problemset/problem/1973/B, I thought of a sliding window technique to find all windows that satisfy the or condition which is O(n). Yet, it took me like an hour and multiple failed submissions to get an AC. Right now, it feels like I have the "brains"(ingenuity) but not the "brawn"(implementation skills) right now. Furthermore, when I'm spending more time debugging than constructing it feels like I'm somewhat wasting my time(also its not very fun lol). What should I do?

P.S: I know someone is going to comment on how long I have been doing cp. Yes, I have only being doing cp for 1.5 months, and yes I know my implementation will naturally get better over time. Still, I'm looking for any advice BESIDES that. Thank you.

Full text and comments »

implementation

Negationist
3 months ago
19