tibinyte's blog

By tibinyte, 2 years ago, In English

A — Indirect Sort

Authors: mejiamejia, Ecrade_

Solution
Code (Ecrade_)
Rate Problem

B — Maximum Substring

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

C — Complementary XOR

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

D — Count GCD

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

E — Bracket Cost

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

F — Majority

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

Challenge: Solve the problem in $$$O(nlog^2)$$$ or $$$O(nlog)$$$ ( modulo is prime )

Solution

G — Doping

Author: tibinyte

Solution
Solution 2
Code (tibinyte)
Rate Problem

H — BinaryStringForces

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

#LeafTON

  • Vote: I like it
  • +253
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The Solution code is not revealed

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

tibinyte orz

»
2 years ago, # |
  Vote: I like it +128 Vote: I do not like it

omg green editorial

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great contest! Seems like the editorial was prepared before the contest :D
tibinyte orz

»
2 years ago, # |
Rev. 2   Vote: I like it +76 Vote: I do not like it

I use divide and conquer to solve E. Assume that ( is $$$+1$$$ and ) is $$$-1$$$. Let $$$t$$$ be the total balance of the string and let $$$m \leq 0$$$ be the minimum prefix balance of the string. Then there are two main observations:

  1. Cost of making the string balanced is $$$|m| + \max(0, t)$$$;
  2. Concatenation of strings $$$(t_1; m_1)$$$ and $$$(t_2; m_2)$$$ yields $$$(t_1 + t_2; \min(m_1, t_1 + m_2))$$$.

Using this, we may just compute sum of $$$|m|$$$ and of $$$\max(0, t)$$$ for every sub-string separately by splitting a string in two equal halves, computing answers on them recursively and then computing answers for strings passing the middle point by sorting prefixes of right half by $$$t_2$$$ and by $$$m_2$$$, and by using some prefix sums on them.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      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 $$$m_1$$$ or in the right half, in which case it's $$$t_1 + m_2$$$. You just pick the minimum.

      To compute $$$\max(0, t)$$$ contribution, note $$$t = t_1 + t_2$$$ and:

      1. Sort right half by $$$t_2$$$;
      2. For each possible $$$t_1$$$, find first $$$t_2$$$ such that $$$t_1 + t_2 \geq 0$$$;
      3. For elements to the right of it, contribution is $$$t_1 + t_2$$$ and to the left it's $$$0$$$.

      To compute $$$|m|$$$ contribution, note $$$m = \min(m_1, t_1 + m_2)$$$ and:

      1. Sort right half by $$$m_2$$$;
      2. For each possible $$$m_1$$$, find first $$$m_2$$$ such that $$$m_2 \geq m_1 - t_1$$$;
      3. For elements to the right of it, contribution is $$$|m_1|$$$ and to the left it's $$$|m_2 + t_1|$$$.

      Actual contributions then may be computed with prefix sums. My sol is 179624832. Now that I think about it, my complexity is actually $$$O(n \log^2 n)$$$ because of sorting... Though one could've used counting sort instead.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand the part $$$max(0, t)$$$ clearly.

    I mean to destroy the part $$$t \geq 0$$$, we just put the ')' at the end $$$t$$$ times. To destroy the $$$|m|$$$, we do the cyclic shift.

    But I don't know what will happen when $$$t < 0$$$.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      When $$$t < 0$$$, we put $$$|t|$$$ of ( in the beginning. It will reduce $$$m$$$ by $$$t$$$ and we will do $$$|m| - |t|$$$ cyclic shifts to get rid of remaining imbalance, making it a total of $$$|m|$$$ operations.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain in problem D, how to use the inclusion-exclusion principle to find the count of numbers in range [1, m / a[i]] that are co-prime to a[i — 1] / a[i] ?

That's essentially what we are trying to do for each i, right? To find out the count of numbers that are co-prime to a given number x in a given range starting from 1.

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Video Solution for Problem D

    Hint:
    • »
      »
      »
      22 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thanks. Very helpful. Can you suggest some good resources for Inclusion exclusion and combinatorics? + How to master the number theory problem?

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

First BinaryStringForces round on codeforces.com

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem statements were short and quite simple to understand. No unnecessary stories. Thank you.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The unneccessary stories were the best part :,(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Quickest Tutorial Ever, WOW!

Good Job boys ..

»
2 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

My solution for D is similar but instead of factorizing a1, I use the fact that a[i]/a[i+1] is amortized:

We notice that b[0] = a[0] and let's look for transition from b[i] to b[i+1]:

Exist a number b[i+1] s.t. it is possible to do the i -> i+1 transition <=> gcd(a[i], a[i+1]) = a[i+1]

b[i] must fulfill that gcd(a[i], b[i+1]) = a[i+1] <=> b[i+1] € {x s.t. gcd(x/a[i+1], a[i]/a[i+1]) = 1 and a[i+1]|x and x <= m}

Those are the number of co-primes numbers of a[i]/a[i+1] in range [0, (m/a[i+1])]

To get the number of co-primes number of a[i]/a[i+1] in range m/a[i], we can go through the factorization of a[i]/a[i+1], keep unique primes in a vector, let's call it "decomposition", and then go through all the 2^(|decomposition|) subsets with inclusion-exclusion to get the number of non-co-primes numbers of a[i]/a[i+1]. (we get the number of multiples of every subset of decomposition by (m/a[i]) / LCM(subset) and add it or subtract depending on the parity of the cardinal of the subset (this comes from inclusion-exclusion)).

Considering 2 sqrt(m)/logm the number of primes in [2, sqrt(m)] we get this is O(n*(2 sqrt(m)/logm) + sqrt(m)log(m)), but it turns out that a[i]/a[i+1] is amortized and then (2 sqrt(m)/logm) is a constant, so we get O(n + sqrt(m)logm).

Sorry for not using LaTex, I should definitely learn LaTex

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "add it or subtract depending on the parity of the cardinal of the subset (this comes from inclusion-exclusion))." Can u please elaborate more on this part?

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In problem C if all elements of both arrays are equal to 1, the editorial solution will do 2*n operations , right?

wasn't it suppose to make at most n+5?

or am I mistaking something?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nvm I'm dumb

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you please c's logic i'm finding it hard to understand

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Video Solution for Problem C.

        Hint:
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I want to plug my solution for Problem E here which does not use a BIT, just prefix sum, a map (which couldve been a vector, but I was too lazy for negative indices...) and two for-loops.

Solution: 179633595

Explanation: Link to comment in Announcement.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain C logic .

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Hint1
    Hint2
    Tutorial
    Solution
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I am generating the prime factors of all the numbers but it is not giving me a TLE.

Example:

$$$n = 2$$$x$$$10^{5}$$$

$$$arr = [10^9, 1, 10^9, 1, 10^9,....]$$$

Then isn't the time complexity $$$O(10^5$$$ x $$$\sqrt{10^9})$$$ and won't this give TLE?

179686581

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Your testcase is wrong, because you check in the very beginning, that $$$a_i$$$ divides $$$a_{i-1}$$$

    And since every next number divides the previous one, then you'll need to factor a number except 1 only at most $$$log(10^9)$$$ times. So we can limit the complexity to $$$O(n) + O(log(10^9)\sqrt{10^9})$$$. And an even better limit would come from the fact that the product of all the numbers we decompose is $$$a_1$$$, and the fact that $$$\sqrt{a\cdot b\cdot c ...} \geq \sqrt{a} + \sqrt{b} + ...$$$ gives us the total complexity of $$$O(n)+O(\sqrt{10^9})$$$

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the clarification.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Why $$$\sqrt{a \cdot b \cdot c \cdot ...} \geq \sqrt{a} + \sqrt{b} + ...$$$?

      This is not true, for example, for $$$a = b = 2$$$ : $$$\sqrt{4} < 2 \sqrt{2}$$$

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +16 Vote: I do not like it

        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 $$$O(1)$$$

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell why this solution 249691884 does not give tle, even thought tc is

      $$${O}({n}*{2^9}*{9}+\sqrt{m})$$$
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Well, why wouldn't it? $$$n \cdot 2^9 \cdot 9 \approx 4E8$$$. Given that C++ speed is around $$$1E9$$$ simple operations per second, 400ms sounds just about right.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Isn't $$$10^8$$$ operations fesible in one second in C++ . Also since sum of n over all test cases is bounded by $$$2\cdot10^5$$$ , so $$$n\cdot2^9\cdot9$$$ should be $$$\approx 9E8$$$ .

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The condition A[i-1] % A[i] != 0 handles that

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Okay I'm a bit annoyed (and it certainly is my fault) that I FST'd Problem D and once again (yes, previous times also I was reaching Master and then FST'd) I have to wait to touch that yellow colour again.

What was the mistake?

At this point, it seems like my fate doesn't want me to reach master again :(

Anyways, it was a great contest! A big thank you to everyone involved in the problem setting team. (Although I believe C was a bit harder than usual :P)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the runtime complexity of problem D wrong ? Not sure what is the log in 2^9 * 9 * log + sqrt(M). Shouldn't it be 2^9 * 9 * N + sqrt(M) per test case, where N is the length of the input array A's length per test case ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are at most $$$LogN$$$ factors of a Number , so $$$a[i]/a[i+1]$$$ can yield a value not equal to 1 only $$$LogN$$$ times , The correct time complexity is $$$O(N+2^9*9*LogN + M )$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this solution of the first problem didn't get accepted?? Solution: 179614121

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Ohh that's why after deleting this line my code got accepted. Thank you.

»
2 years ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

Myself, after seeing the solution code for C: The hell is the purpose for making a Problem C with a 67-line intended solution code?

UPD: Saw the code for H. 500 lines. I swear THERE IS NO DAMN WAY SOMEONE COULD TYPE THAT DURING THE CONTEST.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    You can obviously tell my coding style is shit. Live with it.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Omg you added dollar sign to count strings from 1...

      You should not be allowed to write editorials

      (jk, great contest)

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problems Were really nice :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The links in your blogpost are a bit weird, since clicking on the caption "A -- Indirect Sort" sends you to Problem B :) But it is a great contest and editorial!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D- Why does this submission https://codeforces.me/contest/1750/submission/179652391 give TLE?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Damnn I often don't break out of laziness basically. Terrible mistake. Thanks for your time!

»
2 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

What was the point of setting non constant $$$mod$$$ in problem F? I had a very funny bug in my non-static $$$mod$$$ template. I forgot that the $$$mod$$$ isn't always prime, so for calculating $$$a$$$ to the power of $$$b$$$ I took $$$b$$$ modulo $$$mod - 1$$$. And due to the small constraints on $$$mod$$$ I didn't find $$$2^n$$$ correctly and didn't get accepted ;)

Anyway the problem was good in my opinion, and would be better with the constant $$$mod$$$.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Otherwise you'd be able to precalculate the answer and submit a solution with an array of size 5000.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    You can precalculate answer with some slow solution with constant $$$mod$$$

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    There's a new trend to set problems with variable mod without an explicit reason just because "why not, it might help with something that we don't know".

    Or so I've been noticing. Not the case in this problem, but I've seen it happening at least twice.

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to make observations such as "The cost of s[l + 1, r] is max(bl, br) — min(bl, ..., br)?"
Really bad at binary strings or balanced sequence stuff.. Can someone please share what is the intuition/strategy for those problems?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.me/contest/1750/submission/179686679), or you could reorder the formula some more and get the author's one.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

A tough contest that ended my positive delta streak for 10 rounds, however it was well prepared and I learnt a lot, Thanks. Orz tibinyte

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In editorial of C, "For each operation, the interval changed by a sequence and b sequence is complementary, so you must judge whether all [ai=bi] are the same at the beginning."

Can someone explain in more detail?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Maybe this will be easier:

    You can see that this

    $$$a_i {\oplus} a_j = b_i {\oplus} b_j$$$

    will be true after every operation, so if we make every $$$a_i = 0$$$, then $$$b_i = b_j$$$ will hold for every i and j

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bashkort Can you explain how to further approach the solution after this observation?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If initially there are i, j such as $$$a_i \oplus a_j \neq b_i \oplus b_j$$$, 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 $$$a_i \oplus a_j \neq b_i \oplus b_j$$$.

        After we made every $$$a_i = 0$$$, then every $$$b_i = 0$$$ or every $$$b_i = 1$$$, 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)

»
2 years ago, # |
  Vote: I like it +89 Vote: I do not like it

Can someone explain the solution to the problem F properly?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I updated some stuff in the editorial. Does it make more sense now ?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    Let $$$dp_{ij}$$$ be the number of sequences of size $$$i$$$ whose maximum electrifiable prefix is of size $$$j$$$. For example, $$$dp_{i0} = 2^{i-1}$$$, corresponding to any sequence starting with $$$0$$$, and $$$dp_{nn}$$$ is the solution to our problem. Also note that $$$dp_{ii} = 2^i - \sum_{j \in [0, i)} dp_{ij}$$$.

    To calculate $$$dp_{ij}$$$ for $$$0 < j < i$$$ we use a recursive formula. Such a sequence is made by a electrifiable sequence of length $$$j$$$ followed by either all zeros or enough zeros then a one. In the second case, there are at least $$$j + 1 + b$$$ zeros before the one, where $$$b$$$ is the maximum electrifiable prefix of the subsegment starting at the one. Thus, if $$$a$$$ is the length of that subsegment, we have $$$j + j + 1 + s + b + a = i$$$, where $$$s \ge 0$$$ is any amount of extra zeros in that segment. For each $$$a,b,s$$$ satisfying $$$a + b + s = i - 2j - 1$$$ we have a set of sequences of size $$$dp_{jj} \cdot dp_{ab}$$$. Since we can determine $$$s$$$ in terms of $$$a$$$ and $$$b$$$ (having fixed $$$i$$$ and $$$j$$$), the sets given by every pair $$$(a, b)$$$ 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 $$$a + b + s = i - 2j - 1$$$ is equivalent to $$$a + b \le i - 2j - 1$$$. Thus, the formula is

    $$$ dp_{ij} = dp_{jj} \left(1 + \sum_{a + b < i - 2j} dp_{ab}\right).$$$

    To compute the sum we can something similar to 2d prefix sums but for a triangle instead of a square.

    Code: Submission

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I really like the name "electrifiable" :))

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ajutaţi-l pe Jolteon să determine câte subsecvenţe electrizante are şirul pe care l-a primit.

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it +105 Vote: I do not like it

    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 $$$\underbrace{1\ldots 1}_{a_0} \underbrace{0\ldots 0}_{b_0} \ldots \underbrace{1\ldots1}_{a_k}$$$. When this string could actually be final (i.e. we can't make any operation)? It's not hard to see that $$$b_i > a_i + a_{i + 1}$$$ must holds. And it's not hard to see that if it holds then it's not possible to make an operation.

    Let $$$dp_n$$$ be the answer for the length $$$n$$$. Then if we know $$$a_i$$$ and $$$b_i$$$ then for how many strings this string will be final? Answer: $$$\prod\limits_{i = 1}^{k}{dp_{a_i}}$$$. Let's call it contribution of the final string.

    Let $$$bad_n$$$ be the sum of contributions over all final strings of length $$$n$$$, such that $$$k > 1$$$ (there're zeroes in the final string). Then $$$dp_n = 2^{n - 2} - bad_n$$$ (cause as we said we only consider strings that starts and ends with one).

    To calculate $$$bad_n$$$ we can write the following dp: let $$$q_{n,\text{ }balance}$$$ be the sum of contributions over all final strings of length $$$n$$$ that ends with zero and we can insert at most $$$balance$$$ ones to it's end so it still would be final. $$$balance$$$ can be negative, but $$$balance \in [-n, n]$$$.

    Note that in this dp we only consider strings that ends with zero and starts with one.

    To calculate $$$q$$$ there're following transitions:

    1. $$$q_{n,\text{ }balance}$$$ += $$$q_{n - 1,\text{ }balance - 1}$$$. Here we insert one zero to the end.

    2. For all $$$1 \le m$$$ such that balance $$$balance \ge m$$$: $$$q_{n,\text{ }-m}$$$ += $$$q_{n - m - 1,\text{ }balance} \cdot dp_m$$$. Here we just insert $$$\underbrace{1\ldots1}_{m}0$$$ to the end.

    If we knew $$$dp_n$$$ we could calculate this in $$$O(n^2)$$$, because there're $$$O(n^2)$$$ transitions of the first type and for second transitions we can fix $$$m$$$ and use suffix sums to make them fast.

    Final step: to calculate $$$q_{n,\text{ }balance}$$$ we need to know only $$$dp_i$$$ for $$$i < n$$$. And if for all $$$balance$$$ we've already calculated $$$q_{n,\text{ }balance}$$$ then we can calculate $$$bad_n$$$. 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 $$$bad_n$$$. Knowing $$$bad_n$$$ we can calculate $$$dp_n$$$. So we can calculate $$$dp$$$ and $$$q$$$ at the same time.

    Total time complexity: $$$O(n^2)$$$. Code

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why in problem D, a[i-1] has to be divisible with a[i]?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D ,I used inclusion-exclusion principle but why my code gives wrong answer in test 3 in the sample cases?

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In problem C. Why does a[i] have to be different from b[i]?

In test case:

2

10

01

Is not a valid solution:

1

1 1 ?

»
2 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

The solution of problem B can be better by the count of 0 = n — count of 1

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can you tell me why when $$$b[l] > b[r]$$$ respect then we can just use right bracket at the end of string?

In case of $$$()(())))))($$$,1-Index,let $$$l=3, r=11$$$. It's easy to see that $$$b[l] = 1,b[r] = -2$$$ 。But we should do operation 1 one time,and add two left bracket on the left. If we just work as the edtorial, we can make the last bracket be matched.

Sorry for my bad English. But can anyone teach me? Thank you very much.

»
2 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

For E, you don't need to use BIT to calculate the answer, you can split it into two parts (I concatenated 0 to the start of prefix sums)
$$$\sum_{l=0}^{n} \sum_{r=l+1}^{n} max(b_l, b_r) - min(b_{l..r}) \;=\; \sum_{l=0}^{n} \sum_{r=l+1}^{n} max(b_l, b_r) \;-\; \sum_{l=0}^{n} \sum_{r=l+1}^{n} min(b_{l..r})$$$

Which is just sum of max over all pairs in array (which you can calculate by sorting) minus the sum of minimums for all subarrays (which you can calculate using contribution technique and stacks(next and previous smaller element))
Submission Link

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why problem 2 gave TLE for same approach written in Java. I have done both work in one for loop , still it gave me TLE.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Java scans and prints stuff very slowly, maybe scanner from here will be helpful for you

    114016483

»
2 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

How to solve F in $$$\mathrm{O}(n * polylog)$$$ time ?$

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think we can ask errorgorn to share the orz $$$O(nlog)$$$, since I only know the $$$O(nlog^2)$$$ solution.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 4   Vote: I like it +34 Vote: I do not like it

      Let's say we know $$$ans[1,n]$$$. We will demonstrate how to find $$$ans[1,2n]$$$ in $$$O(n \log n)$$$.

      Same as editorial we want to count number of bad configs of form $$$\texttt{1}^{a_1} \texttt{0}^{b_1} \texttt{1}^{a_2} \ldots \texttt{0}^{b_{k}} \texttt{1}^{a_{k+1}}$$$. Where $$$b_i > a_{i}+a_{i+1}$$$. Also, the contribution of term $$$\texttt{1}^{a_i}$$$ is $$$ans[a_i]$$$. For bad string of length $$$2n+3$$$, the maximal $$$a_i$$$ we need is $$$n$$$ for the string of form $$$\texttt{1}^{n} \texttt{0}^{n+2} \texttt{1}^{1}$$$. So knowing $$$ans[1,n]$$$ is sufficient to find $$$ans[1,2n]$$$.

      We can use genfuncs to calculate this value. Imagine the string instead as $$$(\texttt{1}^{a_1}\texttt{0}^{a_1} \texttt{0}^{b_1}) (\texttt{0}^{a_2}\texttt{1}^{a_2}\texttt{0}^{a_2} \texttt{0}^{b_2}) \ldots (\texttt{0}^{a_k}\texttt{1}^{a_k}\texttt{0}^{a_k} \texttt{0}^{b_k}) (\texttt{0}^{a_{k+1}}\texttt{1}^{a_{k+1}})$$$. Where instead of $$$b_i > a_{i}+a_{i+1}$$$, the conditions are $$$b_i>0$$$ instead. It is easy to find OGF of first, middle and last terms which we denote $$$A(x),B(x),C(x)$$$. Then bad configs of length $$$n$$$ is $$$[x^n] A(x) (1+B(x)+B(x)^2+\ldots)C(x) = [x^n] \frac{A(x)C(x)}{1-B(x)}$$$. All these operations can be done in $$$O(n \log n)$$$.

      Code: 180044094 (sorry for cringe FFT, it was hacked together from here and here).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain for C :

Observe that answer is only possible if both the string is the same or if we can get b after inverting each character of a.

How this stataement is true , i not able to understand

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Every operation flips the Boolean values of all a[i] == b[i] together, and the final goal requires all a[i] == b[i] to be true. So the initial values of a[i] == b[i] must be all true or all false.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can hardly understand the editorial for Problem G.

Can anybody explain it in a more detailed way?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Added a second solution. The model uses this idea.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my implementation of E. It uses the same idea as the official solution, but only requires an std::set instead of a BIT.

By inserting the indices to a set in sorted order of prefix sum, we can find the possible starting and ending points of a segment whose minimum is located at each index. The other part of the summation is easier to deal with; simply count how many times each element is the maximum of a pair.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

BIT seems very handy but I don't understand some parts of code in editorial. Can anyone explain how to use BIT to count Max and Min in Problem E?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually, we can solve E in O(n) instead of O(n log n). 179627446 this is my solution for the problem. Now we can see that we can replace maps with arrays, because all keys in first map are from -n to n, and from 0 to n in the second one.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone help with my code for C- Complementary Sort?

https://codeforces.me/contest/1750/submission/179955063

It gives me WA because for some line at test 3, l = 0 and it is out of bounds. I have checked and that is not true. Any clue?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the complexity of solution D? For each adjacent element we have to generate the power set of primes also. So It'll be around 2^10 . for each adjacent element 2^10 would be a lot. I get the thing that there won't be much 2^10 as the primes will exhaust very fast. But can anyone prove it mathematically? Like for the factorisation part we can get an amortised analysis. Similarly for power set generation how to get amortised analysis?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It took me a while to understand the solution for C. The problem is interesting though.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give an insight as to why the same code TLEs in C, yet passes comfortably in C++?

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Alsalam Alykom,My solution for A,B is skipped and i swear i didn't use ideone or another account or anything its my clear solution ! I swear to god i didn't cheat why something like that happen to me ? how to avoid this MikeMirzayanov tibinyte

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For me, A was harder than B. I don't know why.