Endagorion's blog

Technocup 2020 — Elimination Round 2 + Codeforces Round 596: analysis
By Endagorion, history, 5 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +77
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does 63503240 gives TLE in div2 B2?

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

    t = 1e4 and k = 1e6

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

    Because you are allocating and initializing cnt for every test case, which makes your code O(tk). Check the values of $$$t$$$ and $$$k$$$ in the question — these values will definitely result in a TLE.

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

      Thank you guys. I completely ignored k. Changing array to map does the trick

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

        or you can delete cnt after each query

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

    you can use map,not the ans to index,the ans will TLE

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

    I made the same mistake hah

    I thought about clean cnt with n but I didn't fix it

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I solved D, with a different approach(after contest).
I calculated divisors of $$$x^k$$$ for every $$$x$$$ such that 1 <= $$$x$$$ <= $$$10^5$$$ and $$$x^k$$$ <= $$$1e10$$$.Since $$$x$$$ can be only in range $$$1$$$ to $$$10^5$$$ in worst case, we can calculate the divisors of $$$x^k$$$ using prime factors of $$$x$$$. Caluculating prime factors of $$$x^k$$$ is easy if we know prime factors of $$$x$$$, we just need to multiply power of every particular prime factor by $$$k$$$. Since we know divisors of every $$$x^k$$$ we can easily count pairs such that $$$Ai*Aj$$$ = $$$x^k$$$.

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

    I don't see your "Accepted" for this problem and how would you then calculate the answer not in an at least quadratic time? It doesn't seem like a good solution to me.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      Link to Submission.
      I already mentioned that i solved it after contest.
      Time complexity of my solution is $$$ (\Sigma_{i=1}^{10^5} divisors(i^k)) * C$$$ (let C be some constant) for calculating divisors,and worst case of this approach occurs when k = 2 because in this case we have to calculate divisors of $$$10^5$$$ numbers. When i computed on my pc they were roughly $$$6*10^6$$$ which is not much for a problem with 2 sec TL.

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

        Oh, I thought that I see all your submissions when I go to your profile but apparently I don't. Thanks for the link.

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

          There is an option named "show unofficial".

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

            Thank you! I could have thought about it.

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

        Thanks for your method to calculate divisors. I used a similar overall solution but the only difference was the method in which I tried to calculate divisors. It gave a TLE for $$$k==2$$$ For each x such that $$$ x^k<(10)**10 $$$, I calculated the divisors using $$$O(\sqrt(x))$$$ method. Which apparently miserable fails for $$$k==2$$$ but works fine for all others

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

          Can someone explain why is that giving TLE?

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

    See this for finding divisors using prime factors.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone tell me what is wrong in my coding approach for Power Products(D)

I am sorting the array and using two pointer approach to find possible pairsI

63471990

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

    Check on this Tc:
    5 2
    1 1 1 1 1 It's answer is 10 and yours give 4.

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

      Yeah, I guess because of the repeated numbers two pointers approach won't work. Thanks for checking it out.

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

Has the tutorial not been made or there is some bug.It is showing tutorial not available for problems D-G

Edit:resolved

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

    The analysis is complete, but there is an issue with loading it from Polygon automatically. This usually resolves itself eventually.

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

      It has not been uploading for me for about 30 mins now, could you please resolve it or tell how to resolve the same. Thanks!

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in Problem E what is the best RSQ can be used with a few implementation cause i thought of segment tree so that we have n segment tree of base m and m segment tree of size n but it would be a lot of implementation so what do u think ?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

In problem $$$C$$$, why does $$$n-kp$$$ has to be at least $$$k$$$ can someone please throw some light on it?

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

    Because you’re writing it as sum of k power of 2s which are all bigger than or equal to 1

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    because the number of digits in the binary representation of the max value can be

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please look upon the issue of editorial.It's showing that "Tutorial is not available"

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain how to solve div2E/div1C , in editorial it's not clear about defination of D,R arrays?

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It would be great if someone can explain me easier way solution of div2-C. I cant understand the solution and I,m not so fimiliar with binary numbers, bit cnt etc.

Thanks a lot. :)

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

    Let the minimum number of $$$p$$$-binary numbers required to represent $$$n$$$ be $$$l$$$. We start from $$$l = 1$$$ and increment $$$l$$$, testing its possibility. If it's possible in $$$l$$$ $$$p$$$-binary numbers, then that means that $$$n = (\text{sum of }l\ \text{powers of}\ 2) + lp$$$, because we get a $$$+p$$$ contribution from each of the $$$l$$$ $$$p$$$-binary numbers. So we need to check if $$$n - lp$$$ can be represented as a sum of $$$l$$$ powers of $$$2$$$, not necessarily distinct.

    Now you can represent a number uniquely in any integral base greater than 1. It will result in a unique representation. Now given $$$n - lp$$$, you need at least $$$\lfloor log_2{(n-lp)} \rfloor + 1$$$ bits to represent $$$n$$$, and that is the binary representation of $$$n - lp$$$. So we get one condition that $$$l \geq \lfloor log_2{(n-lp)} \rfloor + 1$$$.

    Consider the example: $$$n-lp = 2^2 = (100)_2$$$. We can write this as $$$2^2 = 2^1 + 2^1 = 2^0 + 2^0 + 2^1 = 2^0 + 2^0 + 2^0 + 2^0$$$ In each subsequent representation we are breaking a power of $$$2$$$ down and adding one term in the representation. This shows us that we can represent $$$2^a$$$ in $$$1$$$ to $$$2^a$$$ terms, therefore we can represent $$$\sum 2^a$$$ in $$$\sum 1$$$ to $$$\sum 2^a$$$ terms. If we choose $$$a$$$ from the binary representation of $$$n - lp$$$, $$$\sum 2^a = n-lp$$$ and $$$\sum 1 = \text{sum of bits in}\ n-lp = \sigma$$$ (say). So $$$l$$$ must satisfy $$$\sigma \leq l \leq n-lp$$$. In GCC, __builtin_popcount(n-lp) can be used that gives the value of $$$\sigma$$$ (sum of bits).

    Now $$$n \leq 10^9$$$ and $$$p = 1000$$$, so number of bits in $$$n-lp$$$ should be the same as that in $$$n$$$. A satisfactory upper bound should be 34. Start from $$$l = 1$$$ to $$$34$$$, and check if $$$\sigma \leq l \leq n-lp$$$; if it's true, then you have your value of $$$l$$$.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

My approach for D:

Let $$$f_{1}$$$ be a function such that $$$f_{1}(a)=b$$$ for $$$1 \le a \le 10^5$$$ where $$$b=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$$$. Here $$$p_{i}$$$ is a prime and $$$c_{i}<k$$$.

Let $$$fr$$$ gives frequency of an element in given array. Hence for $$$1 \le i \le 10^5$$$ do $$$freq[f_{1}(i)]=freq[f_{1}(i)] + fr[i]$$$.

Now, let $$$f_{2}$$$ be a funtion such that $$$f_{2}(a)=b'$$$ where $$$b'=p_{1}^{k-c_{1}}p_{2}^{k-c_{2}}...p_{m}^{k-c_{m}}$$$.

The answer is ans

$$$ ans= \begin{cases} ans \enspace + \enspace freq[f_{1}(i)] \times freq[f_{2}(i)], & \text{if } f_{1}(i) \ne f_{2}(i)\\ ans \enspace + \enspace freq[f_{1}(i)] \times (freq[f_{2}(i)] - 1)/2, & \text{otherwise} \end{cases} $$$

Note: Chech if $$$f_{1}(i)$$$ has already been calculated as $$$f_{1}(i) = f_{1}(j)$$$ for $$$i \ne j$$$.

Link to code

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

Alternative solution to G:

  • Consider the dumb $$$O(N^\alpha 3^N (\sum a_i)^2)$$$ DP solution that just finds numbers that can be made from each subset. It's too slow.
  • Add bitsets. It's still too slow.
  • Consider a different $$$O(N^\alpha 3^N (\sum a_i)^2)$$$ DP solution that goes in the reverse direction and calculates for each subset and number "if we can make this number using this subset, we win". It uses the results of the previous DP, because when we want to make $$$x$$$ (or $$$xK, xK^2, \ldots$$$) using subset $$$i$$$ and we can definitely make $$$y \le x$$$ using a subset $$$j \subset i$$$, then we want to make $$$x-y$$$ using the subset $$$i-j$$$. It's still too slow.
  • Combine these two DPs in a meet-in-the-middle approach. Due to symmetry, we only need to consider cases where the subset $$$j$$$ above is smaller than $$$i-j$$$, or equally large (with some tiebreaker like j < i-j). As soon as we find out that we both can make number $$$j$$$ using subset $$$i$$$ (first DP) and if we make it, we win (second DP), we can stop and use the first DP to construct a solution.
  • The first DP now only needs to consider subsets with size $$$\le N/2$$$. The theoretical bound isn't much better, but in practice, we have much fewer states to consider both because there are less subsets and much fewer numbers to make using small subsets.
  • The second DP only needs to consider the remaining subsets and it will either quickly find a solution or have very few states to process, so it's pretty fast either way. Intuitively:
    • If the first DP finds many numbers, the chance that the second DP also finds many numbers (using those found by the first DP) and therefore that it quickly stumbles upon a solution is high.
    • If the second DP finds few numbers, the first DP will have difficulty forming many numbers we want to make using large subsets. Small subsets should automatically consume little time, since they have fewer subsets and in the split $$$i \rightarrow (j, i-j)$$$ described above, if the sets $$$j$$$ and $$$i-j$$$ are both processed by the first DP, we don't gain any states in the second DP.
    • If $$$i$$$ is large and $$$j$$$ is kinda large, then $$$i-j$$$ is much smaller than $$$i$$$ and we already get a small state. On the other hand, when $$$i$$$ is large and $$$j$$$ is very small, then there are few numbers we can make using the subset $$$j$$$.

Time complexity: 1200 ms.

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

    So someone cheesed this problem after all, huh. Nice job!

    With enough stress-testing I've managed to time out this solution very slightly with this test:

    16 3
2 143 158 16 58 56 161 101 89 100 250 7 334 92 103 251
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      11

      Main observation: the loop "for each set bit in v1, shift v2" allows a massive speedup if v1 has just one set bit, which is very often the case for small subsets. (I already tried your hack.)

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

    Could anyone please explain "dumb" dp? I don't get what is the dp state there.

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

      "Using a subset $$$S$$$ of the given numbers, can we create a number $$$j$$$?" The values of the states are 0/1, there are $$$O(2^N \sum a_i)$$$ of them.

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

        Thanks! How do you end up with $$$N^{\alpha}$$$ in the complexity?

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

          Choose $$$\alpha$$$ arbitrarily. Then, there's always $$$N^\alpha$$$ in any complexity. In this case, it's the exponential and sum that matter, so I didn't bother thinking what $$$\alpha$$$ is.

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I waited for like 10 MINUTES and there was still no editorial. Can anyone who can see the editorial for Div. 1 B to Div. 1 F consider posting the editorial on somewhere else for others' convenience?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE in div2 B2 when contest final consequence came out.But accepted it after contest with exactly the same codes.

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

Is this an alternative solution to problem F(Div. 1)?

Again, solve it backwards.

Consider elements in [L, X] can reach X in no more than K steps. Then, elements in [L', X] can reach X in no more than K + 1 steps, where L' = min_i{pre[i], L <= i <= X} where pre[i] = the last occurance of ch[i] before i(ch[] is the string in the input).

Let's try to fix X. Then, the process above forms a tree structure, and what we need to compute is the sum on the path from X to the root.

Consider how does the tree change when 1 is added to X. The parent of an interval [[the minimal Y such that min{pre[Y...X]} >= pre[X]], X] will be modified to pre[X] while the other vertices of the tree remain unchanged. Put the intervals with the same parent together and we only need basic operations in dynamic trees to fix it.

Use Link Cut Tree or Euler Tour Tree(I'm not sure because I don't know ETT well) to solve the problem in O(n log n).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 C can someone explain the case when P is negative answer for K still won't cross 31

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

    Let $$$p < 0$$$, then the maximum value of $$$n - 31p$$$ will be $$$10^9+31000$$$ which can be represented with 30 binary digits (less than 31). It's obvious that all the numbers less than $$$10^9+31000$$$ can also be represented with no more than 30 binary digits. So $$$k=31$$$ will always be possible.

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

      But whose telling you to stop at 31p for p<0 ,I can still keep on subtracting it

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

        We wish to find the minimum answer. So if we know that surely 31 is a possible answer, then we won't check for numbers greater than 31.

        → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In solution of D there is a small mistake. It is given that 360 = 2^3 * 2^2 *5 but it should be 360 = 2^3 * 3^2 * 5

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could someone give me a elaborated explanation for problem Div2-C. The Edtiorial is so hard to grasp, especially the range of all $$$k$$$ value. Thanks

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it 
    /*
Let x = n-31*p
There are two possibilities: 
1.  x >= 31
2.  x < 31

For the first case, the maximum value of x is (1e9 + 31*1000) < (2^31). So, 31 <= x < 2^31. Hence, x can always be represented as exact 31 powers of 2's. However, there is a possibility that we can achieve the same with fewer. So, just iterate the value of k from 1 to 31 and check for the minimum value.

For the second case, n < 31*(p+1). Since, n>0 and n<31*(p+1) , 31*(p+1) >0 . So, p > -1 or p >=0 (in the editorial there is a mistake, it should be p+1>0 not p+1<0). If (k>31) , -kp < -31p, So,n-k*p < n-31*p < 31 < k. Hence, n-k*p < k (not possible, as it has to be at least k). So, k <= 31.
*/
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much! Excellent Explanation.

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

        But what happen if I let x = n-1e9*p? I am confused that: I want to represent $$$n-kp$$$ not just $$$n-31p$$$.

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

          The given case will come under one of the two cases mentioned

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

          I got it, the reason we don't need a large k like that, we always can find the answer with k < 31.

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

    Hint : How to represent a number as exactly k powers of 2.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does https://mirror.codeforces.com/contest/1225/submission/63542673 give TLE using g++, but works with MSVC???

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

    I just know why the code got TLE using g++. Because there may be 1e5 test case. And for each test case, the value of k can be 1e6. Then the code will run Line 24 1e5*1e6 times. It got TLE here.

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

In case(like me ) you are having a hard time implementing problem D tutorial (DIV 2) here is a implementation of the given approach
https://mirror.codeforces.com/contest/1225/submission/63557938

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain B2 to me..

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

    Think in terms of sliding window u need to count minimum unique elements at a given window and keep sliding window till the end. See my submission

    → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Typo in ur editorial of D -> factorisation of 360 should be 2^3 3^2 5^1 u mistyped 2 in place of 3

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Maybe it will be useful for users who will try to solve this task later. I've found that the following solution passes all authors' tests although it's incorrect: Let's consider DP[N][X][Y] — it is 1, if we can apply such consequence of operations to N-length prefix of an array so that last two numbers are X and Y, and 0 if we can't. Then DP[2][A[1]][A[2]] = DP[2][A[2]][A[1]] = 1, and for each i from 2 to N and X, Y from 1 to 2000 if DP[i — 1][X][Y] == 1 then DP[i][f(X+A[i])][Y] = DP[i][Y][f(X+A[i])] = DP[i][X][f(Y+A[i])] = DP[i][f(Y + A[i])][X] = DP[f(X+Y)][A[i]] = DP[A[i]][f(X+Y)] = 1. So in the end we just have to check if for some X, Y such that f(X+Y)=1 DP[i][X][Y] == 1, and restore the answer. The problem is that in general it's not true that f(f(a+b)+c) = f(a+f(b+c)). Test that breaks this solution: 8 4 39 39 51 13 38 66 98 86

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I found it interesting that my friend skip1978 solved div1 E using the random method.

I wonder how high the correct rate of this method is.

63493030

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

    Very, very high at least without trying to design a countertest. It took me many hours of runtime to find a test where it fails — specifically, where the probability that a random sequence of operations works is low enough... although maybe I could buy processing power in the cloud and find more. And that's still just because it reshuffles $$$N$$$ times. With some optimisations, finding a test where it fails would be near impossible because $$$N$$$ is so low.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me what is wrong with my prime factorization in this code for D : Code 1

Also , after changing it I got ac Code 2

Thanks in advance !

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

    I think the code is wrong because of Line 16. The end value of x may be 2 when the begin value of x is 2. Then it will not think 2 has the prime factor 2. the code will be wrong if there is 2 in the input.

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

      Oh I see! Got ac in that too now. Thanks a lot! :D

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cant understand in D one thing. What if we have ones? This solution doesn"t work in this case.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somebody tell me how to solve div2 B2 in O(n) as maintaining count with array will give TLE?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem E to me?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the task D how can we find factorization of every number in the sequence with sqrt(max ai) or log2(max ai) complexity?__

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

    Perhaps it means sqrt(max a[i]) for each number separately so total of n*sqrt(max a[i]) (or nlog(max a[i]))

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to understand E's editorial. please help.

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

Thanks for Fast Editorial.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, we don't need to store the whole list. We know that each list gives us unique number so we just store that number and its frequency.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

My $$$O(n^\frac{5}{3})$$$ code works for D, just thought it was interesting and curious that it got accepted.

On a second look, I think it can be hacked easily. The test cases for D were quite weak.

233245894

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why don't the dickhead authors provide their own code ?

→ Reply