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

1777B - Emordnilap

Idea: TimeWarp101 quantau
Preparation: TimeWarp101
Editorialist: TimeWarp101

1777C - Quiz Master

Idea: quantau
Preparation: TimeWarp101 quantau
Editorialist: TimeWarp101

1777D - Score of a Tree

Idea: AwakeAnay
Preparation: mayankfrost ShivanshJ
Editorialist: AwakeAnay

1777E - Edge Reverse

Idea: Crocuta
Preparation: mayankfrost
Editorialist: mayankfrost

1777F - Comfortably Numb

Idea: Crocuta
Preparation: TimeWarp101
Editorialist: Crocuta

• 15 months ago, # ^ | 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∗A−−√2n∗A2 not pass, but n∗A−−√3n∗A3 pass.

  • 15 months ago, # ^ | how to achieve O(n*A^(1/3))?

    • 15 months ago, # ^ | The maximum factors of a number AA are bounded by A−−√3A3. Discussion for the same. Using some precalculation methods you can store factors for all possible smartness values as nn was capped at 105105. Refer the implementation for the same.

      • 15 months ago, # ^ | thanks!

      • 11 months ago, # ^ | I do not quite understand this, are you saying that it is possible to enumerate all factors in 3x−−√3x time? Can you tell how?

  • 15 months ago, # ^ | ← Rev. 5 →   -17 [DELETED]

    • 15 months ago, # ^ | The statement clearly say that: It is guaranteed that the sum of n over all test cases does not exceed 10^5.

  • 15 months ago, # ^ | I passed with time complexity O(nlognA−−√)O(nlog⁡nA).

    • 15 months ago, # ^ | I used Segment Tree and passed with time complexity O(128nlogm)O(128nlog⁡m).

      • 15 months ago, # ^ | ← Rev. 3 →   0 Same, shouldn't have passed, code breaks an test 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.

• 15 months ago, # ^ | Hacked

  • 15 months ago, # ^ | 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)O(nlognlogA) was intended in the first place.

    • 15 months ago, # ^ | what does that "tune=native" do ?

• 15 months ago, # ^ | same i dont know why

  • 15 months ago, # ^ | 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.

    • 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 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

  • 15 months ago, # ^ | lol, don't assume we have friends.

• 15 months ago, # ^ | Who asked? There is already the solution above.

• 15 months ago, # ^ | Lucky! Can you share your idea?

  • 15 months ago, # ^ | 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.

• 15 months ago, # ^ | ← Rev. 2 →   0 Bro,You have to minimize the answer.Which you have notdone.

  • 15 months ago, # ^ | 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?

• 15 months ago, # ^ | 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 ?

  • 15 months ago, # ^ | 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.

    • 15 months ago, # ^ | Aha it's clear now. Thanks !

• 15 months ago, # ^ | This algorithm could be improved by finding the interval that a_i is the leftest largest element in any subarray.

• 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 190017681 is O(n2)O(n2) (and not O(n∗logn)O(n∗logn) even if even if all elements are distinct. Simple testcase It's easy to make all elements distinct, just change aiai integer to (ai,i)(ai,i) tuple, although it won't help in this case.

• 15 months ago, # ^ | 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 :/

  • 15 months ago, # ^ | 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 :)

    • 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 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)).

• 15 months ago, # ^ | 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.

• 15 months ago, # ^ | 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.

  • 15 months ago, # ^ | thanks!

• 15 months ago, # ^ | 3rd line of code: #define int long long

• 15 months ago, # ^ | Can someone please tell me where have I got it wrong?

• 15 months ago, # ^ | 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, # ^ | Now I know that 64-bit can be harmful too.

• 15 months ago, # ^ | Or they could just do the standard D&C which divides in half :)

  • 15 months ago, # ^ | How to solve it with standard D&C?

    • 15 months ago, # ^ | For a segment [l;r][l;r] let m=(l+r)2m=(l+r)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][L;R] such that L≤m<RL≤m<R is the optimal answer. max(aL,...,aR)max(aL,...,aR) lies either in the [L;m][L;m] (left part) or [m+1;R][m+1;R] (right part). Let's assume that it's in the right part. We will use two pointers. Initially, L=mL=m and R=m+1R=m+1 Assume that the right end of the answer is RR. We already know the maximum element mxRmxR and xor xrRxrR 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][L;m] such that max(aL,...,am)≤mxRmax(aL,...,am)≤mxR combined with the right part could be the optimal answer. Create a trie for xor. While max(aL,...,am)≤mxRmax(aL,...,am)≤mxR, add xor(aL,...,am)xor(aL,...,am) to the trie, and decrease LL. When you can't move LL anymore, get the best number xrLxrL from the trie to maximize mxR⊕xrR⊕xrLmxR⊕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

      • 15 months ago, # ^ | 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.

        • 15 months ago, # ^ | The complexity is O(nlogn∗logn)O(nlogn∗logn). Btw, why does it look like an O(n2)O(n2) algo? It is absolutely the same as the standard D&C with an additional log from the trie?

          • 15 months ago, # ^ | I mean the solution which first comes to mind seems like you would need to do O(N2)O(N2), 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.

• 15 months ago, # ^ | No, you need to do topological sort on the condensed graph.

  • 15 months ago, # ^ | 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 cc, I consider the graph with reverse edges only if c≤wc≤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 nini that appears before node njnj in the topological sorting.

    • 15 months ago, # ^ | ← Rev. 2 →   +1 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.

• 15 months ago, # ^ | I was about to write the same; did you get any answers ???

  • 14 months ago, # ^ | ← Rev. 2 →   0 Maybe unrated all the time?