Educational Codeforces Round 189 — Editorial

Tutorial

Solution 1 (BledDest)

t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    good = False
    for z in range(x * 2, y, x):
        if y % z != 0:
            good = True
            break
    if good:
        print('YES')
    else:
        print('NO')

Solution 2 (BledDest)

t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    print('YES' if y > 2 * x else 'NO')

2225B - Alternating String

Author: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < (int)s.size() - 1; i++){
		ans += (s[i] == s[i + 1]);
	}
	cout << (ans <= 2 ? "YES\n" : "NO\n");
}
 
signed 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;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2225C - Red-Black Pairs

Author: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;

#define int long long

const int INF = 1'000'000'007;

void solve(){
  int n;
  cin >> n;
  vector<string> d(2);
  cin >> d[0] >> d[1];

  vector<int> dp(n + 1, INF);
  dp[0] = 0;
  for (int i = 0; i < n; i++){
    dp[i + 1] = min(dp[i + 1], dp[i] + (d[0][i] != d[1][i]));
    if (i + 1 < n){
      dp[i + 2] = min(dp[i + 2], dp[i] + (d[0][i] != d[0][i + 1]) + (d[1][i] != d[1][i + 1]));
    }
  }

  cout << dp[n] << '\n';
}
 
signed 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 t = 1;
	cin >> t;
	while(t--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2225D - Exceptional Segments

Author: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 998'244'353;

int get0(int x){
    return 1ll + (x >= 3 ? (x - 3) / 4 + 1 : 0);
}

int get1(int x){
    return (x >= 1 ? (x - 1) / 4 + 1 : 0);
}

void solve(){
	int n, x;
	cin >> n >> x;

    int l0 = get0(x - 1) % MOD;
    int r0 = (get0(n) - l0) % MOD;
	int ans = l0 * r0;

    int l1 = get1(x - 1) % MOD;
    int r1 = (get1(n) - l1) % MOD;
	ans += l1 * r1;
    ans %= MOD;

    cout << ans << '\n';
}

signed 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;
	while(tests--){
		solve();
	}

#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2225E - Covering Points with Circles

Author: basalov_yurij

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;

#define int long long

mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
 
void solve() {
	int n, r;
	cin >> n >> r;
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++){
		cin >> p[i].first >> p[i].second;
	}

	int w = 2 * r, h = ceil(sqrt(3) * r);

	auto is_in_circle = [&](int x, int y, int ox, int oy, int r){
		return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
	};

	int cov;
	vector<pair<int, int>> ans;

	do{
		ans.clear();
		cov = 0;
		
		int x0 = rng() % 100'000, y0 = rng() % 100'000;
		auto check_point = [&](int x, int y){
			int nearest_row = (y - y0) / h;
			for (int row = nearest_row - 2; row <= nearest_row + 2; row++){
				int nearest_col = (x - (x0 + (row % 2) * r)) / w;
				for (int col = nearest_col - 2; col <= nearest_col + 2; col++){
					int x_lat = x0 + col * w + (row % 2) * r;
					int y_lat = y0 + row * h;
					if (is_in_circle(x, y, x_lat, y_lat, r)){
						ans.emplace_back(x_lat, y_lat);
						cov++;
						return;
					}
				}
			}
		};

		for (int i = 0; i < n; i++){
			check_point(p[i].first, p[i].second);
		}
	} while(cov * 100 < 89 * n);

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	cout << ans.size() << '\n';
	for (auto [x, y] : ans){
		cout << x << ' ' << y << '\n';
	}
}
 
signed 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;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2225F - String Cutting

Author: FelixArg

Tutorial

Solution 1 (FelixArg)

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long

const int MODS[] = {some hidden number 1, some hidden number 2};
const int P = some hidden number 3;

int powP[2][1'000'007];
int inv_powP[2][1'000'007];

int bpow(int x, int p, int mod){
	int res = 1;
	while(p){
		if (p % 2 == 1){
			res = (res * x) % mod;
		}
		p >>= 1;
		x = (x * x) % mod;
	}
	return res;
}
 
void solve(){
	int n, l, k;
	cin >> n >> l >> k;
	string s;
	cin >> s;
 
	if (l * k > n){
		cout << "NO\n";
		return;
	}
 
	if (k == 1){
		cout << "YES\n";
		cout << s << '\n';
		return;
	}

	vector<vector<int>> h(2, vector<int>(n + 1));
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < n; j++){
			h[i][j + 1] = (h[i][j] + (s[j] - 'a' + 1) * powP[i][j]) % MODS[i];
		}
	}

	function<pair<int, int>(int, int)> get_h = [&](int l, int r){
		return make_pair((h[0][r + 1] - h[0][l] + MODS[0]) * inv_powP[0][l] % MODS[0],
		(h[1][r + 1] - h[1][l] + MODS[1]) * inv_powP[1][l] % MODS[1]);
	};
 
	function<int(int, int, int, int)> cmp_substring = [&](int l1, int r1, int l2, int r2){
		int len1 = r1 - l1 + 1;
		int len2 = r2 - l2 + 1;

		int l = 0, r = min(len1, len2) - 1;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (get_h(l1, l1 + m) != get_h(l2, l2 + m)){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}

		char ch1 = (l < len1 ? s[l1 + l] : 'a' - 1);
		char ch2 = (l < len2 ? s[l2 + l] : 'a' - 1);
 
		if (ch1 < ch2){
			return -1;
		}
		if (ch1 > ch2){
			return 1;
		}
		return 0;
	};
 
	int la = 0, ra = l - 1;
 
	for (int i = 0; i < n; i++){
		int cnt = i / l;
		if (i > 0 && cnt == 0){
			continue;
		}
		int len = i + max(0ll, (k - 1) - cnt) * l;
		if (n - len >= l){
			if (cmp_substring(i, i + n - len - 1, la, ra) == 1){
				la = i;
				ra = i + n - len - 1;
			}
		}
	}
 
	cout << "YES\n";
	cout << s.substr(la, ra - la + 1) << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	powP[0][0] = powP[1][0] = 1;
	inv_powP[0][0] = inv_powP[1][0] = 1;
	int inv_p[] = {bpow(P, MODS[0] - 2, MODS[0]), bpow(P, MODS[1] - 2, MODS[1])};

	for (int i = 1; i < 1'000'001; i++){
		for (int j = 0; j < 2; j++){
			powP[j][i] = powP[j][i - 1] * P % MODS[j];
			inv_powP[j][i] = inv_powP[j][i - 1] * inv_p[j] % MODS[j];
		}
	}

 
	int tests = 1;
	cin >> tests;
	while(tests--){
		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 (BledDest)

#include <bits/stdc++.h>
 
using namespace std;
 
int n, l, k;
string s;
string cur;
int zf[2000043];
mt19937 rnd(421337);
 
void z_function(const string& s) 
{
    int n = s.size();
    for(int i = 0; i < n; i++) zf[i] = 0;
    for (int i = 1, l = 0, r = 0; i < n; i++) 
    {
        if (i <= r)
            zf[i] = min(r - i, zf[i - l]);
        while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]])
            zf[i]++;
        if (i + zf[i] > r) 
        {
            l = i;
            r = i + zf[i];
        }
    }        
}
 
bool read()
{
    if (!(cin >> n >> l >> k))
        return false;
    cin >> s;
    return true;
}    
 
string find_best(vector<pair<int, int>> cand)
{
    while(true)
    {
        if(cand.size() == 1)
            return s.substr(cand[0].first, cand[0].second);
        int lf = cand[0].first;
        int rg = cand[0].first + cand[0].second;
        for(int i = 1; i < cand.size(); i++)
        {
            lf = min(lf, cand[i].first);
            rg = max(rg, cand[i].first + cand[i].second);
        }
        auto p = cand[0];
        cur = s.substr(p.first, p.second) + "?" + s.substr(lf, rg - lf);
        z_function(cur);
        vector<pair<int, int>> better;
        int len = p.second;
        for(int i = 0; i < cand.size(); i++)
        {
            if(cand[i] == p) continue;
            int L = cand[i].first - lf;
            int cur_len = cand[i].second;
            int lcp = zf[len + 1 + L];
            lcp = min(lcp, cur_len);
            if(lcp == cur_len || (len > lcp && cur[L + len + 1 + lcp] <= cur[lcp]))
                continue;
            better.push_back(cand[i]); 
        }
        if(better.empty())
            return s.substr(p.first, p.second);
        else
            cand = better;
    }
    return "";
}
 
void solve()
{
    if(k * 1ll * l > n)
    {
        cout << "NO\n";
        return;
    }
    if(k == 1)
    {
        cout << "YES\n" << s << "\n";
        return;
    }
    vector<pair<int, int>> cand;
    for(int i = 0; i < n; i++)
    {
        if(i > 0 && i < l) continue;
        int lf = i / l;
        int rg = (n - i) / l;
        if(lf + rg < k) continue;
        int need_rg = max(0, k - lf - 1);
        int len = (n - need_rg * l) - i;
        if(len >= l)
            cand.push_back(make_pair(i, len));    
    }
    shuffle(cand.begin(), cand.end(), rnd);
    if(cand.empty())
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n" << find_best(cand) << "\n";
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int tc = 1;
    cin >> tc;
    while (tc--)
    {
        read();
        solve();
    }
}

2225G - Simple Problem

Author: basalov_yurij

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<int> g;

bool read()
{
    if(!(cin >> n >> m)) return false;
    k.resize(m);
    for(int i = 0; i < m; i++) cin >> k[i];
    return true;
}

pair<vector<int>, vector<int>> get_chain(int start, int rank)
{
    if(rank == 0)
        return make_pair(vector<int>({start}), vector<int>());
    pair<vector<int>, vector<int>> p = get_chain(start, rank - 1);
    int cnt = g[rank - 1] / g[rank];
    for(int i = 1; i < cnt; i++)
    {
        p.second.push_back(k[rank]);
        int next_start = (p.first.back() + k[rank]) % k[0];
        pair<vector<int>, vector<int>> q = get_chain(next_start, rank - 1);
        for(auto x : q.first) p.first.push_back(x);
        for(auto x : q.second) p.second.push_back(x);
    }
    return p;
}

void solve()
{
    g = k;
    for(int i = 1; i < m; i++)
        g[i] = gcd(g[i - 1], k[i]);
    if(g.back() != 1)
    {
        cout << -1 << "\n";
        return;
    }   
    if(k[0] == 1)
    {
        for(int i = 0; i < n; i++)
        {
            if(i) cout << " ";
            cout << i;
        }
        cout << "\n";
        return;
    }
    pair<vector<int>, vector<int>> chain = get_chain(0, m - 1);
    vector<int> classes = chain.first;
    vector<int> add = chain.second;
    vector<int> ans;
    int new_begin = 0;
    for(int i = 0; i < classes.size(); i++)
    {
        int new_end = -1;
        for(int j = classes[i]; j < n; j += k[0])
            if(j != new_begin)
            {
                new_end = j;
                break;
            }
        ans.push_back(new_begin);
        for(int j = classes[i]; j < n; j += k[0])                                                   
            if(j != new_begin && j != new_end)
                ans.push_back(j);
        ans.push_back(new_end);
        if(i + 1 < classes.size())
            new_begin = new_end + add[i];
    }
    for(int i = 0; i < n; i++)
    {
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}

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

ll mul(ll a, ll b) { a %= MOD; b %= MOD; ll res = 0; while (b > 0) { if (b%2==1) { res = (res+a)%MOD; } a = (2*a)%MOD; b/=2; } return res; } //------------------------BE THE BEST---------------------------------------------- void solve(){ ll n,x; cin>>n>>x; ll y = (x/2)+1; ll k = x + !(x%2); if(k>n) {cout<<0<<endl; re;} ll ans = 0; if(y%2==1) { n++; ll z = (n-k)/4; if(k%4==0 || n%4==0) z++; n--; ll t = (n-x)/2; if(n%2==0) t+=((n-x)%2); else t++; ll c = t-z; ans = (((mul(z,((y/2)+1)))%MOD) +ans)%MOD; ans = (((mul(c,(y/2)))%MOD) +ans)%MOD; } else{ ll z = ((n-k)/2)+1; if(n%2==0 && k%2==0) z--; ans = (((mul(z,(y/2)))%MOD) +ans)%MOD; } cout<<ans<<endl; }

Comments (41)

Write comment?

BledDest

3 weeks ago, hide # |

Auto comment: topic has been translated by BledDest (original revision, translated revision, compare)

→ Reply

sushant4599

Damn!! Fastest Edu Round editorial

adaptatron

3 weeks ago, hide # ^ |

I made video editorial for the key idea behind D. Exceptional Segments.

I also made video editorial for F. String Cutting.

wery0

+10

I tried to solve problem G by explicitly building a graph and heuristically finding hamiltonian path in it using approach from this blog, but failed.

Does someone have a heuristic algorithm for finding hamiltonian path which will actually be good enough to solve problem G?

golomb

372054437

Rakshit_1

-26

Very nice contest !

Suzuran

+12

Is the randomness of test36 of E good enough?I use hexagonal close packing centered (0,0)and have roughly 90% accuracy in test2-35 stably,but drop to 78.35% in test36.

monaxia

The test aims to punish codes that have predictable starting points, I guess.

It is generated in the same way as the other tests. However, this is the first test with $$$x = 10^5$$$, all tests before it use smaller rectangles.

ggq15plus2

Are your iteration bounds enough for covering the whole square? You can try initially generate more than n circles and then greedily take those with the most points enclosed.

psgawa

Why can't I hack submissions on problem F?

mhnd01s

Tutorial for D is incomplete. The number of required indices for a specific value to the left or to the right of x can be found by simple division, based on the pattern. You have to show how to do this simple division.

We believe that some simpler parts of the solution should be figured out by participants themselves. But if you've tried to do it and got stuck, check out the spoiler

Spoiler

Thanks

aryanc403

My post contest discussion stream for ABCDF https://mirror.codeforces.com/blog/entry/153161
Youtube VOD

dirtblock

problem E was cool, but now i wonder if it can be possible by using a greedy method, or if hexagonal packing is the only possible way...

vitural

same question, since that was my first approach after giving up

man-ray

where is the tutorial of problem G

madamadam

+21

first, the aim of the problem is to find a hamiltonian path in the numbers 0..n-1, where i and j have an edge iff |i-j| is divisible by any element in a set of integers k.

clearly, if gcd(k) != 1, there is no solution (cannot link up different sets)

lets say we have the numbers 1..n and a set of integers k. if we choose some element x ∈ k, and we group all nodes that have an edge because |a-b| divisible by x, we get a set of x cliques, where nodes within the cliques all have the same remainder mod x. as these are cliques, we can freely order the nodes within them, so the only nodes that matter are the start and end nodes

now we should look at edges that cross cliques. say clique 0 and clique y have at least 1 edge between them, then so do clique 1 and y+1, clique 2 and y+2 etc (obvious). so this actually looks like the same problem as before, just now on x < n nodes, but the same set k.

so the problem can be solved recursively, let f(n,k) -> vector be a sequence of n-1 "jumps" that is the difference array for a solution with that n and k. f(n,k) = [clique 0] -> [some other clique that 0 has an edge to] -> [clique with an edge to] etc. if there are x cliques, we can determine the cross jumps needed by f(x,k), and the intra jumps by adding x each time

finally to reconstruct the order, notice that for each clique we just care about the entry and exit node, and they need to be different. as k[i] <= n/3, every clique has >= 3 nodes, which is helpful. simple greedy method can be used to choose the entry and exit nodes for each clique

hope it helps

refrxn

Is the way to do C other than DP is greedily take vertical segments, else try take it horizontally? We have to take min(count from left, count from right)? Please help me if you've done it without DP.

Jimmy47

I don't think there will be a greedy solution here as you can easily see that their are two ways , like in first the two horizontal adjacent cells are of same color in both row or the two vertical row are of same color , so what happens here is that after you have decided colors for them you don't care about these choices for the next ones but the issue is that you cannot optimally choose for one of both those choices here and tbh dp was very intuitive idea here and maybe after more practice you will just see dp idea coming intuitively for this one

rishuvaiya_12

← Rev. 2 →

Yes we can do it greedily

if a[i]==b[i] then regardless of a[i+1] and b[i+1] we choose to pair a[i] and b[i] and increase i by 1

else

if a[i]!=a[i+1] and b[i]!=b[i+1], we pair up a[i] and b[i] and increase ans by 1, i by 1

else if one of the conditions is false we increase ans by 1 and i by 2(horizontal pairing) if both conditions are false then we simply increase i by 2

372033411

Siemperman

2 weeks ago, hide # ^ |

Even simpler: When a[i] != b[i], we only need to place two dominoes horizontally if a[i] == a[i+1] and b[i] == b[i+1]. Otherwise, we will need to add 1 or 2 anyway, whichever way we place them, so we can just place one vertically and continue with the next column. 371998802

Mohamed2Rayen

i think your approach is wrong, what if the input is RR BR your code will give 0 as output, but the right answer is 1 tell me if am i wrong

No, that will work as well. First, it will encounter a[0] == R and b[0] == B. Therefore, it checks whether a[0] == a[1] and b[0] == b[1]. This is not the case. In the code I sent (which got accepted), we count the number of correct dominoes, so we will just continue for i == 0. For i == 1, it finds a[1] == b[1] and thus adds 1 to the count. Then, it returns 2 — 1 = 1 wrong dominoes / tiles that need to be repainted.

SirMrGuy

Label the columns with three labels — 0 if the two cells are the same, 1 if red is on top, 2 if blue is on top. Then break it into contiguous chunks with the same label.

Chunks with label 0 can be ignored because we can cover them completely with vertical pairs. The other chunks can be covered with horizontal pairs if the length of the chunk is even. Otherwise, we have one column left over which we can flip a cell of so we can cover it with a vertical pair. So the answer is the count of all chunks with odd length that are labeled 1 or 2.

Solution

pransh_8

My solution

Why I think it works

Anil_Sailla

This is my greedy approach submission:

solution

hecko_yes

my method was, if the next 2 columns can do horizontal without switching then go horizontal, otherwise just take one column (if it would cost 1 to switch for horizontal then that means there's 3 red 1 blue or vice versa, in which case vertical costs the same so might as well go with that)

E looks quite unique problem and I haven't seen one of its kind anywhere , is there any place we can practice these type of problems and are there some similar problems there online ? Also how to think about these type of problems when solving them for the first time? __

Heuristics problem i think

xndr

I was able to use suffix array for F (though I didn't get it in contest): submission

Idea was to go backwards from the end in the suffix array (so in decreasing order of suffix order) and check feasibility of the suffix. If we have found a feasible suffix $$$a$$$, another feasible suffix $$$b$$$ that is earlier in the suffix array can only improve the solution if $$$a$$$ is a prefix of $$$b$$$. So we can keep a running min of the lcp array as we scan over the suffixes to check this condition.

marcus06

+16

Can anyone explain the constraint "a circle's area is at most $$$\frac{1}{10}$$$ of the rectangle's area". How does it specifically impact the solution for Problem E?

When the area of the circle is too big, the choice of starting point (from which we build the hexagonal pattern) affects the result much more severely. So, it increases the probability that you pick a "bad" starting point in the beginning by making the random less "pure".

XDEv11

But how does this constraint relate to covering 89% of the points? It seems like there should be enough starting positions to cover 89% of the area.

azure-

imagine if you place a circle with a large enough radius such that every point is within 2*r of the circle but not necessarily within r of the circle. You can have many points outside that you can't center circles at because they would intersect with the already placed circle. The area constraint makes it so there will generally be a point far enough away from the circle that can be used to center an additional circle at.

My opinion: Because the area of the rectangle is bounded, we can't achieve ~ 90% density using hexagon packing if the radius is too big. On wikipedia they work with the infinite space, and the density converge to ~ 90% regardless of circle radius.

vasuganesha1

weak pretest for problem F

NiekvD

When finding circles that can contain point p, why do we check the 5 nearest rows and cols and when is checking 3 not enough?

arpitpathak

2 weeks ago, hide # |

My solution for D, using observation that xor of consecutive 4 numbers with starting number being even number, is always 0. In code, y : number of even numbers before x (inclusive of x). t : total number of odd numbers between x and n (inclusive). z : (when y is odd, in case of even y, answer added for each odd number is same y/2): number of odd number, i between x and n (inclusive) such that (i+1) is divisible by 4. mul : modular binary multiplication function.

wangzehao

Dear Codeforce Team,
I am writing to appeal the "skipped" verdict on my submisson for problem D in the contest Educational round 189. This is my code's number
372047076.
The problem revolves around the xor sum from one to n, which is a well-known conclusion.The first time I learned it form csdn blog which sowed the seed i solved this problem.
My code is around four key functions to count the numbers mod 1 and 3 in the left and right.This is because i found that 2 or 4 can't contribute to the result, i didn't count them. n≡1(mod4),the result is always 1.n≡3(mod4),the result is always 0.Then it comes to the main function, i speed up input and output, afraid of tle.Then comes to the key point,i set four variable temp1,temp2,temp3,temp4,with my functions.The reason why i write +1 is a specific boundary correction i made during my thinking.S0=0.So i add 1.Then set two variable to multply temp1 and temp3 to get res1,temp2 and temp4 to get res2 ，Then i add them, with mod 998245353. So this is my code. I couldn't believe that my code would be similar with others because i thought my code is a little redundancy,i manually finished it with pressure, and also try to revise my errors with the examples. I apologize for the verbose implementation, but it helped me avoid mistakes.Thank you for your time and for maintaining a fair competitive on codeforce.I am confident my code is an original result. I look forward to your positive reponse.
Best regards,
wangzehao
include
define mod 998244353
using namespace std;
long long count_1_l(long long r){
long long temp1=r%4;
long long temp2=r/4;
if(temp1>=1){
temp2++;
}
return temp2;
}
long long count_3_l(long long r){
long long temp1=r%4;
long long temp2=r/4;
if(temp1>=3){
temp2++;
}
return temp2;
}
long long count_1_r(long long l, long long n){
long long temp1=l%4;
long long temp2=l/4;
long long temp3=n%4;
long long temp4=n/4;
if(temp1>=1){
temp2++;
}
if(temp3>=1){
temp4++;
}
return temp4-temp2;
}
long long count_3_r(long long l, long long n){
long long temp1=l%4;
long long temp2=l/4;
long long temp3=n%4;
long long temp4=n/4;
if(temp1>=3){
temp2++;
}
if(temp3>=3){
temp4++;
}
return temp4-temp2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
long long t;
cin >> t;
while(t--){
long long n, x;
cin >> n >> x;
long long left_limit = x — 1;
long long temp1 = count_1_l(left_limit);
long long temp2 = count_3_l(left_limit) + 1;
long long temp3 = count_1_r(left_limit, n);
long long temp4 = count_3_r(left_limit, n);
long long res1 = (temp1 % mod) * (temp3 % mod) % mod;
long long res2 = (temp2 % mod) * (temp4 % mod) % mod;
cout << (res1 + res2) % mod << endl}
return0}

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	162
2	adamant	150
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

BledDest's blog

include

define mod 998244353