Блог пользователя ch_egor

Автор ch_egor, 4 года назад, По-русски

Спасибо за участие!

1323A - Задача о подмножестве чётной суммы придумал и подготовил vintage_Vlad_Makeev

1323B - Посчитай подпрямоугольники придумал и подготовил vintage_Vlad_Makeev

1322A - Интересные конкурсы придумал vintage_Vlad_Makeev, а подготовил DebNatkh

1322B - Подарок придумал meshanya, а подготовил wrg0ababd

1322C - Лапша быстрого приготовления придумал vintage_Vlad_Makeev, а подготовил ch_egor

1322D - Реалити-шоу придумал voidmax, а подготовил okwedook

1322E - Медианный горный хребет придумал Sender, а подготовил grphil

1322F - Разработка тарифов придумали mingaleg, vintage_Vlad_Makeev, а подготовил 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...
  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Why editorial for D1C in Russian?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How is it written 2weeks ago?

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

1322B — Подарок придумал Tudor Costin & Oncescu Costin, а подготовил Tudor Costin

http://info1cup.com/files/Xorsum-editorial.pdf

»
4 года назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

Div1.D reminds me 2048.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

can anyone explain div2 D problem

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    With hashing you need two modulos to avoid conflicts

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +66 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        really appreciate it! thanks :D

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thanks a lot!!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +110 Проголосовать: не нравится

meme1

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 3   Проголосовать: нравится +54 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    There's also a nlogn solution. Link

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

        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 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          $$$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 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        thx vro

»
4 года назад, # |
Rev. 10   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For div1 B,if you use two pointers and radix sort.Then it will be n log C.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you explain the solution more clearly? thanks.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        OK, thanks for your explaination.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            You can refer to this

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится

              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 года назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится

                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 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Где можно посмотреть разбор на русском?

»
4 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

Bonus of 1322B:

Solution
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

it isn't right bracketed.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone know how to solve div1 B in Nlog(C)??

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why count subsequences problem have binary search tag??

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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