Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Negationist's blog

Off by one?

By Negationist, history, 5 weeks 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
5 weeks ago
0

Can anyone put a name on this type of question?

By Negationist, history, 6 weeks 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
6 weeks ago
7

What is wrong with this algorithm?

By Negationist, history, 7 weeks 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
7 weeks ago
7

I don't like most editorials

By Negationist, history, 7 weeks 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
7 weeks ago
4

Problem with rolling hash? (solved)

By Negationist, history, 7 weeks 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
7 weeks ago
11

Failing to build a greedy countercase(solved)

By Negationist, history, 2 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
2 months ago
7

Why is the STL failing?

By Negationist, history, 2 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
2 months ago
7

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

By Negationist, history, 2 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
2 months ago
5

Speedbreaker

By Negationist, history, 2 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
2 months ago
6

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

By Negationist, history, 2 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
2 months ago
2

How to improve implementation skills?

By Negationist, history, 2 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
2 months ago
19