Codeforces Round #705 (Div.2) Editorial

#	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	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (74TrAkToR)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t, n, k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        cout << n - k + k / 2 << '\n';
        for (int i = k + 1; i <= n; ++i) cout << i << " ";
        for (int i = (k + 1) / 2; i < k; ++i) cout << i << " ";
        cout << '\n';
    }

    return 0;
}

1493B - Planet Lapituletti

Idea: AlFlen

Tutorial

Solution (74TrAkToR)

#include <bits/stdc++.h>

using namespace std;

vector < int > go = {0, 1, 5, -1, -1, 2, -1, -1, 8, -1};
int inf = 1e9 + 7;

int get(int x) {
    string s = to_string(x);
    if ((int)s.size() == 1) s = "0" + s;
    string answ = "";
    for (int i = 1; i >= 0; --i) {
        if (go[s[i] - '0'] == -1) return inf;
        answ += char(go[s[i] - '0'] + '0');
    }
    return stoi(answ);
}

string good(int x) {
    string ans = to_string(x);
    if (x < 10) {
        ans = "0" + ans;
    }
    return ans;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, h, m, H, M;
    cin >> t;
    string s;
    while (t--) {
        cin >> h >> m;
        cin >> s;
        H = (s[0] - '0') * 10 + s[1] - '0';
        M = (s[3] - '0') * 10 + s[4] - '0';
        while (1) {
            if (M == m) {
                H++, M = 0;
            }
            if (H == h) {
                H = 0;
            }
            if (get(M) < h && get(H) < m) {
                cout << good(H) << ":" << good(M) << '\n';
                break;
            }
            M++;
        }
    }
    return 0;
}

1493C - K-beautiful Strings

Idea: 74TrAkToR

Tutorial

Solution (74TrAkToR)

#include <bits/stdc++.h>

using namespace std;

int cnt[26];

int get(int x, int k) {
    return (k - x % k) % k;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        string s;
        cin >> s;
        for (int j = 0; j < 26; ++j) cnt[j] = 0;
        for (auto c : s) cnt[c - 'a']++;

        int sum = 0, flag = 1;
        for (int i = 0; i < 26; ++i) {
            sum += get(cnt[i], k);
        }

        if (sum == 0) {
            cout << s << '\n';
            flag = 0;
        }

        if (n % k != 0) {
            cout << -1 << '\n';
            continue;
        }

        for (int i = n - 1; i >= 0 && flag; --i) {
            sum -= get(cnt[s[i] - 'a'], k);
            cnt[s[i] - 'a']--;
            sum += get(cnt[s[i] - 'a'], k);
            for (int j = s[i] - 'a' + 1; j < 26; ++j) {

                int lst_sum = sum;
                sum -= get(cnt[j], k);
                cnt[j]++;
                sum += get(cnt[j], k);

                if (i + sum + 1 <= n) {
                    for (int pos = 0; pos < i; ++pos) {
                        cout << s[pos];
                    }
                    cout << char('a' + j);

                    string add = "";
                    for (int w = 0; w < 26; ++w) {
                        int f = get(cnt[w], k);
                        while (f) {
                            f--;
                            add += char('a' + w);
                        }
                    }
                    while ((int)add.size() + i + 1 < n) {
                        add += "a";
                    }

                    sort(add.begin(), add.end());
                    cout << add << '\n';
                    flag = 0;
                    break;
                }

                cnt[j]--;
                sum = lst_sum;
            }
        }
    }
    return 0;
}

1493D - GCD of an Array

Idea: 74TrAkToR

Tutorial

Solution (74TrAkToR)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int const maxn = 2e5 + 5, max_val = 2e5 + 5;
ll mod = 1e9 + 7, ans = 1;
int nxt[max_val], n;
multiset <int> cnt[max_val];
map <int, int> cnt_divisor[maxn];

void add(int i, int x) {
    while (x != 1) {
        int div = nxt[x], add = 0;
        while (nxt[x] == div) add++, x = x / nxt[x];

        int lst = cnt_divisor[i][div];
        cnt_divisor[i][div] += add;
        int lst_min = 0;
        if ((int)cnt[div].size() == n) {
            lst_min = (*cnt[div].begin());
        }
        if (lst != 0) {
            cnt[div].erase(cnt[div].find(lst));
        }
        cnt[div].insert(lst + add);
        if ((int)cnt[div].size() == n) {
            for (int j = lst_min + 1; j <= (*cnt[div].begin()); ++j) {
                ans = ans * (ll)div % mod;
            }
        }
    }
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int q, l, x;
    cin >> n >> q;

    for (int i = 2; i < maxn; ++i) {
        if (nxt[i] == 0) {
            nxt[i] = i;
            if (i > 10000) continue;
            for (int j = i * i; j < maxn; j += i) {
                if (nxt[j] == 0) nxt[j] = i;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cin >> x;
        add(i, x);
    }

    for (int i = 1; i <= q; ++i) {
        cin >> l >> x;
        add(l, x);
        cout << ans << '\n';
    }

    return 0;
}

1493E - Enormous XOR

Idea: AlFlen

Tutorial

Solution (74TrAkToR)

#include<bits/stdc++.h>

using namespace std;

string add(string s) {
    int i = (int)s.size() - 1;
    while (s[i] == '1') {
        s[i] = '0';
        i--;
    }
    s[i] = '1';
    return s;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string l, r;
    cin >> l >> r;
    if (l == r) {
        cout << r << '\n';
        return 0;
    }
    if (l[0] != r[0]) {
        for (int i = 1; i <= n; ++i) cout << "1";
        return 0;
    }
    if (add(l) == r || r.back() == '1') {
        cout << r << '\n';
        return 0;
    }
    cout << add(r) << '\n';
    return 0;
}

1493F - Enchanted Matrix

Idea: 74TrAkToR

Tutorial

Solution (74TrAkToR)

#include <bits/stdc++.h>

using namespace std;

int const maxn = 1005;
int dp[maxn];
vector < vector < int > > T;

int ask(int lx1, int ly1, int rx1, int ry1, int lx2, int ly2, int rx2, int ry2) {
    cout << "? " << rx1 - lx1 + 1 << " " << ry1 - ly1 + 1 << " " << lx1 << " " << ly1
    << " " << lx2 << " " << ly2 << endl;
    int ans;
    cin >> ans;
    return ans;
}

int good(int l, int r) {
    if (l == r) return 1;

    int cnt = (r - l + 1) / 2;
    if (ask(T[l][0], T[l][1], T[l + cnt - 1][2], T[l + cnt - 1][3], T[l + cnt][0], T[l + cnt][1], T[l + 2 * cnt - 1][2], T[l + 2 * cnt - 1][3])) {
        return good(l + cnt, r);
    }
    return 0;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, cntn = 0, cntm = 0;
    cin >> n >> m;

    for (int i = n; i >= 1; --i) {
        if (n % i != 0 || dp[i] != 0) continue;

        for (int j = 2 * i; j <= n; j += i) {
            if (n % j == 0 && j % i == 0) {
                T = {};
                for (int k = 1; k <= j / i; ++k) {
                    T.push_back({(k - 1) * i + 1, 1, k * i, m});
                }
                if (good(0, (int)T.size() - 1)) dp[i] = 1;
                else dp[i] = 2;
                break;
            }
        }

        if (dp[i] == 2) {
            for (int j = 1; j <= n; ++j) {
                if (i % j == 0) dp[j] = 2;
            }
        }
        else {
            dp[i] = 1;
            for (int j = i; j <= n; ++j) {
                if (dp[j] == 1) {
                    int w = __gcd(i, j);
                    for (int pos = w; pos <= n; pos += w) {
                        dp[pos] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) cntn += (dp[i] == 1);
        dp[i] = 0;
    }

    for (int i = m; i >= 1; --i) {
        if (m % i != 0 || dp[i] != 0) continue;

        for (int j = 2 * i; j <= m; j += i) {
            if (m % j == 0 && j % i == 0) {
                T = {};
                for (int k = 1; k <= j / i; ++k) {
                    T.push_back({1, (k - 1) * i + 1, n, k * i});
                }
                if (good(0, (int)T.size() - 1)) dp[i] = 1;
                else dp[i] = 2;
                break;
            }
        }
        if (dp[i] == 2) {
            for (int j = 1; j <= i; ++j) {
                if (i % j == 0) {
                    dp[j] = 2;
                }
            }
        }
        else {
            dp[i] = 1;
            for (int j = i; j <= m; ++j) {
                if (dp[j] == 1) {
                    int w = __gcd(i, j);
                    for (int pos = w; pos <= m; pos += w) {
                        dp[pos] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= m; ++i) {
        if (m % i == 0) cntm += (dp[i] == 1);
    }
    cout << "! " << cntn * cntm << endl;
    return 0;
}

Comments (120)

Show archived | Write comment?

sid_rasa

4 years ago, # |

+20

This fast :0

→ Reply

kassutta

4 years ago, # ^ |

-15

Video Editorial For problem C- K-Beautiful Strings: https://youtu.be/bCeBtoho8II

Sai_t

FastForces :)

chilliagon

-25

Why did 109265569 give Wrong answer for problem D. TLE would be given if time limit had exceeded. But why wrong answer?

PraveenDhinwa

← Rev. 2 →

Numbers won't fit in the desired data type. We are multiplying each element by x in each query. Suppose x is like 2 * 10^5, even in 100 queries, x would become 10^105 which is so large.

E404_Not_Found

So how to solve that ?

xuqin

We just need to save the factors of x, they and their times are less than or equal to 2 * 10 ^ 5

Puc_Puc

-26

Does Segment Tree + bignumber work for D?

beingsebi

Most likely you'll get TLE. The numbers can get huge if for example we have 1 number and multiply it by 2e5 every time.

hackerbhaiya

i tried to use segment tree but it gave tle :(

aabrakadabra

i tried using seg tree but it gives WA. i used this approach https://mirror.codeforces.com/contest/1493/submission/109260301

Triple-H

Modifying it (segment tree) correctly can give AC. See this 109274205

alokmaurya_81

why storing factors in map ? we can not use gcd function? why this logic is not working ? https://mirror.codeforces.com/contest/1493/submission/109252075)

igorwwylson

+10

gcd of a set of numbers is the number consisting of the intersection of the prime numbers of each number in the set. You just need to take the modulo remainder of any number from the set to ruin everything

For example a = 10, b = 5, c = 35, mod = 4. GCD(a, b) = 5, 5 mod 4 = 1. gcd(1, 35) = 1. But, gcd(a, b, c) = 5. You can use segment tree, but you need to think in another key.

It was a bad example, sorry. Correct example: a = 50, b = 25, c = 100, mod = 9. gcd(50, 25) = 25. 25 mod 9 = 7. gcd(7, 100) = 1. But, gcd(a, b, c) = 25. 25 mod 9 = 7.

ekansh9927

Can you explain, what exactly "addl" and "addr" is doing?

The map in each node of the tree contains the excess counts of various primes (i.e. information pertaining to which — left or right child of that node has excess).

Now in order to update a node, we need to inform the node whether the left child has its gcd updated or the right child. This is communicated by calling addl() when the left child's gcd is multiplied by some factor (similarly addr()).

Comprehensively, say some node's gcd has been multiplied by x, and it happens to be a left child. In this case, its parent will call addl passing x. addl will then factorise x and use these factors and the map to find the additional factors that the right child had which can be combined and used to updated the gcd here. The state of the map is also updated here.

addr performs a similar task.

PhantomAssassin

a [i] can be equal to 10 ^ (10 ^ 5) and __gcd work in log (n). obviously it will be TLE

Can you analyse my code's time complexity which got tle on pretest 4!!

Each time you run over the common divisor of the sons of the vertex. but there can be a lot of them. -> This is to add time log (x)

log (n) from tree, log (x) from multiset, and the number of common prime divisors of sons-> log (x) general asymptotics O (qlog (X) Log (x) log (n)) is TLE ~ 11sec

adam_rajsky

+12

Bignumber will definitely TLE, because operations with bigint -> +-/* work in polynomial time relative to the length of the number.

I got an AC, 109274205, while using a segment tree (modified) which ran in <650ms. The idea was to have for each segment [l,r] store the gcd of the range and a map storing for each extra prime (which is in excess in either the left or right range) its frequency (negative or positive depending on which range has excess).

Now, in order to update a tree node (query), you can prime factorize the value and compare prime factors with elements of the map, and update them along with the gcd.

Can someone calculate a tight bound on the time complexity, as according to me its O(n log^3 n)? [log^3 -> at each level prime factorize and for each prime factor update a map value]

TokaiHachimi

← Rev. 4 →

I think use SegmentTree to solve D is easier. 109248519.

We use a dynamic create point segment tree for each prime factor to maintain single point addition and global $$$\min$$$.

Regarding how to update the answer, every time we add a single point to the segment tree of a certain prime factor and see if the global $$$\min$$$ of this segment tree has changed, just fastpower the answer to multiply if it changes.

$$$ 2 \times 3 \times 5 \times 7 \times 11 \times 13> 2 \times 10^5 $$$, so we just modify at most 6 segment trees for a number change, so the time and space complexity are both It is $$$\mathcal O(6\times(n+q)\log a_i)$$$.

Emm... I used $$$\mathcal O((n+q)\sqrt {a_i})$$$ prime factor，you can use $$$\mathcal O(n - (n+q)\log a_i)$$$ :P

pied-piper

How is it easier? Instead of segment tree you can use multiset (as in editorial) since you only need the minimum of the full range everytime. Am I missing something?

Liu_QY

This comment should not be downvoted, it is a friendly and kind discussion.

ShmilyTY

The editorial came out really fast, excellent!

I think this contest is as hard as I expected, and I only solve the first three problems.:(

I hope I won't get any fst. ples!

mushroom_knight

-10

A very great contest.

Let me know how silly I am.

E is very easy but I wrote a very long and incorrect code :(

gabaswillwinIOI2022

Why you just don't give transformations in B

alexrider

n problem B there is one test case 51 3 30:01 (8th case) How is answer 50:00? shouldn't the answer be 00:00? as if 50:00 then 00:05 isn't a valid time...plz explain someone

https://mirror.codeforces.com/contest/1493/submission/109793069 here is my submission Can you plz help me out? is the jury's answer wrong?

vishwas_007

You forgot to consider the fact that mirror image of 5 will be 2, So this is valid time.

abhay.raihal

3 years ago, # ^ |

thx bro great help

aknov711

Not so easy round! xD

tiger_2005

Such a FAST update! It really helps me because I can't wait to learn the solutions of the problems!

← Rev. 3 →

-34

Waiting for another contest from you :)) !

Implementation heavy contest. But I think questions were not that much tough.

epsilon_573

I hastily read the problem statement for C and solved it for exactly k occurrences. Feel so dumb now. Also this contest seemed more on the implementation side.

Makise_Kurisu

Can someone explain how to estimate the time complexity of D?

(n + q)log(max(X))

we can get answer for each request in log (x) using Eratosthen

UPD: i missed log from mutiset

navneet.h

multiset factor is missing

BucketPotato

Thank you for the contest!

yash_daga

+46

I had a slightly different approach to D which didn't require the use of multiset, first we calculate the gcd after processing all the queries and after that we process the queries in reverse order where instead of multiplying we divide the index with the number given and if the number occurrences of a prime factor becomes less than the number of occurrences in the current answer we change the answer accordingly.

ZiadEl-Gafy

There were some difficult problems but still a great, well put together round after all!

uttaran_das

Anyone having tough times understanding C?

DIVANSHMAHAJAN29

-18

can someone explain d?why answer wont dec it can be 1 also sometimes..

parveen1981

GCD is really the smallest power of each prime multiplied together. So after multiplying a value x, for each prime, its power is not going to decrease.

mykhail0

I do not think this is true for problem C: "If the string s is beautiful, then s itself is the answer." Because the length of s can be smaller than n as I it does not state otherwise in the problem statement. Otherwise a great tutorial. I had the exact same idea but took me too long to implement it sadly:(

AlFlen

+14

length of s is always n, as it says in the input section of the statement

Indeed. Sorry then. Was a great contest!

adiagr

probelm B: https://mirror.codeforces.com/contest/1493/submission/109275855 Im not able to figure out the mistake.

alsoba

You are setting "a" to 2 and two lines below you are setting the same 2 to 5. Same for var b. Those if should have been if-else. I don't know if there are more problems, but at least that is.

YangTY

I used segment tree in D and it worked well. Just add new nodes dynamically so as not to get a TLE.

jack07

I cannot get the mistake in my Problem C's code. (WA on test 3 (272th line).

Could someone help?

Code link

wwch

Maybe you need to increase the amount of occurences of 'a' on suffix to make sure that the length of answer equals n instead of adding the letter *st.begin() .

shubham320

Thank you for fast tutorial!

rgnerdplayer

According to the editorial, I think it would be better if you used -1 for not calculated states. Using dp=2 is a little bit confusing, because as you said in the editorial, number of r is just the sum of dp... and etc. Just some advice.

TheRoot

until now i don't know why segment tree got MLE, i think because of recursion

here is my impl. if you wanna chick it

https://mirror.codeforces.com/contest/1493/submission/109276549

Why this logic is not working in problem D can anyone tell me please? Link : https://mirror.codeforces.com/contest/1493/submission/109252075

You can't take modulo like that

For example if (mod = 3)

array = {4,6,8}, gcd(array) = 2

then if we get modulo for them

array = {1,0,2}, gcd(array) = 1

Ferrarixxx

Am getting Runtime Error on TC 4
Submission Link: https://mirror.codeforces.com/contest/1493/submission/109286557

I have taken the variable names as intuitive as possible in case you decide to help me.
Please tell me why am I getting this error, what mistake have i made in my code.

Thanks in Advance !!

TheLethalCode

// find and update in set
auto it = factor_to_freq_index[factor].find({prev_freq, i});
if (it != factor_to_freq_index[factor].end())
        factor_to_freq_index[factor].erase(it);

I am not particularly sure, but in a rough glance this seems to stand out. If previously there were no factors for $$$a_i$$$, prev_freq will be $$$0$$$, and you will be erasing some random element from the factors frequency set.

TheScrasse

+16

Problem F: you can check if $$$k$$$ is a period in $$$3$$$ queries.

This is equivalent to check if $$$x = n/k$$$ "blocks" of $$$k$$$ rows are equal.

Let $$$[l, r]$$$ be the segment of blocks from $$$l$$$ to $$$r$$$. Let $$$y = \lfloor (x-1)/2 \rfloor$$$.

It's enough to check if

$$$[1, y] = [y + 1, 2y]$$$
$$$[1, y] = [y + 2, 2y + 1]$$$
either $$$x$$$ is odd, or $$$[1, x/2] = [x/2 + 1, x]$$$

This was enough to get AC with some dirty randomization. 109275723

jeroenodb

I also used kind of the same approach, but without randomization it also passed. 109267700. I tested my approach locally against all pairs of $$$r,c \leq 1000$$$ with the worst case for my program (when all queries return 1, all elements are equal). For all r and c my approach was under the query limit.

r57shell

You need to cut only by primes. And if cut fails don't try same prime again. 109297822

I did check that n blocks are same: if n == 2 just compare 0 and 1, otherwise if n is prime then it's odd, so:

check [0,(n-1)/2-1] = [(n-1)/2,n-2]
check [1,(n-1)/2] = [(n-1)/2+1,n-1]
check [0,1] = [1,0] if necessary (now it looks like ababababa, and with n = 3 you already know a = b)

+21

Regarding to number of checks. Factorization of N has at most $$$\log_2(N)$$$ factors, for 2 it performs 1 check, for 3 it performs 2 checks, each factor >= 5 it performs 3 checks. For any M with prime factors >= 5 there is N < M with prime factors replaced into 5 with same worst case checks amount. In other words, worst checks count is maximum for some number $$$N = 2^a3^b5^c$$$, then checks $$$a+2b+3c$$$ and $$$\log_2(N) = a+b\log_2(3)+c\log_2(5)$$$. So, we want to maximize $$$a+2b+3c$$$ over constraint $$$a+b\log_2(3)+c\log_2(5) \leq \log_2(N). a, b, c >= 0.$$$ We can apply linear programming knowledge. For real values a,b,c maximum is bigger than any integer solution. Vertices gives $$$\log_2(N)$$$, $$$2\log_2(N)/\log_2(3)$$$, $$$3\log_2(N)/\log_2(5).$$$ So, winner is $$$\log_2(N)\cdot 3/\log_2(5)$$$ which is approximately $$$1.29203\cdot \log_2(N)$$$.

You can also do this: We only do one dimension of the grid at a time. Call this dimension n. Then the prime factorization of $$$n = p_0^{k_0}\cdot p_1^{k_1} \dots$$$. Do queries for each distinct prime factor. So for $$$p_i^{k_i}$$$ We need to find the biggest $$$c \leq k_i$$$ such that the grid can be divided in $$$p_i^c$$$ blocks. We do this incrementally. We can check first if the grid is divisible by p blocks. Than we check if the first out of these blocks is again divisible by p. We do this procedure recursively c times. For odd primes we can do this in 2 queries per divisibility check. For the only even prime $$$2$$$ we only have to do one query. So the worst case queries is # factors of 2 + 2* #factors of all other primes. The worst case is either $$$log_2(n)$$$ queries or $$$2 * log_3(n)$$$, the smallest odd prime. So the worst case for one dimension for this approach is $$$\frac{2}{log_2(3)} log(n) \approx 1.262 log(n)$$$

-8

how can you check with two queries for odd primes >= 5?

oh, I see now. it's above. [1,y]=[y+1,2y], [1,y]=[y+2,2y+1].

DrSwad

I think $$$2$$$ queries are enough. If $$$x$$$ is odd, check the first two points and if it's even, check the first and the last points. Here's a submission using $$$2$$$ queries.

TranLeHiep

I can check if k is a period in 2 queries.
if x = [n/k] "blocks" and x2 = [x/2]
I call {L,R} is blocks from L to R
if x odd you will check: {1,x2} = {x2 + 1,2 * x2} and {1,x2} = {x2 + 2,2 * x2 + 1}
if x even you check: {1,x2} = {x2 + 1,2 * x2} and {1,x2 — 1} = {x2,2 * x2 — 2}
This is my code: https://mirror.codeforces.com/contest/1493/submission/109450681

darkcoder123

Can anyone tell why my solution to D will not exceed the memory limit. As in my accepted solution I am creating a map of multiset of the number of each prime that I am getting. and in worst case, if a prime is present in all n elements then the size of this map of multiset will be (2*1e5)*20000 memory (as there are more than 20000 primes from 2 to 2e5), which is too huge to pass. But I am not sure how it is getting accepted?

GoatTamer

This applies for any solution which stores only non-zero prime powers for each element. Any number less than 2e5 is made of $$$<18$$$ unique primes. So initially, we have at max $$$18*n$$$ {prime, position} pairs. In each update, we are are multiplying by $$$x$$$ which can bring at most 18 more unique {prime, position} pairs into the map. So, in the end the map should not have more than $$$18(n+q)$$$ {prime,element} pairs, which is $$$O((n+q)log(max))$$$ memory complexity.

+22

Another way of proof 1493E - Огромный XOR.

very long proof

Let's say f(x) is XOR of all numbers in range [0, x] inclusive. Then XOR of all numbers within range [a, b] is f(b) XOR f(a-1) — idea is similar to prefix sum, so I usually call it prefix XORs. Then, easy to show that f(b) is:

b if b mod 4 = 0
1 if b mod 4 = 1
b + 1 if b mod 4 = 2
0 if b mod 4 = 3

Then, also easy to show that f(a-1) is:

a-1 if a mod 4 = 1
1 if a mod 4 = 2
a if a mod 4 = 3
0 if a mod 4 = 0

So, now we can see that our answer can be XOR of any of 16 combinations. Instead of considering each combination, it's easy to see that values can be 0, 1 or within range [l-1, r+1]. We also always can get r if we pick only number r. This naturally leads into question: when can we get f(b) XOR f(a-1) bigger than r?

Now, crucial observation is following: let say we XOR two numbers from range [l-1, r+1] and both l-1 and r+1 numbers starts with 1. (highest bit of number l-1 is 1, and highest bit of number r-1 is 1) Then all numbers within range [l-1, r+1] has highest bit 1 in its binary representation. Then any x XOR y within the range gives 0 in highest bit. In this case we know that any case with f(a-1) = a or f(a-1) = a-1, f(b) = b, f(b) = b+1 are useless because their XOR is less than r. In that case, one of value should be 0 or 1.

If one of values is 0, then 0 XOR v is just v. So, maximum is when v is maximum. Among 0,1,[l-1,r+1] maximum is r+1. And we already know how to get f(b) XOR f(a-1) = r. The value r+1 is possible only as f(b) = b+1 = r+1. In other words, when b = r. Also it require r mod 4 = 2. Then, we want f(a-1) = 0, and it is possible when a mod 4 = 0. If r mod 4 = 2 then (r — 2) mod 4 = 0, so f(r) XOR f(r-2) = r + 1 in this case. In other words, if r mod 4 = 2 and we can pick range [r-2, r], then we get r + 1. Otherwise, either r mod 4 != 2 and we can't get r + 1 value, or we can't get a mod 4 = 0 because l > r-2.

If one of values is 1, then 1 XOR v is v — 1 if v is odd, and v + 1 otherwise. We want v XOR 1 > r, this means either v is odd and v — 1 > r, thus v > r + 1, which is impossible; either v is even and v + 1 > r, thus v > r — 1, so v >= r.

Case v = r.

f(b) = b = r and f(a-1) = 1. b mod 4 = 0, a mod 4 = 2, in other words r mod 4 = 0 and r — 2 >= l so we can pick [r-2, r].
f(b) = b + 1 = r and f(a-1) = 1. b mod 4 = 2, in other words b = r — 1 and r — 1 mod 4 = 2. So r mod 4 = 3 which means r is odd, but we require r = v to be even, so this case is impossible.
f(b) = 1 and f(a-1) = a-1 = r. a-1 = r is impossible because a <= r.
f(b) = 1 and f(a-1) = a = r. b mod 4 = 1 and a mod 4 = 3. And, because a <= b <= r means b = r, but r mod 4 can't be equal to 1 and 3 at the same time. So this case is also impossible.

Case v = r + 1. This only possible when f(b) = b+1 = r+1 and f(a-1) = 1. b mod 4 = 2 and a mod 4 = 2. Here b = r, and r mod 4 = 2, so r + 1 mod 4 = 3 in other words v mod 4 = 3, which means v is odd. So, this case is also impossible.

Summary: if highest bit of all numbers within range [l-1,r+1] is 1, then we can always get r. If r is even we can try pick [r-2, r] and in case r mod 4 = 2 we get 0 XOR r+1 = r+1, or in case r mod 4 = 0 we also get r XOR 1 = r+1.

You can avoid checking cases above analytically, you can just check all allowed [a,b] where b in range [r-3,r] and a in range[b-3,a]. Because maximum of 0 XOR v or 1 XOR v is obviously reached only there.

Now, what happens when [l-1, r+1] has highest bits 0 and 1? First, case: when l and r has different highest bits, then we can get [01111....,10....] as [a,b] and get XOR = 111111... Otherwise [l,r] all has same highest bit.

Case highest bit of [l,r] is 0, then it doesn't satisfy conditions of the problem. In statement highest bit of r is 1 unless r = 0. Case r = 0 is trivial. Case highest bit of [l,r] is 1, then l-1 = 011111.... or r = 1 (trivial). We considered all cases when x XOR y highest bit both set, and also 0 XOR y and 1 XOR y. So cases we didn't check here is case 0111111.... XOR y, 011111... XOR 0, 011111.... XOR 1. But this require f(x) = 0111111.... = l-1. This is only possible when f(a-1) = a-1 = l-1. And this require a mod 4 = 1. But obviously l — 1 mod 2 = 1. This means we can't get f(x) = 011111... So here answer is also r or r+1 depending on parity of r.

https://mirror.codeforces.com/contest/1493/submission/109287327

Problem — D Please tell me, where I am getting wrong. I have used a segment tree to solve this problem.

Thanks in advance!

spike1236

Your solution is wrong, because you can't just take modulo. For example, if $$$n=2$$$ and $$$a[1] = a[2] = 2*10^5$$$, for query $$$i=1$$$ and $$$x=2*10^{5}$$$, you will multiply first number of array by $$$2*10^{5}$$$ and take modulo $$$10^{9}+7$$$, that's wrong, because $$$gcd(4*10^{10} \, mod \, (10^{9}+7),\, 2*10^{5}) = 1$$$ is not equal to $$$gcd(4*10^{10},\, 2*10^{5}) = 2*10^{5}$$$.

rananjay23

Could someone please tell why my submission in problem D giving TLE , I have used same idea as given in editorial . 109312305 .

Edit : I figured out , i was making mistake in calculating the sieve.

dryice

Can someone explain why does the solution given in editorial for D does not exceed memory limit? In the multiset cnt, every i from 2 to maxn can be of size n, therefore memory required will be O(n^2), which will be too much. Am I missing something?

CSQ31

the number of prime factors of n is bounded by $$$O(logn)$$$ ,each number can only increase the size of cnt by $$$logn$$$ ,in total you process n numbers from the initial array and q queries so the size of the multiset is bounded by $$$O((n+q)*log(2e5))$$$

ThoughtNerd

Please tell me why I get time limit exceeded with this ?

https://mirror.codeforces.com/contest/1493/submission/109323707

in the update, you run through the divisors of sons every time. but there can be A LOT of them -> from this you get TLE.

George1123

+11

May I ask if there are some problems in problem F's example?

Through the Q & A in the example we can not sure that the matrix is like that...

What if the matrix is

1 2 1 2
1 2 1 2
1 2 1 2

Then the answer will be $$$2 \times 3 = 6$$$ and not $$$2$$$.

+19

Sorry I get it...

The example needn't to prove the matrix is like this

It only needs to let the answers of the asks conform to this matrix...

vish_HItesh01

This contest is very helpful for me and Editorial is also very nice !!

Please help me. Why I get time limit exceeded ?

Submission : https://mirror.codeforces.com/contest/1493/submission/109325566

a.rjput

In question C (K-beautiful strings), I had a doubt in the tutorial statement:

"If sum<suff, then lets increase the amount of occurences of a on suffix by suff−sum."

After adding extra a's, how will it be ensured that the occurance count of 'a' is still divisible by k? Can anyone point what I am missing?

codefforces

Overall length $$$n$$$ is a multiple of $$$k$$$. Every letter appears some multiple of $$$k$$$ times in the the first $$$pref + 1$$$ and the last $$$sum$$$ positions combined (because of the way we are constructing the suffix). Hence the remaining number of positions should also be a multiple of $$$k$$$, which we fill all with as.

indresh_0903

Can someone please tell why my code for C is giving Memory limit exceeded on test case 3 Link to the code: https://mirror.codeforces.com/contest/1493/submission/109341765 I have done according to the logic in editorial.

GOT IT :)

I_AM_RAHIMOV

-63

Fuck you AlFlen. it's one of the badest contest

+35

No need to curse ;(

I can't even see round 705 in your contest list.

Can you elaborate why is that round one of the "badest contest"?

Time_To_Night_Sky

Don't personal attack plz...

jakab922

Could someone give me a hint on why the upper bound on the query count is true for 1493F - Заколдованная матрица given that I use the strategy in the tutorial?

The editorial was updated, now it contains a more accurate upper bound and a quick proof

Thanks!

priyanshugarg219

Can someone clarify the below statement
**__gcd(a, b) % c == __gcd(a % c, b % c) % c** ?

this is generally a wrong statement

askd

Haven't read the editorial's proof of E (because I'm too lazy :D) but I found a simple one which is probably different, so here's a (very) informal proof:

Suppose that $$$n \geq 2$$$ and that we're dealing with the "interesting" case (the most significant $$$1$$$ bit is shared in $$$l$$$ and $$$r$$$.) We can immediately use $$$r$$$ as a lower bound for $$$f(l, r)$$$. Note that we must choose $$$x$$$ and $$$y$$$ with the same parity, or else $$$g(x, y) < r \leq f(l, r)$$$ (because there'd be an even number of most significant bits). Therefore, their binary representations must either be $$$(...1, ...1)$$$ or $$$(...0, ...0)$$$.

In the first case, all of the bits in $$$g(x, y)$$$, except the least significant one, are the same as those in $$$x$$$ (by a symmetry argument).

In the second case, all of the bits in $$$g(x, y)$$$, except the least significant one, are the same as those in $$$y$$$ (by a similar argument).

In either case, the substring consisting of these bits in $$$g(x, y)$$$ is lexicographically smaller than or equal to the same substring in $$$r$$$. Therefore, we can always set these bits in $$$x$$$ or $$$y$$$ (depending on case) to be equal to those bits in $$$r$$$ (let's call an assignment of $$$x$$$ and $$$y$$$ which satisfies this as the bruh condition). So what's left is determining if we can make the one bit of $$$g(x, y)$$$ to be on or not.

If $$$r$$$ is odd, we can make it on by setting $$$x = y = r$$$ (this is definitely maximal because it satisfies the bruh condition and has the one bit set).

If $$$r$$$ is even, we must set $$$y = r$$$, or else the bruh condition wouldn't be satisfied. If possible, setting $$$x = r - 2$$$ is maximal because of the same reason as the odd $$$r$$$ case. Otherwise, it's easy to see that setting $$$x = y = r$$$ is the best we can do.

newhar

← Rev. 5 →

Thanks.

I don't understand all of the non-one bits at first, but soon i got the key ideas and solved it. My explanation of the proof:

If both $$$x$$$ and $$$y$$$ are odd ($$$...1$$$), then all of the bits(except the least significant bit) in $$$g(x,y)$$$ are the same as $$$x$$$, so $$$g(x,y) = [x-1, x]$$$. That's because $$$g(x,y) = x \oplus (x+1 \oplus x+2) \oplus (x+3 \oplus x+4) \dots$$$ and all of the bits(except the last bit) in $$$(x+2k-1,x+2k)$$$ are the same.
If both $$$x$$$ and $$$y$$$ are even ($$$...0$$$), then all of the bits(except the least significant bit) in $$$g(x,y)$$$ are the same as $$$y$$$, so $$$g(x,y) = [y, y+1]$$$. The proof is similar.

So for every $$$y$$$, the maximal value of $$$g(x,y)$$$ is $$$y$$$ (if $$$y$$$ is odd) or $$$y+1$$$ (if $$$y$$$ is even).

If $$$r$$$ is even and $$$r - l \geq 2$$$, then the answer is $$$r + 1$$$, and it's the maximal possible answer;
Otherwise, the answer is $$$r$$$, because $$$\max(g(\dots,r)) = r$$$(because $$$r$$$ is odd or $$$r - l < 2$$$) and $$$\max(g(\dots,l\sim r-1)) \leq r$$$.

ah, despite my best efforts, I now realize that "all of the non-one bits" was terribly phrased LOL

glad that that actually helped someone tho!

zjs22

Great proof and explanation! Thank you.

Sandip_Jana

Never thought passing an ArrayList to a function can be taking so much time. Costed me TLE and hell lot of time to debug

https://mirror.codeforces.com/contest/1493/submission/109385847 — AC

https://mirror.codeforces.com/contest/1493/submission/109362908 — TLE

just instead of passing Arraylist passed the same array

towrist

Another (easier?) way to prove E: note that $$$4k \oplus 4k+1 \oplus 4k+2 \oplus 4k+3$$$ is $$$0$$$. So there are atmost 6 "alive" terms in XOR of any range (a prefix of length atmost $$$3$$$ and a suffix of length atmost $$$3$$$ ).

Your 4 paragraph proof of E comes down to two lines if you just observe this fact :P

mitty_nanachi

Shock! A Candidate Master rank 8000+ but gained +77 rating points and became MASTER!!1

Standings , and you can see rating changes => LYC_music's Profile

Need I to @ Mike ?

Magic_Moon

Because these two competitors cheated in this contest and the rating have not rolled back yet.

Pub

+30

Maybe it will roll back soon...?

After four days. I think it's a bug in website, or website maintainer forget to change rating.

__Watcher

I think cheating people's ratings should be lower instead of just cancel the rating changes of this contest.

almeidaraul

Can someone explain to me why (in the solution for problem C) the suffix receives a letter a until it has the appropriate size? Couldn't that make the number of occurrences of a not divisible by k?

motorcycle

As n and (pref + 1 + suff) are both multiples of k, the difference n — (pref + 1 + suff) is also multiple of k, so fill the gap with these additional pref 'a' won't influence the correctness.