When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ShivanshJ's blog

By ShivanshJ, history, 14 months ago, In English

We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments.


1777A - Everybody Likes Good Arrays!

Idea: ShivanshJ
Preparation: ShivanshJ
Editorialist: ShivanshJ

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

1777B - Emordnilap

Idea: TimeWarp101 quantau
Preparation: TimeWarp101
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

1777C - Quiz Master

Idea: quantau
Preparation: TimeWarp101 quantau
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Feedback

1777D - Score of a Tree

Idea: AwakeAnay
Preparation: mayankfrost ShivanshJ
Editorialist: AwakeAnay

Hints
Solution
Implementation (C++)
Feedback

1777E - Edge Reverse

Idea: Crocuta
Preparation: mayankfrost
Editorialist: mayankfrost

Hints
Solution
Implementation (C++)
Feedback

1777F - Comfortably Numb

Idea: Crocuta
Preparation: TimeWarp101
Editorialist: Crocuta

Hints
Solution
Implementation (C++)
Feedback
  • Vote: I like it
  • +98
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).

»
14 months ago, # |
  Vote: I like it -45 Vote: I do not like it

lol didn't read

»
14 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The time complexity allowed for problem C is too high

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

    We had initially thought of keeping it tighter but after some discussions we decided that it wont be be a good idea to let $$$n * \sqrt[2]{A}$$$ not pass, but $$$n * \sqrt[3]{A}$$$ pass.

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

      how to achieve O(n*A^(1/3))?

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

        The maximum factors of a number $$$A$$$ are bounded by $$$\sqrt[3]{A}$$$. Discussion for the same.

        Using some precalculation methods you can store factors for all possible smartness values as $$$n$$$ was capped at $$$10^5$$$. Refer the implementation for the same.

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

          thanks!

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

          I do not quite understand this, are you saying that it is possible to enumerate all factors in $$$^3\sqrt{x}$$$ time? Can you tell how?

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 5   Vote: I like it -17 Vote: I do not like it

      [DELETED]

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

        The statement clearly say that:

        It is guaranteed that the sum of n over all test cases does not exceed 10^5.

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

      I passed with time complexity $$$O(n\log n \sqrt A)$$$.

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

        I used Segment Tree and passed with time complexity $$$O(128 n \log m)$$$.

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

          Same, shouldn't have passed, code breaks an test

          1

          100000 100000

          83160 100000 times

          They just didn't include that test, which allowed many wrong submissions to pass, not only segtrees, but also some people used maps, which results in same complexity.

          It is posible to fit this code in TL, the person's above code runs in 2550ms, mine in 2170 ms (without I/O), so with small bit optimizations on segtree I got 2022ms (also without I/O), if improved more, this should pass.

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

When systesting?

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

The TL on F is stupidly high, a simple $$$O(n^2)$$$ passed: 190000292

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

    Hacked

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

      Optimized it, I wanna know if you could hack this one: 190039238

      Also I think it's kind of wrong that people started downvoting my comment, me being hacked doesn't change the fact that TL is absurdly big when only $$$O(nlognlogA)$$$ was intended in the first place.

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

Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).

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

idk why i was stuck on B. I knew the final product needed for the answer, but it was failing pretest 3

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

    same i dont know why

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

      If you change n and m to long long it works, i guess because you are combining long long and int you should go for all long long but I´m not completely sure.

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

        it worked thanks,I read 10^5 as 10^4 in the range of n and tested 10^4 and thought declaring m long long shouldn't be a problem fm.

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

    I had the same problem as you. When n = 10^5, n*(n-1) overflows an integer. So n also has to be a long long.

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The editorial of #845 is earlier than #844

Or there will be no editorial of #844

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

    Oh please stop spamming everywhere, You have commented in most of the blogs in recrnt months, Instead of spamming go and find some friends to talk with them

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

      lol, don't assume we have friends.

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

In problem A,you could just simply check consecutive elements whether they were even or odd.The count of consecutive even or odd pairs or both would be the result._

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My solve for C barely passed, 1996 ms. Thought I had to binary search for length.

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

    Lucky! Can you share your idea?

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

      Similar to the solve in the tutorial, I kept a frequency of how many factors appeared and I binary searched to what length to keep it. If the length is greater than the series, it fails.

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

Any advice on How to master number theory..I Struck in "C" today.(How to think in the mathematical sense for the problem).

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

can anyone tell me what i did wrong in C?

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

    Bro,You have to minimize the answer.Which you have notdone.

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

      I have sorted the smartness array in reverse, so the answer is the maximum value possible for each number,how can i further minimize it?

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

I managed to hack my own code after the contest, feels bad to get accepted after this...

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

A good Spring Festival gift, but a stupid me. ):

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

It's such a pity that I watched the Spring Festival Gala and failed to solve E in time.

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

In E instead of topological sort, you can just check the in degree of each scc. If there are more than one scc with in degree == 0 then graph is not reachable.

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

    I'm not sure if I got your point right, but I guess you're saying that if there's more than one node with indegree equal to zero in the scc graph, then there is no answer, if so consider the following test:

    3 2

    1 2 1

    3 2 2

    you can make node one reach every node by reversing the second edge (3 2 2) could you clarify a bit more ?

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

      No I was talking about the routine inside binary search. You make all edges with weights less than or equal to mid double sided. Then you make SCC and if there are more than one nodes with in degree 0 then not possible for that value of mid.

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

There is a right bracket missing in the solution of Problem D. The location is just as the picture shows.

»
14 months ago, # |
  Vote: I like it +14 Vote: I do not like it

In the contest I wrote such an algorithm below for F: for every index I,find the interval that a_i can be the largest element in any subarray of it,which can be solved simply in O(n) complexity. Then just calculate the answer for every I using 01trie.The total complexity is O($\sum len(interval)$log n). If the value of a_i are distinct,the complexity is O(nlogn),which is acceptable.However,if there are same elements---for example a_i are same for every I,the complexity would be O(n^2) or higher.

However,the algorithm passed both the pretest and the system test.Isn't the data too weak?

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

    This algorithm could be improved by finding the interval that a_i is the leftest largest element in any subarray.

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

    I don't understand. Won't that be O(n^2) even when the elements are distinct. Like, consider when the given array is in sorted order.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • 190017681 is $$$O(n^2)$$$ (and not $$$O(n*logn)$$$ even if even if all elements are distinct.
    Simple testcase
    • It's easy to make all elements distinct, just change $$$a_i$$$ integer to $$$(a_i,i)$$$ tuple, although it won't help in this case.
»
14 months ago, # |
Rev. 4   Vote: I like it +32 Vote: I do not like it

To my attitude , it's too standard. If you understand Chinese (or use translation softwares), you can see that the last two problems are just constructed with some standard algorithms(E: https://www.luogu.com.cn/problem/P3387 and F: https://www.luogu.com.cn/problem/P4735) . The fact that they weren't as hard as usual caused the ranking to seem a little strange. And I think if you replace E or F with harder or more interesting problems, then this round will be much better.

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Super fast editorials (: And very interesting problems.

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

Am I correct in saying the complexity of my solution for C is $$$O(a \ln m \cdot \ln(a \ln m) + m)$$$? It TLEs in 190006029 when I just use $$$a = 10^5$$$ but passes in 190008245 when I use compute up to the max $$$a_i$$$ from the input.

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

I thought about a harder version of problem D during the contest —

At any integer time t>0 , the value of a node becomes the bitwise XOR of the values of all children (all nodes below it) at time t−1.

How to solve this ?

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

    I'm guessing that the solution would be the exact same. That the node would have a value of 1 approximately half the time. Not sure though :/

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

      well you could look at it this way that, let say the grandchildren becomes zero, it means they don't affect the children and we go back to the same case as was mentioned in the original question. Now another case is that the value of grandchildren matters , but you can see that the great grand children will become zero 1 step before, leaving children's value to be dependant on the grandchildren only and not the nodes below that. This way we can conclude that the answer would not change and probability of 0 or 1 will still remain (1/2).

      Correct me if I am wrong :)

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

        I mean, I'm not sure it's EXACTLY the same. You mentioned that after the leaves become 0, the parents of the leaves won't be affected. But if you look at the root of the tree for example, it will still have to deal with the XORs of a lot more values than in the original problem. However I'm pretty sure that the answer would still stay the same, b/c I doubt that the #of descendants that affect the current node matters.

»
14 months ago, # |
  Vote: I like it +19 Vote: I do not like it

video editorial for Chinese:

BiliBili

»
14 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

In problem E we don't even need to check for toposort in SCC, we just need to check the count of indegree, there should be only one element whose indegree should be zero in the SCC

if there are no elements (you graph is not DAG)

and if there are more than one, than you can't reach from one of the elements to other

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

    Yes. You are right. The editorial is a little off. What we meant was you don't need to do the complete SCC algorithm. You can just do a toposort on the graph (which is the first part of SCC algo). If you think about it,the first node in this sorted list will be the one belonging to a 0-degree SCC. So, you can just check the reachability of all other nodes from the first node.

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

Can someone please tell me what is the mistake in my code of problem C https://codeforces.com/contest/1777/submission/190077492

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

how can one can generalize this statement "We will focus on computing the expected value of F(A) rather than the sum, as the sum is just 2n×E(F(A))" from editorial of question d.

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

    Each initial situation has chance of p(A)=1/2^n to appear, so E(F(A))=sum(F(A)*p(A))=sum(F(A)/2^n)=(1/2^n)*sum(F(A)).

»
14 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

F can be solved with the standard D&C in less than 1s. why is the TL 8s?

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

I didn't understand the explanation for D.

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

    Jumping off someone else's comment, the idea is that if we let V(node, time) be the sum of all the possible values of this node over all initial positions, then V(node, time) is equal to 2^n-1 for all nodes and times(except when we hit a time such that the value of the node is guaranteed to become 0). This is b/c we can expect each node to have a value of 1 approximately half the time. This is kind of intuitive to see, but you might need to do some examples to prove this to yourself. So in order to calculate the sum of all ideal V's, we need another observation. At time 1, the problem states that the leaves of the tree will become 0. This effect will actually cascade upwards. So if a node i has a height of k_i (the distance from the node to the farthest leaf that's a descendant), then that means that it will have a 50% chance to be a 1 for exactly k_i times, before becoming a 0 for the rest of eternity. So the solution is to sum up all the values of k_i and multiply that sum with 2^n-1.

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

In problem D, the way $$$V_u(A,t)$$$ is defined (that is, value of node u is bitwise xor of all nodes at distance t from u) is not at all true for t=1, or many instances of time, for ex:

Did I do something wrong or there is something wrong in the editorial?

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

I didn't understand how we calculate expected value of k boolean nodes in problem D, can someone explain in simpler)

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

    Expected value = C(k, odd) / (C(k, odd) + C(k, even)). It's a well known fact that C(k, odd) = C(k, even) with k > 0.

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

I approached Problem C: Quiz Master in the following way:

Let $$$pos_x$$$ store all numbers $$$num$$$ (present in given sequence $$$A$$$) such that $$$num$$$ is divisible by $$$x$$$. Also make $$$pos_i$$$ is sorted for each $$$1 \leq i \leq m$$$.

If $$$pos_i$$$ is empty for any $$$i$$$ then our answer is $$$-1$$$ else it is just a variation of this problem Smallest range in K lists.

Smallest range in K lists

Here is my submission.

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

emordnilap is palindrome backwards.

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

For B. Emordnilap, wouldn't you have to set ans to a long long (c++ solution)? N goes up to 10^5 and n * (n-1) would most definitely be past the ranges of an int. an int goes to about 2 billion (2^9 or to be exact 2147483647), and multiplying would be out of the range. Please tell me if I'm wrong.

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

For Problem F, the editorial solution gives Memory Limit Exceeded on test 84. https://codeforces.com/contest/1777/submission/190232289

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

    Can someone please tell me where have I got it wrong?

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

    That's because you submitted it in a 64 bit compiler. Pointers are 8 bytes in 64 bit compilers and 4 bytes in 32 bit compilers. The solution will pass if you submit it in a 32 bit compiler (like GNU G++17). But it takes double the memory in 64 bit compilers and therefore MLEs.

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Suggestion for people having TLE on F even though they implemented the optimal solution: Make sure you use a structure like a segment tree or sparse table to find the maximum in the interval you are solving. Or alternatively, pass it when returning recursion. Do not iterate through the entire interval as I did as that can take up to $$$O(N^2)$$$ time, because d&c does not divide in half each time.

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

    Or they could just do the standard D&C which divides in half :)

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

      How to solve it with standard D&C?

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

        For a segment $$$[l;r]$$$ let $$$m={(l+r)\over 2}$$$.

        The optimal answer is either in the left, right or both parts. For the left and right parts solve recursively.

        Now, if the answer lies in the both parts. Assume that a segment $$$[L;R]$$$ such that $$$L \le m \lt R$$$ is the optimal answer.

        $$$max(a_L,...,a_R)$$$ lies either in the $$$[L;m]$$$ (left part) or $$$[m+1;R]$$$ (right part).

        Let's assume that it's in the right part. We will use two pointers. Initially, $$$L=m$$$ and $$$R=m+1$$$

        Assume that the right end of the answer is $$$R$$$. We already know the maximum element $$$mxR$$$ and xor $$$xrR$$$ of the right part.

        We have the right part of the answer, but we are missing the left one. How do we find it fast such that it would be the optimal one?

        We assumed that the maximum element in the optimal answer lies in the right part. It means that each segment $$$[L;m]$$$ such that $$$max(a_L,...,a_m) \le mxR$$$ combined with the right part could be the optimal answer.

        Create a trie for xor.

        While $$$max(a_L,...,a_m) \le mxR$$$, add $$$xor(a_L,...,a_m)$$$ to the trie, and decrease $$$L$$$.

        When you can't move $$$L$$$ anymore, get the best number $$$xrL$$$ from the trie to maximize $$$mxR ⊕ xrR ⊕ xrL$$$ and update the answer.

        When you are done, repeat the process for the left part(as if the max would be in there).

        submission

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

          I think that I understand your solution. It seems like O(N^2), but it actually has O(N log A) armortized complexity per division. Thank you for sharing.

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

            The complexity is $$$O(nlogn * logn)$$$.

            Btw, why does it look like an $$$O(n^2)$$$ algo? It is absolutely the same as the standard D&C with an additional log from the trie?

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

              I mean the solution which first comes to mind seems like you would need to do $$$O(N^2)$$$, because of keeping maximum and stuff. (Like, going through all possible right and left borders) But actually, it's enough to move one border and move the other one only when necessary by fixing on which side maximum is.

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

problem B was just super good.Idea of solving it is just amazing.

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

It's a bit too much talking about SCCs and kosaraju for E when in the end it just comes down to topologically sorting the uncondensed graph to find an appropriate candidate. But knowing how to think it terms of SSCs does help in this kind of problem.

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

    No, you need to do topological sort on the condensed graph.

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

      If what you call the condensed graph is the one with nodes being SCCs, then you definitely don't. you can check my submission for example. I use binary search. To verify a given cost $$$c$$$, I consider the graph with reverse edges only if $$$c \leq w$$$. I only topo sort then do a dfs on the untransformed graph starting from the top/root node i get. This is because topo sort guarantees that if the "root" node can't reach another node, then this node can't reach the root node either.

      Of course it's true for whatever node $$$n_i$$$ that appears before node $$$n_j$$$ in the topological sorting.

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

        That’s an interesting solution. I didn’t think that you can do that. However, I believe that the SCC solution is actually straightforward for most people.

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

Hey I find this Round has become unrated.Does anyone know why?

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

What E(F(A)) means?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't understand why they prefer to put something like calculating things about $$$max(a_l,\cdots,a_r)$$$ to the last problem. You can solve most of this kind of problem using divide and conquer, or play dsu on cartesian tree. It's very typical and you can see many similar solutions in other problems about min max. With this trick, I figured out F in ten minutes with E still unsolved. (Actually I worked on D for 40 minutes after the contest) I also passed an Ex in ABC easily with this idea.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@TimeWarp101

In problem C,

why sorting is gonna help?