A — Indirect Sort

Authors: mejiamejia, Ecrade_

B — Maximum Substring

Author: tibinyte

C — Complementary XOR

Author: tibinyte

D — Count GCD

Author: tibinyte

E — Bracket Cost

Author: tibinyte

F — Majority

Author: tibinyte

Challenge: Solve the problem in or ( modulo is prime )

G — Doping

Author: tibinyte

H — BinaryStringForces

Author: tibinyte

#LeafTON

• 16 hours ago, # ^ | Omg green editorial

  • 16 hours ago, # ^ | omg green editorial

    • 16 hours ago, # ^ | omg green editorial

      • 16 hours ago, # ^ | break the chain

  • 16 hours ago, # ^ | Omg green editorial

• 16 hours ago, # ^ | ← Rev. 2 →   0 can you explain more that how you got ans for merged string str1+str2 from answers of str1 and str2 and t1 t2 m1 m2 ,ok that answer of this string is |m| + max(0,t) but how to get answers of all substrings that pass from the concatenation point of str1 and str2

  • 16 hours ago, # ^ | ← Rev. 2 →   +4 Balance of the concatenation is just the sum of their balances. And minimum prefix balance is either in the left half, in which case it's or in the right half, in which case it's . You just pick the minimum. To compute contribution, note and: Sort right half by ; For each possible , find first such that ; For elements to the right of it, contribution is and to the left it's . To compute contribution, note and: Sort right half by ; For each possible , find first such that ; For elements to the right of it, contribution is and to the left it's . Actual contributions then may be computed with prefix sums. My sol is 179624832. Now that I think about it, my complexity is actually because of sorting... Though one could've used counting sort instead.

    • 16 hours ago, # ^ | got you ORZzz!!!

• 17 hours ago, # ^ | ← Rev. 4 →   +4 Let the prime factors of a[i - 1]/a[i] be p1, p2, ..., pk. The goal is to compute the number of numbers in range [1, m / a[i]] such that they are not divisible by any of pi. To do this, let A_i be the set of numbers in range [1, m / a[i]] such that they are divisible by pi. We can apply PIE on all A_i to find the total number of in-range numbers that are divisible by some pi. m / a[i] minus this number is the desired result

  • 16 hours ago, # ^ | Thanks! I missed the point the total number of possible pi is small.....

• 5 hours ago, # ^ | Video Solution for Problem D Hint:

• 15 hours ago, # ^ | ← Rev. 2 →   +7 I really couldn't make all the tasks about binary strings, but that was the intention... I was inspired by antontrygubO_o's xor contest idea on codechef.

• 16 hours ago, # ^ | nvm I'm dumb

  • 16 hours ago, # ^ | could you please c's logic i'm finding it hard to understand

    • 12 hours ago, # ^ | Notice that every operation can be inverted, so you just need to move to a case where it is trivial to check if it is possible

    • 10 hours ago, # ^ | Video Solution for Problem C. Hint:

• 16 hours ago, # ^ | Hint1 Hint2 Tutorial Solution

  • 3 hours ago, # ^ | why you are doing l++ when flag1 is true

• 16 hours ago, # ^ | Your testcase is wrong, because you check in the very beginning, that divides And since every next number divides the previous one, then you'll need to factor a number except 1 only at most times. So we can limit the complexity to . And an even better limit would come from the fact that the product of all the numbers we decompose is , and the fact that gives us the total complexity of

  • 16 hours ago, # ^ | Thanks for the clarification.

  • 12 hours ago, # ^ | This is not true, for example, for :

    • 12 hours ago, # ^ | ← Rev. 2 →   +5 Well, you got me there It works only for numbers starting from 4 I guess you wouldn't have a problem factoring numbers 1, 2 and 3 in

• 16 hours ago, # ^ | The condition A[i-1] % A[i] != 0 handles that

• 108 minutes ago, # ^ | ← Rev. 2 →   0 I generated primes for the first element and going forward from a[i — 1] to a[i] deleted the primes that are not present in a[i]. But it was not needed.

• 16 hours ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 16 hours ago, # ^ | I care!

    • 16 hours ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 16 hours ago, # ^ | i care too

    • 15 hours ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 15 hours ago, # ^ | I also care!

    • 15 hours ago, # ^ | No one cares. blue_princess

      • 5 hours ago, # ^ | I care!

        • 5 minutes ago, # ^ | No one cares. blue_priness

• 16 hours ago, # ^ | Because you have out-of-bounds in line int pos[n]; for(int i=0;i<n;i++) pos[a[i]] = i; That leads to undefined behaviour so program can output arbitrary data.

  • 4 hours ago, # ^ | Ohh that's why after deleting this line my code got accepted. Thank you.

• 16 hours ago, # ^ | when you find that ans is zero( v[i-1]/v[i] is not integer ) you can break,but if you don't the value of v[i-1]/v[i] keeps jumping ex 1 1000000000 1 1000000000 1 1000000000 1 1000000000... so so your actual complexity is now N*sqrt(m) instead of sqrt(m)

  • 16 hours ago, # ^ | Damnn I often don't break out of laziness basically. Terrible mistake. Thanks for your time!

• 15 hours ago, # ^ | Otherwise you'd be able to precalculate the answer and submit a solution with an array of size 5000.

• 15 hours ago, # ^ | You can precalculate answer with some slow solution with constant

• 15 hours ago, # ^ | I can share what I did, it may be a bit complicated. So, let's divide all of our sequences into two types of groups — positive and negative. (positive have balance > 0, negative — <= 0) For a bracket sequence b, let's call P the absolute value of the minimum prefix balance that is achieved in it (ex, for )(()) it is 1) I claim that the cost for making a permutation good is P for negative BS's and P + balance for positives. How to prove? Let us prove at the start that for a bracket sequence with balance = 0 the cost is P. Let's take first P opening brackets and rotate them to the start — that is the construction. And given that one operation increases a given prefix value by no more than 1, this proves that less than P is impossible. Now, for positive BS's you always need at least BAL closing brackets, which you simply append (the optimality of this is trivial), and then you need P rotations. For negatives — we simply assign the required opening brackets to the start and repeat the proof. Now, you can either simply code this approach (two ST's + deque, my submission = https://codeforces.com/contest/1750/submission/179686679), or you could reorder the formula some more and get the author's one.

• 13 hours ago, # ^ | Maybe this will be easier: You can see that this will be true after every operation, so if we make every , then will hold for every i and j

  • 4 hours ago, # ^ | Great idea!! I had never thought in this way...

  • 3 hours ago, # ^ | bashkort Can you explain how to further approach the solution after this observation?

    • 2 hours ago, # ^ | If initially there are i, j such as , then answer is clearly NO, because if we could make a's and b's equal to zero, then there were no i, j such as . After we made every , then every or every , so if b's are equal to zero, then we solved the problem, or if every b is equal to 1, then we do 3 operations: (1, 1), (2, 2), (1, 2)

• 13 hours ago, # ^ | I updated some stuff in the editorial. Does it make more sense now ?

• 12 hours ago, # ^ | ← Rev. 2 →   0 Let be the number of sequences of size whose maximum electrifiable prefix is of size . For example, , corresponding to any sequence starting with , and is the solution to our problem. Also note that . To calculate for we use a recursive formula. Such a sequence is made by a electrifiable sequence of length followed by either all zeros or enough zeros then a one. In the second case, there are at least zeros before the one, where is the maximum electrifiable prefix of the subsegment starting at the one. Thus, if is the length of that subsegment, we have , where is any amount of extra zeros in that segment. For each satisfying we have a set of sequences of size . Since we can determine in terms of and (having fixed and ), the sets given by every pair are disjoint because they either have a different number of zeros before the one or a second fully electrifiable subsegment of different size. The condition is equivalent to . Thus, the formula is To compute the sum we can something similar to 2d prefix sums but for a triangle instead of a square. Code: Submission

  • 12 hours ago, # ^ | I really like the name "electrifiable" :))

• 12 hours ago, # ^ | ← Rev. 4 →   +52 If somebody still does't understand the solution for F, I hope this would be helpful. Let's fix a binary string (assuming that the first and the last elements are ones). And let's imagine that wile we can make the following operation we make it. Of course it's always good for us. Then let's look to the final string: It looks like . When this string could actually be final (i.e. we can't make any operation)? It's not hard to see that must holds. And it's not hard to see that if it holds then it's not possible to make an operation. Let be the answer for the length . Then if we know and then for how many strings this string will be final? Answer: . Let's call it contribution of the final string. Let be the sum of contributions over all final strings of length , such that (there're zeroes in the final string). Then (cause as we said we only consider strings that starts and ends with one). To calculate we can write the following dp: let be the sum of contributions over all final strings of length that ends with zero and we can insert at most ones to it's end so it still would be final. can be negative, but . Note that in this dp we only consider strings that ends with zero and starts with one. To calculate there're following transitions: += . Here we insert one zero to the end. For all such that balance : += . Here we just insert to the end. If we knew we could calculate this in , because there're transitions of the first type and for second transitions we can fix and use suffix sums to make them fast. Final step: to calculate we need to know only for . And if for all we've already calculated then we can calculate . To do this we need to iterate over the number of ones in the end of the final string and using the same suffix sums update . Knowing we can calculate . So we can calculate and at the same time. Total time complexity: . Code

• 9 hours ago, # ^ | consider a[i-1]=2*2*3 and the current b[i]=2*3*7. Then a[i]=gcd(a[i-1],b[i]) = 2*3 since 2*3 is their common factors. That mean that prime factors(a[i]) should be a subset of prime factors(a[i-1]) and this mean that a[i-1]%a[i]==0.

  • 3 hours ago, # ^ | Thank you! It was actually obvious from the associative property of the GCD. I have misread the problem.

• 7 hours ago, # ^ | Problem C is a bad problem, u know.

• 4 hours ago, # ^ | For the answer to be 'YES', the necessary and sufficient condition is that the XOR of a[i] and b[i] for every i from 1 to n, must be equal. It is not that a[i] has to be different from b[i].

• 6 hours ago, # ^ | Note that the problem input is a permutation

  • 5 hours ago, # ^ | Thanks and I forgot the permutation, for my bad english. Have a good day buddy!

• 2 hours ago, # ^ | Java scans and prints stuff very slowly, maybe scanner from here will be helpful for you 114016483