ch_egor's blog

By ch_egor, 4 years ago, translation, In English

Thanks for the participation!

1323A - Even Subset Sum Problem was authored and prepared by vintage_Vlad_Makeev

1323B - Count Subrectangles was authored and prepared by vintage_Vlad_Makeev

1322A - Unusual Competitions was authored by vintage_Vlad_Makeev and prepared by DebNatkh

1322B - Present was authored by meshanya and prepared by wrg0ababd

1322C - Instant Noodles was authored by vintage_Vlad_Makeev and prepared by ch_egor

1322D - Reality Show was authored by voidmax and prepared by okwedook

1322E - Median Mountain Range was authored by Sender and prepared by grphil

1322F - Assigning Fares was authored by mingaleg, vintage_Vlad_Makeev and prepared by KiKoS

Tutorial is loading...
Tutorial is loading...
c++ code by gritukan
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +39
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why editorial for D1C in Russian?

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

How is it written 2weeks ago?

»
4 years ago, # |
  Vote: I like it +69 Vote: I do not like it

Div1.D reminds me 2048.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

can anyone explain div2 D problem

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

How can I split the vertices with same neighboring set in div1 C? I tired hashing with mod 1000000009 and add vertices with same hash values, but got WA at main test 88 :(

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

    With hashing you need two modulos to avoid conflicts

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

    trying not well-known modulos(or return pair of integer with different modulos as hash value) might help.

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

      I highly dissuade hashing (multi)sets modulo a prime. Instead: assign random 64bit integer for each element, and use xor/sum of all elements as hash of the whole set (xor if we are guaranteed there are no repetitions, or we do want repetitions to cancel out, sum if we're hashing a multiset). To get those values of each element I use following function:

      ull mix(ull o){
          o+=0x9e3779b97f4a7c15;
          o=(o^(o>>30))*0xbf58476d1ce4e5b9;
          o=(o^(o>>27))*0x94d049bb133111eb;
          return o^(o>>31);
          //Those constants supposedly are chosen to give this function better pseudo-random properties, but on any on-site contest, when one can't have team reference document/doesn't want to waste time searching it for implementation typing arbitrary large odd numbers by hand should be good enough
      }
      

      And value used for x is mix(x), or in case of rounds with hacking mix(x ^ salt), where salt is value returned by chrono::steady_clock::now().time_since_epoch().count() at the beginning of runtime. This is way faster than anything using modulo, uses all 2^64 possible hash values, so avoids any birthday paradox issues, also avoids any overflows/issues with and requires way less code than using more than one modulo.

      Moreover this technique can be used for hashing other objects than sets, e.g. sequences, which can be represented as set of pairs $$$(i, a_i)$$$, the only difference is that now we need random value for each pair, but this can be easily done e.g. by

      ull hash(pii a) {return mix(a.first ^ mix(a.second));}
      

      And finally: using well-known modulos is not an issue, as long as you use random number as base (guaranteed by Schwartz–Zippel lemma).

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

        really appreciate it! thanks :D

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

        Hashing sequences modulo two highly non-random primes has always worked for me. Your method seems better, but the critical part is avoiding outright bad hashes and the second is avoiding easy hacks, the rest is finetuning.

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

        thanks a lot!!

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

        Hey, would it possible for you to give a little insight on its applications and also could you give some links to your own codes using this methodology so that I can study them.

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

    Using a map passes in a little bit less than 1s 72663606. Memory is easy to analyze here since total number of elements in all vectors in the map will be equal to $$$E$$$ (where $$$E$$$ is the total number of edges). But I'm not sure how to analyze the time complexity of this solution.

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

      Insertion:
      comparing two vectors a,b takes $$$min(a.size(),b.size())$$$. In balanced BST like map comparison occurs $$$O(log(n))$$$ times (n -> size of map before insertion). So when inserting vector of size s, time is $$$O(s*log(n))$$$. So inserting multiple vectors with combined size $$$m$$$ is $$$O(s_1*log(n))+O(s_2*log(n))+ \ldots = O(m*log(n))$$$

      Retrieval : similar to above analysis.

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

    You can just keep a map<vector< int>,long long>, where the key (vector< int>) is the list of all connected vertices and the value is the sum. This passes in about 800ms.

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

      How to analyze the time complexity of this solution? How to calculate the upper bound on the total number of comparisons made in the map?

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

        Good question, I'm not at all sure. Maybe someone can hack our solutions. But if i had to guess, I would say that it can not be hacked and maybe someone can show that the complexity is something better than $$$O(n^2 log~n)$$$.

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

        Well, the number of comparisons is $$$O(\log m)$$$ and each comparison takes $$$O(size)$$$. Since you search every vector in map only once and the sum of all sizes is $$$m$$$, the complexity is $$$O(m \log m)$$$

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

    Your text to link here... I was calculating equivalence classes of vertices on the right (v ~ u iff N(v) = N(u)), adding vertices to the left part. The complexity this procedure should be around $$$O(V\log{V} + E)$$$.

»
4 years ago, # |
  Vote: I like it +110 Vote: I do not like it

meme1

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

Is the time limit of Div1B set according to $$$O(n \log n \log C)$$$ solution? My submission 72640450 runs 2979ms, which is very close to get TLE.

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

    Yes, it's pretty tight, but the first thing I wrote runs in 2 seconds and it's easy to optimise — e.g. by handling small bits more easily because everything is small when we discard larger bits.

»
4 years ago, # |
Rev. 3   Vote: I like it +54 Vote: I do not like it

I will try to provide some intuition to the solution of Div1 C.

Look at the image below, each node in the left half of the graph is drawn as a cricle (denoting a set, not the problem's defined set, but a new set we're going to define). The numbers in the rectangles are the ID's of the nodes and the characters are the elements included in the node's set. These set elements (the characters) represent sum of node values of the right half of the graph.

For example, if $$$S = \{ 0 \}$$$ then $$$F(S) = a + b + c + d$$$. if $$$S = \{0, 2\}$$$ then $$$F(S) = a + b + c + d + f + g$$$. Note that each character in picture may denote more than one node in the right half of the original graph.

Now assume you've computed the gcd of all intersections of sets like the editorial have mentioned in the first paragraph. In the image below this will mean you've computed $$$gcd(a, g, e, d + c, b + c, c + f, c) = m$$$

You will observe that if you union any number of sets now, the summation will (hopefully) be multiple of $$$m$$$. For example if $$$S = \{0, 1\}$$$ then $$$F(S) = a + b + c + d + e + f$$$, or if $$$S = \{0, 1, 2\}$$$ then $$$F(S) = a + b + c + d + e + f + g$$$. You will find that each term in the summation is a multiple of $$$m$$$.

I'm not sure how to prove this formally (if someone can formalize all this trash, it would be appreciated!), but I wanted to show some intuition on how one would approach such problem.

Untitled

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

    The text of the editorial for problem Div1C (D1C) is not ideal.

    For further clarity, I think the author had something like the following in mind. For example for the instance: LeftSide={a,b,c,d,e}; RightSide={X(11),A(7),B(8),Y(10)} and edges {a,b}-->{A,X}, {d,e}-->{B,Y} and c-->{A,B}, by what I understand for the editorial solution, the partition would be something like this:

    Set1 = {A,X} with value sum(11+9) = 18. Set2 = {B,Y} with value sum(8+10) = 18. Set3 = {A,B} with value sum(7+8) = 15.

    Clearly any non-empty subset of the LeftSide elements will have as sum a linear combination of values from the resulting sets Set1..Set3 above. Including the one with a single 1 and all 0s. As such, clearly the solution is the CMMDC of the values of these sets.

    The tricky part however stirs from the fact a single right hand side element (A or B in the above example) can belong to several partitions. I am not sure the author covered the part about constructing such partitions (and proving there cannot be too many of them) properly (detailed enough).

    My own approach (did not have time to finish implementing it during the contest), relied on the following observations: the sum of any subset is of the form Sum(Right(a1))+..+Sum(Right(ak)) - Sum(Intersect(Right(a1),Right(a2)) - ... - Sum(Interesect(Right(a[k-1]),Right(ak))). Thus all we need is the CMMDC of all singleton sets to be further reduced to common multiples to Sums of each pairwise intersection of right-hand sides of all singleton sets.

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

    An exercise in formalization for readers: think of how 908E - New Year and Entity Enumeration and this are related, and what properties of the GCD function we use.

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

It's my code:https://codeforces.com/contest/1323/submission/72668413

I just use the loop. esay,but of course TLE.So, I have some trouble.

I do not really understand the editorial.

And, what should I do to improve my code.

please help me, thanks!

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

    Your code runs in O(n^2). Your solution is a straight forward brute force. However, you should find an another solution in many problems due to time limit.

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

If the intended solution was O(nlognlog(1e7)) for div 1 B, where can I reduce the constant factor in my code. I am not very experienced in optimizations so any help is appreciated.

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Completely different solution to D1E:

  1. Prove that if $$$a_i$$$ doesn't change at some moment of time, then it will never change anymore.
  2. Assume that $$$a_{i-1} < a_i > a_{i+1}$$$. Prove that each odd-indexed change to $$$a_i$$$ will decrease the number, and each even-indexed change will increase it. (A symmetric claim works if $$$a_{i-1} > a_i < a_{i+1}$$$.)
  3. If $$$a_i$$$ decreased in the first step and increased in the second step, each of the values $$$a_{i-1}, a_{i+1}$$$ must have increased in the first step. So if $$$a_i$$$ changes at least twice, $$$a_{i-2} > a_{i-1} < a_i > a_{i+1} < a_{i+2}$$$ must hold. (Similar claim follows for any number of changes).
  4. Assume that $$$a_{i-1} < a_i > a_{i+1}$$$. Prove that the value of $$$a_i$$$ after $$$k$$$ changes is equal to $$$\max(a_{i-k}, a_{i-k+2}, a_{i-k+4}, \dots, a_{i+k})$$$ if $$$k$$$ is odd, and $$$\min(\text{same stuff})$$$ if $$$k$$$ is even. (For $$$a_{i-1} > a_i < a_{i+1}$$$, $$$\max$$$ and $$$\min$$$ are swapped.)
  5. Therefore, $$$a_i$$$ changes at least $$$k$$$ times if each $$$a_{i-1}, a_{i+1}$$$ changes at least $$$k-1$$$ times and after $$$k-1$$$ operations, $$$a'_i$$$ is not the median of $$${a'_{i-1}, a'_i, a'_{i+1}}$$$.
  6. In particular, if $$$a_i$$$ changes exactly $$$k$$$ times, then $$$a_{i+1}$$$ will change exactly $$$k-1$$$, $$$k$$$ or $$$k+1$$$ times.
  7. Then, for each $$$a_i$$$ we will compute how many times this value changes. Obviously, $$$a_1$$$ changes 0 times. For each following $$$a_i$$$, we have three options on the number of times $$$k$$$ that $$$a_i$$$ will change. We can check if $$$a_i$$$ will change, by computing $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$ after $$$k-1$$$ operations using simple RMQ (we need 4 RMQ instances for computing min/max on odd/even-indexed values) and checking if $$$a_i$$$ is not the median of these three values.
  8. After we compute these values, the rest is easy: we know maximum number of times the sequence will change, and we can restore the final sequence using the formulas in (4).

Not everything in here is sound, but it's possible to write down and analyze all formulas and find out everything should be OK with this solution.

Total runtime is $$$O(n + \text{RMQBuild} + n \cdot \text{RMQQuery})$$$. When RMQ is implemented using a sparse table or a segment tree, we end up with a very fast $$$O(n \log n)$$$ solution: 72662345. Using the optimal RMQ, we can solve the problem in $$$O(n)$$$ time.

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

Can someone walk me through the complexity of D2 B of the editorial. I thought it will led to TLE but it didn't.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. For finding factors of k, you need O(sqrt(k)).
    2. After that you can pre-calculate the no. segments of all length(up to the size of array) which only contains 1 in one go. So, you need O(m+n) for this.
    3. Finally iterate over all the factors of k (which is very small compared to other factors, so you can neglect its complexity) and calculate the answer. ( Say the current factor is a , then other correspondin factor will be b(=k/a), since a*b must be k. Now check how many segments of a are in array 1 and how many segments of b are in array 2 and vice versa. Add these to the final ans )

    So, final complexity is O(sqrt(k)*(n+m)).

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

What was the intended complexity of div2B? I can see so many solutions running in about sqrt(k)*(n+m). Shouldn't that TLE?

I had come up with something similar too early in the contest but didn't submit because I thought it will TLE :/. Ended up submitting an optimisation of the same, which runs in somewhat similar complexity.

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

    Well, complexity sqrt(k) * (n + m) will have TLE. This sqrt(k) comes from finding all divisors of k. You don't need to do that. You only need to find divisors d such that either (d <= n and k / d <= m) or (d <= m and k / d <= n), others are just too big. And that will be fast enough.

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

      Yeah, agreed. What I meant to ask was, why are submissions like these [LINK] getting accepted ? Isn't this exactly sqrt(k)*(n + m) complexity, which is of the order 10^9 as per the given constraints ?

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

        I'm also not sure why submissions like that are accepted. In my solution, I did loop sqrt(k) times, but in my precomputation I only stored the maximal consecutive lengths and put them in a map. With some basic math you find that the number of entries in the maps are bounded by sqrt(n) and sqrt(m), so my solution ran in sqrt(k)*(sqrt(n)+sqrt(m)).

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

          Yeah I did the same during the contest. But after the contest ended I saw so many solutions being accepted without using map and traversing over the entire array. Wasted a lot of time in this unfortunately :/

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

        it's not sqrt(k)*(n+m), it's d*(n+m) where d is number of k's divisors. i think d can't be more than 1000, that's why this solution fits in 1s.

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

          Oh yes you're right! Thanks! I need to learn how to correctly analyse the complexity xD

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

        The upperbound of number of divisor of a number N is considered n^(1/3). So it's not sqrt(k)*(n+m), but it's (k^(1/3))*(n+m)

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

          But this should get TLE too. In worst case k = 16e10 and (n + m) = 8e5
          ==> (k^(1/3))*(n + m) = 5e3 * 8e5 = 4e9, then how is this running within a second?
          I solved this question by preprocessing both arrays to store count of contiguous 1s only (as mentioned in previous comments).

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

            Look at the constraints again, n,m<=4e4 not 4e5. So n+m<8e4 and k<=16e8. Hence (k^(1/3))*(n+m)=1e3*8e4=8e7

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

              Okay got it. My bad

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

    There's also a nlogn solution. Link

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

In D you can also be an idiot, not reverse the sequence, and barely pass in 1980ms like this: 72679047. The complexity is $$$\mathcal{O}(nm \log m)$$$, were you trying to cut solutions like this?

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

I didn't quite get the editorial of Div.1A, can someone please explain it to me?

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

Can someone please explain their intuition and code behind Div2D/Div1B? The tutorial doesn't help me much.

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

For Div2D / Div1B, I think people counted in a different way as editorial, the number of pairs which have k'th bit set in their sum. Can someone share a better approach?

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

    hey could u please explain the logic behind div 2 D problem(present).. i did not get much from the editorial ..thanks in advance

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

      Sure.

      Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also. 2e7 is contained in roughly 25 bits. We check for each bit of ans whether it will be turned on or off.

      For kth bit of ans, we see in all the pair-sums ( $$$a_i + a_j$$$ for all i and j), the kth bit of them. So if the number of pairs having kth bit set are even then for the kth bit, their xor is zero, else one. So kth bit of the answer = xor of all the kth bits of the pair-sums.

      To find the count of pair-sums having kth bit set, we notice that we can mod all $$$a_i$$$ by $$$2^{k+1}$$$.

      Why?

      After modding we say that for a sum to have kth bit set, it can take values from $$$[2^{k}, 2^{k+1}) \ \cup \ [2^{k+1} + 2^{k},$$$ Max-Value-Sum-Can-Take $$$]$$$ (Check the why spoiler to know why)

      To find the numbers in the proposed ranges, we simply make another array $$$B$$$ of modded $$$a_i$$$'s and sort them. Then we can assume sum, $$$S = B_i + B_j$$$ . Iterate over $$$i$$$ in $$$B$$$, find maximum bound of $$$j$$$ using binary search (built-in lower_bound or upper_bound functions in C++). For example if we want to find $$$B_i + B_j <= P$$$ then $$$B_j <= P - B_i$$$. So fix $$$i$$$ and since array is sorted we find the last $$$j$$$ that satisfies the given condition and all the numbers in the range of indices can be added to the count to check the xor.

      Code : 72719677

      Let me know if I missed something or made a mistake.

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

        Got it...thanks a lot brother ...i realy appreciate your efforts ..keep on helping like this ..thanks a lot once again i wish i could give more than one upvote to you ..

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

        Hi, thanks for the detailed solution.
        I understood the core part.
        However, I didn't understand the following:
        Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also

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

          $$$1e7$$$ actually is a notation for $$$10^7$$$. Max value of $$$A_i + A_j$$$ is $$$1e7 + 1e7 = 2e7$$$. Now all the pair-sums can have value $$$2e7$$$ and we are xor'ing them. And we know that for two integers, $$$P\ xor\ Q <= P + Q$$$

          Why? Because $$$P + Q = (P xor Q) + 2 * (P & Q)$$$

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

            Thanks a lot!
            And, thanks for quick reply!
            Keep helping others!

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

        thx vro

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

Is this solution (72639972) to div2B hackable? It's $$$O(n \cdot numDivisors(k))$$$, which might be a bit slow with standard Java HashMaps

Notes

Update: This is my hack attempt generator: https://pastebin.com/2wyjDVMB . Local testing seems to indicate that my solution should still pass with it though (about 70ms, excluding input and startup overhead). Maybe excluding out-of-bounds divisor pairs sped it up enough to be unnoticeable with these input constraints, or even improve the big-O bound.

Update 2: Yep, was unsuccessful. Thanks anyway

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

    My solution was also $$$O(n * numDivisors(k))$$$. What is the upper bound of this complexity that it passed in the time-limit?

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

      Big-O estimates are by nature an inexact science, but the literal formula evaluates to about $$$6 \cdot 10^7$$$, which could be on the edge of 1 second if the constant factor is large enough. I thought using HashMaps might push me over the limit, but I think I might have overestimated the runtime complexity of my solution, considering how fast my thought-to-be-adversarial case ran.

      I believe that the intended solution is meant to be $$$O(n^{1.5})$$$.

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

        Thank you for the response. I am interested in knowing what is the literal formula you're talking about that you calculated it to be $$$6e7$$$ ? Are you approximating the maximum number of divisors with some approximation?

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

For div1 B,you can use two pointers and radix sort,then the time complexity will be n log C.

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

    Could you explain the solution more clearly? thanks.

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

      It is same as the editorial.

      But for the sorting,use radix sort($$$O(n)$$$) instead of quick sort($$$O(n\log n)$$$).For the search,use two pointers($$$O(n)$$$) instead of binary search($$$O(n\log n)$$$).

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

        OK, thanks for your explaination.

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

          Can you please further break it down? I'm struggling to follow the explanation in the editorial

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

            You can refer to this

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

              Thanks. I'm having trouble understanding how did we calculate the ranges? Will you be able to elaborate on how your binary search is working in the same context please?

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

                We exploit the fact that B is sorted.

                Let $$$B = [2, 3, 5, 6, 9]$$$ and suppose you have to find $$$B_i + B_j <= 11$$$ . Now to solve this we iterate over $$$i$$$ from range 1 to N (size of B, which is 5 here and B is 1 based indexing).

                For i = 1, we can take j = 2, 3, 4, 5

                For i = 2, we can take j = 3, 4

                And so on..

                Now to find the last value of $$$j$$$, we perform a binary search in range $$$[i+1, N]$$$ which finds the greatest index $$$j$$$ that satisfies $$$B_j <= 11 - B_i$$$ . Google the working of lower_bound and upper_bound to understand how to implement such a binary search.

                After finding the last $$$j$$$, we conclude that all indices from $$$i+1$$$ to $$$j$$$ can pair with $$$i$$$ to satisfy the problem in hand. So we add $$$(j-i+1)$$$ to the answer.

                Before asking questions, you should first google your problems to check if this kind of question is popular enough that people have answered it already. For example here, googling about upper_bound and lower_bound on geeksforgeeks or even C++ documentation, would have helped you :)

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

                  After modding we say that for a sum to have kth bit set, it can take values from [2k,2k+1) ∪ [2k+1+2k, Max-Value-Sum-Can-Take ]

                  I'm not sure how these values came about ^

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

                  If the most significant bit of a binary number is (k+1), then for a number to have kth bit set, it is necessary to be >= $$$2^k$$$. All the numbers from there to the max val of the binary numbers with (k+1) MSB, except numbers from $$$2^{k+1}$$$ to $$$(2^{k+1} + 2^{k} - 1)$$$, will have kth bit on. Please take k = 2 and draw binary representation of each number to find out why. (I have already explained in the why spoiler in my original comment — it is because of the carry over in addition of binary numbers). If you still have doubts, please personal-message me.

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

        Could you please explain, how to use two pointers instead of binary search?

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

I think the time limit for Div2D is quite tight, I had a O(nlogc*logc) solution using Fenwick Tree but got a TLE

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Can someone explain div1D because I can't get much of what the editorial is saying?

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

why 1323 B , gb[k/i] is not giving runtime , i applied same logic but got runtime at tc 5 ... Please someone clarify

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

    It is probably because k/i goes up to 10^9, which is beyond the size of the array declared. You only need those factors of k which are less than n and m. Basically i <= n and k/i <= m. It should work if you handle this case.

»
4 years ago, # |
  Vote: I like it -36 Vote: I do not like it

for question B, Count subrectangles : plz can somebody tell me why following code in giving wrong answer in test case 7??

include <bits/stdc++.h>

define int long long int

using namespace std;

int max(int a,int b) { return a>b?a:b; }

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //cout<<"I must do it...Yeahhh";

int t=1;
//cin>>t;
while(t--)
{
    int n,m,k;
    cin>>n>>m>>k;

    int a[n],b[m];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i]; 

    int x=0,ans=0;
    vector<int>va,vb;

    vector<int>check;
    for(int i=1;i<=sqrt(k);i++)
        if(k%i==0)
            check.push_back(i);

    x=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]==1)
            x++;
        else if(a[i]==0 && a[i-1]==1)
        {
            va.push_back(x);
            x=0;
        }
        else
            x=0;
    }
    if(a[n-1]==1)
        va.push_back(x);
    /*for(int i=0;i<va.size();i++)
        cout<<va[i]<<' ';*/
    //cout<<'\n';
    x=b[0];
    for(int i=1;i<m;i++)
    {
        if(b[i]==1)
            x++;
        else if(b[i]==0 && b[i-1]==1)
        {
            vb.push_back(x);
            x=0;
        }
        else
            x=0;
    }
    if(b[n-1]==1)
        vb.push_back(x);
    /*for(int i=0;i<vb.size();i++)
        cout<<vb[i]<<' ';
    cout<<'\n'<<va.size()<<' '<<vb.size();*/
    for(int i=0;i<check.size();i++)
    {
        int x=check[i];
        int y=k/check[i];

        for(int j=0;j<va.size();j++)
        {
            for(int k=0;k<vb.size();k++)
            {
                if(k<=va[j]*vb[k])
                {
                    if(y==x)
                    {
                        ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
                    }
                    else
                    {
                        ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
                        ans+=(max(va[j]-y+1,0) * max(vb[k]-x+1,0));
                    }
                }
            }
        }
    }
    cout<<ans;
}
return 0;

}

Thanks in advance

»
4 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

Bonus of 1322B:

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

What's the $$$O(n)$$$ solution for E?

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

    It's quite complicated. Let's call mountain high if $$$a_{i -1} \le a_i \ge a_{i + 1}$$$ and low if $$$a_{i - 1} \ge a_i \le a_{i + 1}$$$. As we know, changes will happen to consecutive segments of mountains, where for each odd $$$i$$$ $$$i$$$-th mountain is high and for even $$$i$$$ $$$i$$$-th mountain is low, or vice versa.

    Now let's assume that all heights are different. Then let's look for each low height $$$a_i$$$ and find, on which positions at some time there was mountain of height $$$a_i$$$. It can be noticed that there is a contiguous segment of such positions, and to find it's left border we should look at first low mountain on the left (on position $$$x$$$) which is higher than $$$a_i$$$ and first high mountain on the left (on position $$$y$$$) which is lower than $$$a_i$$$, and the left border is middle position between $$$i$$$ and $$$max(x, y)$$$. The same with right border and for high mountains. Then we can look at 4 different variants of $$$max(x, y)$$$ on the left and on the right and using only this information we can find on which positions the height $$$a_i$$$ will be in the end. For more details you can look at my code for this problem,

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

For Div1 B, 72638208 doesn't check the sum to fall in two ranges and just uses one pass instead of four passes. Anybody know why?

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

Can anyone explain Div1D. I have no idea what the editorial is saying.

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

After reshuffling 2 segments of total length 8, we can get a right bracketed sequence:()()((()())

it isn't right bracketed.

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

Can anybody explain how to use two pointers method in Div2 D?

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

Is editorial's proof of Div1C(Instant Noodles) correct on this test?

3 6   //n, m
1 3 5
1 1
1 3
2 1
2 2
3 2
3 3
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been trying to understand the editorial for Div.1 D for a whole day, but I still can't get it.

Now I have a question about the problem description:

"The show host reviewes applications of all candidates from $$$i=1$$$ to $$$i=n$$$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $$$i$$$ is strictly higher than that of any already accepted candidates, then the candidate $$$i$$$ will definitely be rejected."

Does it mean we should first choose the set of participants to accept which $$$l_i$$$ is non-ascending then let them do the show and fight against each other? If a participant was defeated, is it still regarded as "already accepted"?

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

In the tag of div2 B problem, it is showing binary search as a tag, but there is no use of it in problem, why it is so?

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

I wrote a more detailed editorial of 1332E — Instant Noodles I wanted to write it down so that I could understand it more.

https://gist.github.com/mightymercado/9f281177bcb9d39b7d55ff4a9ab29f4d

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

why does this tle for count rectangles submission, i have basically the exact same thing as editorial said

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

I took part in the competition in Moscow and now I wanna ask you — is there a place where I can read tutorial like this here but about the other two problems (“Double palindrome” and “Latin Square”), that weren’t included here in this Codeforces round. It’ll be great if I can also practice them somewhere. I’ll be very grateful if somebody helps me :).

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

nobody used stack for div1 A 1322A - Unusual Competitions ?

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

Implementation of ques C-Unusual Competition using Stack, storing position of unbalanced braces. https://codeforces.com/contest/1323/submission/97906786

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

why count subsequences problem have binary search tag??

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

Can you provide the solution for problem: 1322A in a simple language The explanation seems pretty complicated. Also, it would be helpful if you could provide me with a solution to the problem. Problem Link: https://codeforces.com/problemset/problem/1322/A