Good Round! Thanks for the fast editorial!

My Solution for D:

Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.

Otherwise,Let's construct the solution.

First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.

How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).

This is actually a problem of solving congruence equations:$$$(2^{key}-1)+2^{key}X=0(mod\space d)$$$,use exgcd to get such $$$X$$$.

Problem D can also be solved using Chinese Remainder Theorem. First step is the same as stated in solution given above: proccess cases, when answer is -1, and then you can just find X, s.t. X = a|b (mod 2^30), and X = 0 (mod d'). Where d' comes from d = 2^i * d', where d' is odd. The answer is under 2^60, since 2^30*d < 2^30*2^30 = 2^60

I think the problem b was difficult than usual.

Huge gap between A and B.

Problem A is so dumb, just look at it, a lot of people did it under 1 minute, which is time to read the statement alone. Its enough just to go to test cases and see the STUPID pattern

I had the O(100*n) solution for B TLE: https://codeforces.me/contest/1748/submission/180630056 How come?

E is easy but I have no time :(

use cartesian-tree and dp.

is it possible to solve B in python 3 , I see no accepted solutions. would be greatly appreciated if someone can help me with it. thanks

Wow so fast tutorials .Great Contest .Problems were great . Thank u :)

I dont know why I'm experiencing a TLE for this code on my last pretest for problem C T_T any idea??

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    s = 0
    res = 0
    flag = 0
    d = {}
    maxi = 0
    for i in arr:
        s += i
        if flag == 0 and s == 0 and i != 0:
            res += 1
        if i == 0 and flag == 0:
            d[s] = 1
            flag = 1
            maxi = 1
        elif i == 0 and flag:
            res += maxi
            s = 0
            d = {}
            d[0] = 1
            maxi = 1
        elif flag:
            if s in d:
                d[s] += 1
            else:
                d[s] = 1
            if d[s] > maxi:
                maxi = d[s]
    res += maxi
    print(res)

Really nice round. I had guessed that if $$$min(lsb(a), lsb(b)) < lsb(d)$$$, it might be impossible in problem D but can't prove it. Could someone provide a proof of why that is always true?

Am I the only one who stupidly used Euler's Theorem to find inverse modulo in D?

Can anyone explain me why am I getting TLE in Problem C here's my code https://codeforces.me/contest/1748/submission/180659944

My solution for B: for each i such that 1<=i<=n we find for each possible number of distinct elements what is the range L,R where this occurs. Then for each range we check where is the first index j such that the subarray [i,j] is bad, and subract R-j+1 from all possible subarrays. Time complexity is O(100nlogn) because we can find the ranges and check for bad subarrays using binary search. You can check my code to understand more

Thanks for the fast editorial. I quite liked problems A-C. However, on problem D I feel like there should have been a constraint that D is a prime that is not 2. Because most of the ideas from D still apply, but finding the modular inverse is much easier. Or it could have also been split into an easier and harder version, with the easier one having D as a prime. I feel that C-D gap was quite large.

can anyone please explain problem B...

I cant solve b during contest, but still I think that it was a nice problem

I think my solution for D is somewhat simpler (at least for me) to understand:

First, it is impossible if the (where $$$lsb$$$ is the least significant bit) $$$lsb(a) \leq lsb(d)$$$ or $$$lsb(b) \leq lsb(d)$$$ because we are trying to find an $$$x$$$ such that $$$a|x$$$ and $$$b|x$$$ are both multiples of $$$d$$$. When we multiply a number $$$h$$$ by another $$$k$$$ and look at the result in binary, the result is the sum of multiplying the first by each of the bits of the second, which would imply that $$$lsb(h*k) \geq lsb(h)$$$ and $$$lsb(h*k) \geq lsb(k)$$$.

After we figure this out and deal with that case, the rest is easy. First lets say $$$m_i$$$ is the $$$i_{th}$$$ bit of $$$m$$$. We want to find a multiple of $$$d$$$ (lets call it $$$k$$$) where there is no bit $$$i$$$ such that $$$x_i=1$$$ and $$$k_i=0$$$. If we find this then all we need to do is apply a bitwise OR to $$$x$$$ in order to make $$$x=k$$$. This is always possible through the following algorithm:

Lets make $$$x=a|b$$$ and $$$k=d$$$ initally, then we iterate through the bits of both,

If $$$x_i=k_i$$$ then we can can ignore this bit.

If $$$x_i=1$$$ and $$$k_i=0$$$ we can left shift $$$d$$$ some number of times until the $$$lsb(d)$$$ is at the $$$i_{th}$$$ bit and then add this to $$$k$$$. This would not change any of the bits that we have already iterated over, would maintain that $$$k$$$ is a multiple of $$$d$$$, and would make $$$k_i=1$$$.

Now, there is no bit $$$i$$$ where $$$x_i=1$$$ and $$$k_i=0$$$, so we can just make $$$x = k$$$ by making $$$x=x|k$$$

Im pretty sure this is a naive solution compared to one using a single eqution but still I enjoyed coming up with it and think it is a little easier to understand.

In problem F the number of operations can be improved from $$$\frac{3}{2} m^2 + O(m)$$$ to $$$\frac{5}{4} m^2 + O(m)$$$.

Similarly to $$$f(i, j)$$$ in the editorial we can define $$$g(i, j, l)$$$ as a sequence of operations that performs xor-assignments $$$a_i = a_i \oplus a_{j+l-1}$$$, $$$a_{i+1} = a_{i+1} \oplus a_{j+l-2}$$$, ..., $$$a_{i+l-1} = a_{i+l-1} \oplus a_{j}$$$, where indices are cyclic modulo $$$n$$$ and cyclic segments $$$[i, i + l - 1]$$$ and $$$[j, j + l - 1]$$$ do not intersect. This sequence is the same as $$$f(i, j + l)$$$ when $$$l \equiv j - i$$$ and otherwise ends with 3 passes between $$$i + l - 1$$$ and $$$j$$$ to clean up the mess. Defining $$$h(i, j, l)$$$ as a sequence of operations that reverse-swaps such two segments, $$$h(i, j, l) = g(i, j, l) \mathbin\Vert g(j, i, l) \mathbin\Vert g(i, j, l)$$$, $$$\frac{3}{2} m^2$$$ solution is $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$.

But we don't have to drag $$$a_{n-1}$$$ through the whole array to get to $$$a_0$$$. Essentially instead of $$$swap(a_0, a_{n-1})$$$ we can perform $$$swap(a_{n-1}, a_0)$$$, then we replace two long passes and one short with two short passes and one long. Instead of $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$ we split both segments, reverse-swap one pair though the middle of the array and the other through the ends. For example, taking $$$x = \lfloor\frac{n}{2}\rfloor$$$, $$$y = \lceil\frac{x}{2}\rceil$$$: $$$h(n - y, 0, y) \mathbin\Vert h(y, n - x, x - y)$$$.

Hint 2 for problme D: Combined with the first hint, we can say that a triplet (a,b,d) has no solutions if min(lsb(a),lsb(b))<lsb(d). Here, lsb(x) represents the least significant bit of x.

Does this mean that if a and b are even and d is odd then it should have no solution but test case 7 of the example have a solution?

I use unordered_map in C, and I get TLE.

I keep getting a "wrong" judgement on my Kotlin code even though I followed the example solution to a tee. Any hints?

import kotlin.math.max
import kotlin.math.min

fun main() {
    val t = readLine()!!.toInt()
    (1..t).forEach {
        readLine()
        val s = readLine()!!

        var result = 0L

        (0..s.length-1).forEach outer@ { fro ->
            // count how often each digit 0..9 has occurred so far
            val numOccur = MutableList(10) { 0 }

            // only substrings of length <= 100 can be diverse, otherwise maxOccur >= 11 is forced
            val maxTo = min(fro+1 + 100, s.length)
            var diversity = 0
            var maxOccur = 0

            (fro+1..maxTo).forEach inner@ { to ->
                val idx = s[to - 1] - '0'
                numOccur[idx] += 1

                // no matter what chars we add, it can never be diverse anymore
                // note that this also makes the above length-100 condition obsolete
                if (numOccur[idx] > 10)
                    return@inner

                diversity += if (numOccur[idx] == 1) 1 else 0
                maxOccur = max(maxOccur, numOccur[idx])

                result += if (diversity >= maxOccur) 1 else 0
            }
        }
        println(result)
    }
}

I'm not sure I'm right or not, but const number can't exist in $$$O()$$$(except $$$1$$$).

The number of operations are $$$n\times10^2$$$ but you can't say that the time complexity is $$$O(n\times10^2)$$$,maybe.

And of course it is easy to understand, but I suggest to fix it due to rigour.

If I'm wrong please figure out thx.

https://codeforces.me/contest/1748/submission/180639586#

wa on #516th ... any help?

I finally became Master after this round. Thank you for the interesting problems.

I feel like there's an error in editorial of problem C. It should be added $$$[s_{i_1}, s_{i_1 + 1}, \cdots, s_{i_2 - 1}]$$$ in between $$$[s_1, s_2, \cdots, s_{i_1 - 1}]$$$ and $$$[s_{i_2}, s_{i_2 + 1}, \cdots, s_{i_3 - 1}]$$$. Of course, it does not really matter, the pattern is obvious, I was just pointing it out.

I have a stupid and complicated solution for B https://codeforces.me/contest/1748/submission/180642025 time complexity O(n logn)

I think the sample of D is a big hint. During the competition, I tried to convert the output of the last example into binary and found that the last 30 digits are all 1s, so I could find the solution. I think if the sample set the last 30 digits to be a|b, I must not be able to solve it.

how to solve d with exgcd（Extended Euclidean algorithm）?

Have someone else solved C by dp?

so my question is:

why https://codeforces.me/contest/1748/submission/180728658 this works and https://codeforces.me/contest/1748/submission/180728780 does not?

the only difference is that in #1 I go from n-1 to 0 and #2 I go from 0 to n-1

This's a great round... and my first round in CF :)

can someone explain the dp solution for qC?

Can anyone explain why in problem "C — Zero Sum Prefixes" is c++ std::map (my test) more preferable than std::unordered_map (my time limit test)?

Always thought that std::unordered_map should give constant time on all required operations but std::map — logarithmic. sorry for the newbie question.

I participated from an alt but wanted to offer my feedback on the problems.

A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked

B — also alright

C — not very interesting, this problem does not need to exist

D — weird definition of an integer, this problem does not need to exist

E — annoying, this problem does not need to exist

F — incredibly annoying, I don't like this problem at all, i won't even try to solve it

Am o problema mai calitativa:

Dandu se un sir de operanzi cifre si operator ^ * | & ~ XOR + — / ** ! oplus, gasiti valoarea maxima a expresiei facand maximum k interschimbari.

Marinush

I participated from an alt but wanted to offer my feedback on the problems. A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked B — also alright C — not very interesting, this problem does not need to exist D — weird definition of an integer, this problem does not need to exist E — annoying, this problem does not need to exist F — incredibly annoying, I don't like this problem at all, i won't even try to solve it I have another solution for F: Bagi bulaneala pe vectori

At Codeforces Round #833 (Div. 2)

There is a case of cheating in the problem B A solution is available during the contest on YouTube https://youtu.be/0x9kKxfqLr8

Matching solutions:- https://codeforces.me/contest/1748/submission/180650292

https://codeforces.me/contest/1748/submission/180650184

https://codeforces.me/contest/1748/submission/180649269

https://codeforces.me/contest/1748/submission/180646072

https://codeforces.me/contest/1748/submission/180646346

https://codeforces.me/contest/1748/submission/180646263

https://codeforces.me/contest/1748/submission/180646094

https://codeforces.me/contest/1748/submission/180645940

For problem D, how can we say for sure that $$$x$$$ will be of the form: $$$p11..11(30 - k \ times)00..00(k \ times)$$$

In problem D: How can we prove that $$$x_{(2)}=p 1 1 1 … 1 0 0 … 0$$$ is divisible by both a and b? Please, help!

The data structure, described in the editorial for problem E, is called Cartesian tree. One can build it in O(N).

How come in Problem B, not using ~~~~~ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ~~~~~ gives AC 181109995 but using this in code gives WA 181109865

I came up with a different solution to problem E but it is not working (even on the first test case). I can't figure out what is wrong with my approach. I have described the idea below.

Observation

a[i] >= a[i + 1] implies b[i] >= b[i + 1]

a[i] < a[i + 1] implies b[i] < b[i + 1]

dp state: dp[i][j] = number of arrays with b[i] = j

// base case
for j: 1 ... m
    dp[1][j] = 1;

// transition
for i: 2 ... n
    for j: 1 ... m
        if(a[i - 1] >= a[i]) // then b[i - 1] must be greater than j as per observation
            for k: j ... m
                dp[i][j] += dp[i - 1][k]
        else
            for k: 1 ... j - 1 // then b[i - 1] must be lesser than j as per observation
                dp[i][j] += dp[i - 1][k]

Below is a link to my submission with actual code (which optimizes the above pseudocode using a prefix sum array.

181409754

In problem D, there's this step in the explanation

$$$p+1 ≡ (2^{−1})^{30−k} \mod d' ⇔ p+1 ≡ (\frac{d'+1}{2}) ^ {30−k} \mod d'$$$

I don't understand where it comes from, like what property is being used or why this is done, can anybody help me please?

Why is my same code getting accepted in GNU G++17 7.3.0 and not in GNU G++20 11.2.0 (64 bit, winlibs) ? What's the difference between these two languages? GNU G++17 7.3.0 — 186674226 GNU G++20 11.2.0 (64 bit, winlibs) — 186674279

For problem B, can anyone help me understand why this 188673953 is AC, but this 188673213 is WA?

The AC one is simply starting from ans=0 and doing ans++ for each diverse substring. The WA one is the opposite. It starts with ans=(n*(n+1))/2 and doing ans-- for each non-diverse substring.

In C can it happen that maximum frequency prefix of the subarray is such that for nullifying that prefix our ai exeeds the limit of 1e9 ?

D is such a nice problem man but there is something that I found very unintuitive about it and that is — why you filled all the digits before p and after k to be one. I mean the best thing I could arrive at after solving this problem for hours was that rather than filling up all of them with ones as you did I would fill it with a^b and I reched nowhere.

Is there a flow-based solution for Problem E?

Hard Div2 ?