ShivanshJ's blog

By ShivanshJ, history, 2 weeks 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
  • +93
  • Vote: I do not like it

»
2 weeks 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).

»
2 weeks 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).

»
2 weeks 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).

»
2 weeks ago, # |
  Vote: I like it -45 Vote: I do not like it

lol didn't read

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

The time complexity allowed for problem C is too high

  • »
    »
    2 weeks 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.

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

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

      • »
        »
        »
        »
        2 weeks 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.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it -17 Vote: I do not like it

      Why should n*sqrt(A) pass as n up to 1e5 and max A up to 1e5.It overall become something (1e4 * 1e5 *1e2.5)=1e11.5. My submission just pass 190040942. Of oder n*sqrt(A). Due this Iam not able to do even after have some idea.

      Edit: My reading mistake!!

      • »
        »
        »
        »
        2 weeks 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.

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

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

      • »
        »
        »
        »
        2 weeks 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)$$$.

        • »
          »
          »
          »
          »
          2 weeks 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.

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

      You are right, n*sqrt(A) should pass. :)

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

When systesting?

»
2 weeks 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

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

    Hacked

    • »
      »
      »
      2 weeks 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.

»
2 weeks 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).

»
2 weeks 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

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

    same i dont know why

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

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

    while taking the modulo for the final product of n, n-1 and the modded factorial, you must have taken % after multiplying all three values in the same line. This may result in overflow. Ideally, multiply first two, take modulo, then multiply this result with the third term and take modulo. This will work

  • »
    »
    2 weeks 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.

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

    overflow

»
2 weeks 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

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

    There was an unofficial for 844

  • »
    »
    2 weeks 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

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

      lol, don't assume we have friends.

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

Actually that was the best idea. Hats off boss.

»
2 weeks 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._

»
2 weeks 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.

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

    Lucky! Can you share your idea?

    • »
      »
      »
      2 weeks 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.

»
2 weeks 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).

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

OMG!Lunar New Year's Eve Round(Div.2)

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

can anyone tell me what i did wrong in C?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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?

»
2 weeks 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...

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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 ?

    • »
      »
      »
      2 weeks 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.

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

I found B fun, thanks for the round guys

»
2 weeks 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.

»
2 weeks 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?

  • »
    »
    2 weeks 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.

  • »
    »
    10 days 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.

  • »
    »
    10 days 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.
»
2 weeks 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.

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

I don't know why preset 3 was failing on my B's solution and my solution was correct :(

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

    the answer should've been n*(n-1)*n!, however in your code, you iterate i(1 — n) and add i*(i-1) to answer, which is wrong

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

Super fast editorials (: And very interesting problems.

»
2 weeks 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.

»
2 weeks 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 ?

  • »
    »
    2 weeks 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 :/

    • »
      »
      »
      2 weeks 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 :)

      • »
        »
        »
        »
        2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

video editorial for Chinese:

BiliBili

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

Editorial of B is just awesome.

»
2 weeks 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

  • »
    »
    2 weeks 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.

»
2 weeks 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

»
2 weeks 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.

  • »
    »
    2 weeks 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)).

»
2 weeks 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?

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

I don't know why I was stuck on E. It was TLE on test 3. But my time complexity was right.

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

I didn't understand the explanation for D.

  • »
    »
    2 weeks 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.

»
2 weeks 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?

»
2 weeks 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)

  • »
    »
    2 weeks 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.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

emordnilap is palindrome backwards.

»
2 weeks 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.

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

Can someone please share the resources to study about expectation and other topics used in task D. Please Help ?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
If the optimal team has students with maximum smartness M and minimum smartness m, would having students with smartness X such that m≤X≤M the answer will not change.

Is it me or the hint should rather read like this:

If the optimal team has students with maximum smartness M and minimum smartness m, would having students with smartness X such that m≤X≤M change the answer?

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

In problem C what does this mean in the 2nd nested for loop

while (curr_count == m)
        {
            ll curr_ans = vec[i].ff - vec[j].ff;
            if (curr_ans < global_ans)
            {
                global_ans = curr_ans;
            }
            for (auto x : factors[vec[j].ff])
            {
                if (x > m)
                    break;
                if (--frequency[x] == 0)
                {
                    curr_count--;
                }
            }
            j++;
        }

It would be a big help if someone explains me this

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

    2nd loop has tow parts.

    1st part: if (x > m) break;. This would be because we only care about divisors upto m. The divisors > m don't affect our question or answer.

    2nd part: if (--frequency[x] == 0) curr_count--;. When removing a particular factor, if decreasing it by 1 makes it total count as 0, then that means in current range we have no other numbers, that has that number as a factor, hence total found number of factors i.e curr_count is decreased by 1.

»
2 weeks 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

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

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

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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 :)

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

      How to solve it with standard D&C?

      • »
        »
        »
        »
        13 days 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

        • »
          »
          »
          »
          »
          13 days 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.

          • »
            »
            »
            »
            »
            »
            13 days 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?

            • »
              »
              »
              »
              »
              »
              »
              13 days 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.

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

Can't we just say that problem B is an Ad Hoc problem? Because if we draw permutations for the first 5 N's, we can see that every time, the number of inversions for all permutations are same, and if we think a little bit, we can represent the number of inversions with n * (n — 1), and that is it!

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

Can problem C be solved using binary search(Optimization problem) as we have to minimise the maximum difference here?

»
2 weeks 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.

»
13 days 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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was about to write the same; did you get any answers ???

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What E(F(A)) means?