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

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

1420A - Сортировка кубов

Подсказка
Разбор
Код C++ (Wind_Eagle)

1420B - Камень и рычаг

Подсказка
Разбор
Код C++ (Wind_Eagle)

1420C1 - Армия покемонов (простая версия)

Подсказка
Разбор
Код C++ (gepardo)

1420C2 - Армия покемонов (сложная версия)

Подсказка
Разбор
Код Java (gepardo)
Код C++ (Wind_Eagle)

1420D - Спасти Нибель!

Подсказка
Разбор
Код Java (gepardo)

1420E - Боевые лемминги

Подсказка 1
Подсказка 2
Подсказка 3
Разбор
Код C++ (gepardo)
Разбор задач Codeforces Round 672 (Div. 2)
  • Проголосовать: нравится
  • +314
  • Проголосовать: не нравится

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

Ого! Настолько быстрый разбор, да ещё с подсказками! Очень здорово, что вы сделали их. Надеюсь, многие авторы тоже так будут делать в разборах)

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

    ++. Просто за подсказки уже топовый разбор. Задачи, в целом, тоже классные были.

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

Очень полезно и отлично, что разборы идут с подсказками! Было бы хорошо увидеть подсказки перед разбором задачи и в дальнейших контестах.

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

Auto comment: topic has been translated by gepardo (original revision, translated revision, compare)

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

Actually, many people say that now there are practically no data structure or DP tasks, only ad-hoc and constructive. Well, this contest disproves this. There were no constructive tasks, but there were Segment Tree in C2 (there is a solution using it) and DP in E.

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

    One contest doesn't disprove a trend.

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

    I am actually better at ad-hoc and constructive currently and loved the trend :sobs:, But I do like these rounds where I learn a lot.

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

    Please could you explain/hint about the Segment tree solution of C2. How will we merge answer of left and right for getting answer of current node ? Thanks in advance!

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

      You can maintain four quantities in the segment tree node i.e maximum strength given that
      1. first element has $$$plus$$$ sign before it and last one also has $$$plus$$$ sign
      2. first element has $$$plus$$$ sign and last has $$$minus$$$
      3. first element has $$$minus$$$ sign and last has $$$plus$$$ sign
      4. first element has $$$minus$$$ sign and last has $$$minus$$$ sign
      You can easily implement merge and update operations.
      Here is my implementation https://codeforces.me/contest/1420/submission/93716090. There may be easier solutions but this one was more obvious and intutive

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

    Hi Sir, I wanted to know is there any site that focusses more on data structures and less on ad-hoc?

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

    I implemented segtree and received tle in C2. someone willing to help? https://codeforces.me/contest/1420/submission/93731337

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

    Also, if you exepected segtree, the constraints could've been relaxed (:

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

    Wind_Eagle Can you please Explain 1420B.Rock and Lever Not able to understand.From the editorial code

    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<ctime>
    #include<random>
    
    using namespace std;
    
    mt19937 rnd(time(NULL));
    
    int a[1000000+5];
    
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t;
        cin>>t;
        while (t--)
        {
            int n;
            cin>>n;
            for (int i=0; i<n; i++)
            {
                cin>>a[i];
            }
            int64_t ans=0;
            for (int j=29; j>=0; j--)
            {
                int64_t cnt=0;
                for (int i=0; i<n; i++)
                {
                    if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))
                    {
                        cnt++;
                    }
                }
                ans+=cnt*(cnt-1)/2;
            }
            cout<<ans<<'\n';
        }
    }
    

    Why to need to check a[i]<(1<<j+1).Why the total number of pairs is cnt*(cnt-1)/2.Can you please explain.Tried to understand for so long still not clear

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

      a[i]>=(1<<j) is actually $$$a_i \geq 2^j$$$, and a[i]<(1<<(j+1)) is actually $$$a_i < 2^{j+1}$$$. If some number is greater or equal than $$$2^j$$$, and strictly smaller, than $$$2^{j+1}$$$, than it contains $$$j$$$-th bit as the greatest bit.

      cnt*(cnt-1)/2 is actually $$$C_n^2$$$, where C is binomial coefficient. More easily, this is the number of ways to pick to different things from a set of $$$n$$$ things. In this task we want to choose the number of ways to pick two numbers from $$$n$$$ numbers.

      It seems to me that you should first study some simple maths, like basic combinatorics, bit arithmetics and number theory. With mathematical base it is much easier to study CP.

      Thank you for solving my contest!

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

For E, if we accept solution in O(n^5), I think it may be better to choose a smaller n. For me, I was too afraid that an O(n^5) solution will TL and just tried to think of a better solution.

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

    We initially thought of making $$$n \le 100$$$ in this problem, because my solution in $$$O(n^5)$$$ passes with such constraints. Anyway, the DP solution is pretty fast and $$$n^5$$$ can be easily divided by some constant factor, so the constraints may seem too big for $$$O(n^5)$$$.

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

      I can understand your choosing n<=80. Maybe I just need to accept the fact that computers are much faster nowadays.

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

      BTW, my solution at https://paste.storage.boleyn.su/cfr672d2e.cpp should have a better time complexity. I have not analyzed its TC yet so this is just my guess.

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

        Can you explain your approach? Is it true that you use a DP similar to the one described in the editorial, but you optimized the code by skipping invalid DP states?

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

          For the last dimension, it is non-decreasing, so we can express it using a vector<pair<int,int>> and reduce some useless states.

          My guess is that there may be a bound better than O(n^2) for it. It would be nice to prove or disprove my guess.

          UPD: I tested it with larger constraints. It turns out that my guess is wrong. The size of vector<pair<int,int>> is still O(n^2).

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

I felt like D had hard time limits. But, later realized after contest with precomputation of inverse of each factorial it could have been made faster.

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

    Can you(someone) explain how to do that? Cause I got a TLE on pretest-11.

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

      precompute fact 1 to n and mod inverse of those instead of computing them every time.

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

      Precompute factorials from 0 to N (here $$$3*10^{5}) $$$ initially in an array, say $$$fact$$$.
      Then calculate inverse factorial of N using formula $$$inv_f(N) = fact(N)^{MOD-2} \% MOD $$$
      which takes $$$ O(\log_2 (MOD))$$$ time. Using this value, now fill the remaing values from N-1 to 0 using recurrence : $$$inv_f(i) = (i+1)*inv_f(i+1)$$$.
      Thus we can precompute inverse factorials in $$$ O(N) $$$ complexity.
      Solution for reference : 93729779

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

        Hey, I precomputed the factorials and inverse factorials similar to your solution but I am getting TLE.

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

          Use binary exponentiation in your powmod function to calculate $$$a^b$$$ in log(b) complexity, you are calculating it in O(b) time. You can read it here : cp-algo

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

        Note that precalculateing the inverse factorial does not give a better runtime. We never need to calculate more than $$$3*10^5$$$ inverses. So precalculating them just uses more memory, but not less time.

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

          But to calculate $$$3*10^5$$$ inverse factorials you'd have to calculate them in $$$O(log_2(Mod))$$$ individually resulting in $$$O(N*log(Mod)$$$ time. But here I am precalculating them in $$$O(N)$$$, so I am unable to understand your logic behind why this won't give better runtime? Can you please elaborate.

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

            You are right. I was irritated by the long runtime of your solution. But that is caused by the use of the map instead of sorting an array once.

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

        I encountered this for the first time, tried to dig around but can't figure out why this works-

        invf[i] = invf[i+1]*(i+1)%mod;
        

        Can u help or tell me where to look.

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

        Hi there. Please, tell me about inverse factorial of N. What is it?

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

    I precomputed the factorials and the inverses, thus my solution was linear, though I think $$$O(n\log mod)$$$ should fit in time.

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

Great problemset, like it . waiting for your next contest,thanks

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

For some problem editorial is in english and for others it's in russian . Pls Fix.

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

    The English versions will be loaded in several minutes.

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

      Can you tell if the elements of array in C1 are not distinct what will happen??

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

        I don't understand your question. The elements $$$a_i$$$ are distinct by problem statement. Or do you want to know if the intended solution works if equal elements are allowed?

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

          Yess if we go by approach for maxima and minima approach for C1 problem then will it work??

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

            It is unclear how we will treat an element if its neighbor is equal to it. Or even worse, when both neighbors are equal to our element. Will it be a local maximum or local minimum? Also it's important that local minima and local maxima must alternate (this property is used actively in the proof).

            Anyway, it's an interesting question on how to fix the solution when equal elements are allowed.

            If you solve C1 using dynamic programming, you should not be affected by equal elements.

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

              One may assume that out of equal neighboring elements, the left one is smaller. This is equivalent to adding $$$i \cdot \varepsilon$$$ to $$$a_i$$$, which makes all elements distinct while keeping the answer the same if $$$\varepsilon \rightarrow 0$$$.

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

              A trivial fix is to break ties by index, so that if $$$a_i = a_{i+1}$$$, we can simply pretend $$$a_i < a_{i+1}$$$. This is safe because the value of the optimal solution is continuous in the values of $$$a_i$$$ and we can imagine taking $$$a_i = \lim_{\varepsilon \to 0^+} a_i + i \cdot \varepsilon$$$ simultaneously at all indices. Alternatively, the solutions based on the $$$\sum_{i = 1}^n \max (0, a_i - a_{i-1})$$$ formula or on segment trees are completely unchanged, since they do not make use of the distinctness constraint in any way.

              EDIT: I was beaten to the punch! So it goes.

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

what is "Разбор"???? is it rated??

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

Round was great. Kudos to author!!

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

My editorial is in Russian :(

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

I could not solve a single problem in this contest, should I die? Why am I even alive.

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

I don't understand the solution for problem D. This is my understanding so far :-

For example: if there is a starting point on 42 and our count of segments excluding this is 10 and the value of k is 3. then I found out the solution is to add ncr(10,k-1).Now the count is 11 and if we again reach to another starting position on 45 so again we will add ncr(11,k-1).Now count is 12.

So if I understood it correctly, then we will choose one out of k to be the current one and choose rest k-1 from the previous segments right?

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

    If we fixed a starting point, we may pick any $$$k$$$ segments that contain it. But there must be at least one segment that start in this point (note that more than one one segment may start in the same point).

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

      Actually, I was talking something like this solution.

      I tried this concept after the contest.

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

        I understood your solution. It's mostly the same as in the tutorial, but it considers the segments that start in the same point in a shorter and nicer way.

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

How to solve C2 using segment tree?

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

    I used an ad-hoc segment tree with 4 values for each range:

    • The max value you can get by using an even number of elements in that range
    • The max value for an odd number of elements
    • The min value for an even number of elements
    • The min value for an odd number of elements

    The value (max/even) of a node is the max from these values:

    • left child's (max/even) + right child's (max/even)
    • left child's (max/odd) – right child's (min/odd)

    The rest of the values are obtained similarly. Updating the tree is the same as a regular segment tree.

    Here is my code.

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

I am still a bit surprised to see the no. of submissions on the Problem D, Is it some sort of a standard algo or question? Because some were able to this in a matter of just few minutes, if it is then please do tell me

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

    I don't know weather it's standard or not but many interval related questions have similar approach.

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

      What is the approach?

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

        My approach for D. Rescue Nibel : I will tell you the method i used to solve, i don't know weather its similar to tutorial's but mine one is easy.I will create a array and put inside L and R + 1 for all intervals. So array will have size = 2 * N. Then sort the array. We keep a variable cnt which will tell the number of lamps which are currently ON. Initially cnt = 0. Now we will iterate over all element of array (in chronological order). Let the current element be x. Now x will either be starting time or (ending time + 1) of some interval. If it is starting time and cnt >= k - 1 then we add NCR(cnt, k - 1) to the answer. We take k - 1 because the kth element will be the lamp whose starting time is x and remaining k - 1 we take from our cnt(lamps which are already in ON state). Then we increment our cnt by 1. If x is (ending time + 1) of some lamp then we just decrement our cnt. This is my code --->

                vector<pair<int, int> > v;
                int L[n], R[n];
                int ans = 0, cnt = 0;
                for (int i = 0; i < n; i++) {
                    cin >> L[i] >> R[i];
                    v.push_back({L[i], 1});   
                      // starting time of lamp
                    v.push_back({R[i] + 1, -1}); 
                      //ending time + 1 of lamp
                }
                sort(v.begin(), v.end());
                for (int i = 0; i < 2 * n; i++) {
                    int S = v[i].second;
                    if (S == 1) {
                        if (cnt >= k - 1) {
                            ans += NCR(cnt, k - 1, MOD);
                            ans = ans % MOD;
                        }
                        cnt++;
                    }
                    else {
                        cnt--;
                    }
                }
                cout << ans;
        
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think you should try ** Min Stations for trains ** problem on GFG.

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

I had a Java solution TLE on D which I fixed by just using a hashmap to cache the results of modular inverse :/

w/o cache: https://codeforces.me/contest/1420/submission/93688984

w/ cache: https://codeforces.me/contest/1420/submission/93691811

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

Solution for Problem C2

Suddenly it turns out that a single request will change the state of no more than six elements

Didn't get intuition for this statement! Someone Please elaborate

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

    Only the neighbour elements affect local maximum and local minimum. So, if you swap $$$l$$$ and $$$r$$$, you will need to recalculate only $$$l$$$, $$$r$$$ and their neighbours (in the worst case, it will be $$$l-1$$$, $$$l$$$, $$$l+1$$$, $$$r-1$$$, $$$r$$$ and $$$r+1$$$, thus six elements).

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

    Whether an element is a local maximum (or minimum) or not solely depends on its relation to the neighbors, as the required condition for a local maximum is a_i > a_{i-1} and a_i > a_{i+1} (reverse signs for a minimum). Now when swapping elements at given positions l and r, this will affect the status of the elements at positions l-1, l, l+1, and r-1, r, r+1 (note that these triplets may partly overlap).

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

can't we solve problem b using tries

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

Спасибо за быстрый разбор :)

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

I am looking details description of solution D or a video tutorial

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

    Isn't the solution of problem D detailed enough?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    /*
    *       For every endPoint, add the number of ways to choose k segments
    *       Such that the segment(call it p) with that endpoint is one of the k segments
    *       Which basically leaves you to choose the k-1 segments that pass through
    *       that endpoint, other than p.
    */
    

    This is the implementation. Hope it helps.

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

I've succesfully uphacked myself. Turns out I forgot to check if all ai are different and still passed systests :D

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

Can anyone please explain why my code for Problem D got Accepted when I used fastI/O but was getting TLE without using fastI/O even after that fact that the question had just one testcase per testfile?

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

C1 was already on internet. Make this contest unrated https://tkramesh.wordpress.com/2009/10/08/maximum-alternating-sum-subsequence/

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

    C1 is a standard dp problem, you can't argue on that basis to make the contest unrated. It is difficult to make new problems and very easy to make new accounts.

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

      I agree making a new problem is a difficult task but at least we shouldn't use the same language as has been used on other sources. Just googling "maximum alternating sum subsequence" gives you the solution (I googled after seeing this).

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

Can C1 be solved w/o dynamic programming i.e greedy?

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

Is there a typo in the summation of $$$p(A)$$$ for E? Isn't it

$$$\displaystyle \sum_{1 \leq i,j \leq k} f_i \cdot f_j = \left( \sum_{i=1}^k f_i \right)^2 \neq \left( \sum_{i=1}^k f_i^2 \right)^2$$$
»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
Segment tree solution for C2
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i think the time limit for D is really bad, i made this submission in the contest and i got a TLE after it ,i don't know why my code gets TLE is the problem with factor 2? https://codeforces.me/contest/1420/submission/93716363

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

i think the time limit for D is really bad, i made this submission in the contest and i got a TLE after it ,i don't know why my code gets TLE is the problem with factor 2? https://codeforces.me/contest/1420/submission/93716363

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

I really like this kind of editorial where hints are provided rather than directly displaying the solution approach completely. I wish more than more authors adopt this strategy. Also, the problem statements were quite nice. Thank you for the good round and helpful editorials.

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

Well done testers and setters, this was a great contest.

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

thanks for giving hints before solutions, would expect the same for future contests

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

I heard that D was copied from gfg. I was surprised at number of submissions of D

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

An observation free solution for C1 and C2:

First let's try to solve this problem using divide and conquer. On every divide stage, we need the following information for each halve:

  • $$$1 = $$$ Maximum sum subsequence starting with a positive element and ending with a positive element
  • $$$2 = $$$ Maximum sum subsequence starting with a positive element and ending with a negative element
  • $$$3 = $$$ Maximum sum subsequence starting with a negative element and ending with a positive element
  • $$$4 = $$$ Maximum sum subsequence starting with a negative element and ending with a negative element

For the state where $$$R - L = 0$$$,

  • $$$1 = A_l$$$
  • $$$2 = -10^{16}$$$
  • $$$3 = -10^{16}$$$
  • $$$4 = -A_l$$$

In the conquer stage, we need to merge these properties. We can easily do this as follows:

  • $$$1 = $$$ max(1L, 1R, 1L + 3R, 2L + 1R)
  • $$$2 = $$$ max(2L, 2R, 1L + 4R, 2L + 2R)
  • $$$3 = $$$ max(3L, 3R, 3L + 3R, 4L + 1R)
  • $$$4 = $$$ max(4L, 4R, 4L + 2R, 3L + 4R)

Our final answer will be $$$max(1, 2)$$$ over the entire array. This divide and conquer can solve C1. The question is, how do we keep updating this?

Well, in this 'divide and conquer', the conquer part is only $$$O(1)$$$. Therefore, this is a decomposable search problem which can be handled fast by segment trees.

Therefore to AC C2 we can create a segment tree where each node in the segment tree stores the 4 properties mentioned above and the merge function performs the max operations as described above. After this, it's standard.

Time Complexity: $$$O(N + Q \cdot LogN)$$$

You can view my submission for clarity:

https://codeforces.me/contest/1420/submission/93674507

Note: There was a much easier solution using some problem specific observations, but it's always better to have a solution that works on a wider range of cases. I hope this helped :)

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

    To make it cleaner change 2 and 3 to "Maximum sum subsequence of even size starting with a positive element" and "Maximum sum subsequence of even size starting with a negative element", this removes isolated 1L 1R 2L 2R from the max, because the base case turns into 0 (empty subsequence has even size) instead of -10^16.

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

I liked the fact that hints are provided before the full solution. Thank you so much!

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

What is event method mentioned in D's solution?

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

    We intend to keep track of the number of lamps which are switched ON at a particular instance of time,let's call that variable x. Now consider turning ON and turning OFF of each lamps as seperate events.It's intuitive that the numbers of lamps switched ON (variable x) only changes at the time of an event(switching ON or switching OFF of some lamp). Hence we sort all the events in non-decreasing order of their occurence and process them one by one. (Note that for some time T if there are multiple events occuring ,we place the switching ON events before the switching OFF events because the question mentions that lamps are switched ON from li to ri inclusive).

    As we process the events 1by1, if we encounter a switching ON event, x is incremented, otherwise x is decremented.(quite intuitive). Whenever there is a switching on event and x>=k-1 , there are X choose K-1 ways of selecting k-1 lamps ,which cobmined with the current lamp being switched on gives us a new solution of k lamps.(My Submission)

    If you are new to this technique, https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/ is a good introductory problem.

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

      Thanks for your explanation. I had this thought first but hesitated in doing it.

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

      Thank you for the explanation. For anyone who did not get it, an alternate explanation could be that we just have to chronologically sort all that happens and iterate over it while maintaining a counter of the number of bulbs still switched on. Just keep in mind to switch off a bulb after switching on all the bulbs at that instant.

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

I found an AC submission to problem B in my room:

https://codeforces.me/contest/1420/submission/93659129

It has O (n^2) complexity but runs surprisingly fast due to the use of intel vectorization.

Is this possible on AMD processors?

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

    AMD processors have the same instruction set as Intel and support vectorization, so I think it's possible.

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

      Does this mean that we can just pass simple n2 loops like these with this vectorization technique?

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

        Sometimes it helps to fit into time limits, but these cases are not so often. Vectorization improves speed only in constant time, so if I make $$$200'000$$$ instead of $$$100'000$$$, then the $$$O(n)$$$ solution will be two times slower, but vectorized $$$O(n^2)$$$ will become four times slower, because it's still $$$O(n^2)$$$. Additionally, not every solution is good to vectorize.

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

    What is intel vectorization and why this O(n^2) solution passing??

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

      In short, it allow the core perform multiple instructions simutanenously.

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

    OMG!! I tried my luck with the exact same approach but got tle.....Can you plz explain what is Intel vectorization?

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

      You need a new generation of intel cpu e.g. 9th or 10th gen. Older cpus do not support this feature.

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

        So it means who has high processor laptop dont need to worry about time complexity??

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

        Vectorization is available for long time. According to Wiki, AVX2 is supported in Intel CPUs since 2013, and SSE is used for even longer period. Why do you think that only 9th or 10th generations are supported?

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

          I guess so because this code runs on my computer in 6 seconds (intel xeon 6th gen).

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

            1) What compiler are you using?

            2) Did you see the generated assembly?

            If your CPU doesn't support AVX2 instructions and the compiled binary has them, the program will simply crash.

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

              I am using GCC 8.2 Windows, C++14. The compiler bypass all directives and generate the output exe as the same as normal

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

                The compiler bypass all directives and generate the output exe as the same as normal

                Then your compiler didn't produce such instructions. It doesn't mean that CPU is not capable of executing AVX2.

                If you try to compile https://codeforces.me/contest/1420/submission/93659129 with -O2, everything should be optimized and AVX2 will be used.

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

        So does this mean that someone with 9th/10th gen processor can get AC easily by doing 10^10 operations in like 1 second?

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

          It's not true for every program. Vectorization improves the speed much only in the specific parts, like short loops which iterate over the array. You cannot just write #pragma GCC target("avx,avx2") and make any program two times faster. But there are some problems on Codeforces where solutions in $$$O(n^2)$$$ with vectorization passed with $$$n \le 100'000$$$.

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

Clean solution to C1 using maxima minima approach

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

For C2, the answer can be written as $$$\sum_{i=0}^{n}{max(0, a_i-a_{i+1})}$$$, where, $$$a_0 = a_{n+1} = 0$$$. Viewed this way, updates become very easy.

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

Actually , problem E has a solution in only $$$O(N^4)$$$ with simple convex hull trick . You can check my solution here .

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

Can anyone explain to me the problem b's code? why j from 29 to 0?

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

For 1420C2 - Pokémon Army (hard version), instead of storing the local maxima/minima, we actually only need to store the current value of each element.

Why?

Because the best answer we can get can also be represented in

$$$\sum\max(0, a_i-a_{i+1})$$$

If we add an extra $$$0$$$ to the end of the array.

So for each query, we need to check at most 4 pairs: $$$(l-1,l)$$$, $$$(l,l+1)$$$, $$$(r-1,r)$$$, $$$(r,r+1)$$$. Note that there might be duplicates, so we need to use a set to deduplicate.

If the original pair is counted in the current sum, then we subtract it from the sum.

Then we do the swap and check the pairs again. If the new pair should be counted, we just add it to the sum.

I think this solution is clearer than the official one.

AC submission: 93743846

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

    i am getting wrong answer for test case 44 in problem D. please help me out. i have done the same thing as mentioned in editorial most probably. submission : 93742154

    Please help lucifer1004

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

    This solution is really nice :) Do you have an AC submission?

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

    I think it should be $$$\sum max(0, a_{i+1} - a_{i})$$$, $$$i = 0$$$ to $$$n$$$, $$$a_0 = 0$$$ and $$$a_{n+1} = 0$$$

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

      The two forms are equivalent.

      Note that I only add one $$$0$$$ at the end, while you add $$$0$$$ at both front and end.

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

i am getting wrong answer for test case 44 in problem D. please help me out. i have done the same thing as mentioned in editorial most probably. submission : 93742154

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

I really like this editorial providing hints not only solutions.

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

Actually DP solution with $$$O(n + q\sqrt{n})$$$ is also conceivable for C2 although because of hard constraints it gets a TLE. My approach, drawing inspiration from Mo's algorithm, was basically to split the pokemons into $$$\sqrt{n}$$$ segments of size $$$\sqrt{n}$$$ each. For each segment we can calculate following 4 things in $$$O(\sqrt{n})$$$ time (using the approach in C1). 1. Max +- sequence with even number of terms. 2. Max -+ sequence with even number of terms. 3. Max +- sequence with odd number of terms 4. Max -+ sequence with odd number of terms.

Finally we can run the dp on these $$$\sqrt{n}$$$ segments to get the answer in $$$O(\sqrt{n})$$$ time. Now, for every query just swap the pokemons and then recompute the (atmost) 2 segments in which the swapped pokemon lie and finally recompute the DP. For each query this can be done in $$$O(\sqrt{n})$$$ time.

My solution, TLE ofcourse - 93717594

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

Can someone Please explain how to do c2 with segment trees?

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

Why is my code getting runtime error on test 5 of problem c1. I have applied DP using 2d array where dp[i][j] tells answer when i elements are considered with j elements included in subsequence. https://codeforces.me/contest/1420/submission/93757697

I will be obliged if someone helps.

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

    It can happen that $$$n = 3\cdot10^5$$$ in this task. And $$$3\cdot10^5\times3\cdot10^5$$$ is too large to fit into memory on stack, so the program crashes.

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

When will ratings update?

Whats the reason behind the delay?

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

For C2, we can use set to avoid categorical discussions.

set<int>now{l-1,l,l+1,r-1,r,r+1};
for(auto &x:now)
	erase(x);
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Can anyone tell me about the "event metho" which author is referring in solution of D? "It should be noted that p(x) and s(x) can be easily supported using the event method. Then, the total runtime will be O(nlogn)."

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

    The idea is as follows. You have segments $$$[l_i; r_i]$$$ and want to calculate (for example) the number of segments that contain specified points $$$x_i$$$. To do this, you create an array of events:

    • a segment is started (at time $$$l_i$$$)
    • a point is encountered (at time $$$x_i$$$)
    • a segment is finished (at time $$$r_i$$$)

    Then, sort such events by time and process them in sorted order. Now it's easy to keep track of number of open segments in the specified points $$$x_i$$$.

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

I still don't understand the logic behind A Cube Sorting

It is not difficult to see that the answer «NO» in this task is possible when and only when all ai are different and sorted in descending order.

How can one derive such logic

PS — newbie here, want to learn :D

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

    If you know something about bubble sorting, you can think of the worst time complexity of bubble sorting ($$$\frac{n-1 \cdot n}{2}$$$) and its reasons

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

In 1420B- Rock and lever can you explain what this part of the code is doing?

for (int j=29; j>=0; j--) { int64_t cnt=0; for (int i=0; i<n; i++) { if (a[i]>=(1<<j)&&a[i]<(1<<(j+1))) { cnt++; } } ans+=cnt*(cnt-1)/2; }

PS-Newbie Here

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

    if (a[i]>=(1<<j)&&a[i]<(1<<(j+1))) { cnt++; }

    stores the no of ( numbers having their rightmost set bit e.g: 4(binary representation : 001) ,in 4 the rightmost set bit is at index 2(0 indexed) ) .

    • cnt*(cnt-1)/2 part counts the nos satisfying the condition mention in the question for that count.
»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Hello everyone !! I hope you are having a good day!

i tried to make editorial for this round :- https://www.youtube.com/watch?v=uc6mN7BZVbI&list=PLrT256hfFv5WH3U33DuKUzL9fYnVsTGAj

problem solved. -> A , B , C1 , C2 , D

language of communication -> Hindi

programming language -> C++

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

in problem c2 let y be the total number of local maximum and minimum we have now, can we change the parity of the y with an update(swapping two element)?

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

Can someone explain the dp which we have done in ques E. Thanks

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

Can anyone help me with the problem D. I got WA in test 11. Here is my code:93779028

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

    If I am not wrong you have compressed the values but you cannot compress the values in this question. You have to keep them as it is.

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

      Can you explain why I cannot compress the values? I think the values are not important in this problem.

      For example, two segments [1,4] and [2,6] after being compressed will become [1,3] and [2,4], which will not affect the result.

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

Here are video solutions for all problems, including a description of the weird segtree sol for C2

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

Very nice Editorial for problem E. Thanks :). Has anyone solved it using flows?

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

problem D is a nice educational problem thanks :)

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

Why is my code for B failing on 2nd pretest? I have stored the count of occurrences of each MSBs in a map and then have iterated over it to calculate the final count. Link to submission: https://codeforces.me/contest/1420/submission/93796185

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

    Because when you are adding m(m-1)/2s, m can be up to 10^6, so if you set m as an int, it can overflow.

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

I today constucted a easy way to do the C2 problem or C1 problem. The ans is essentially the half of sum of absolute value of adjacent indices. (To work it, we have to add zero at start and end of the array). Now the update is really easy, we have to just remove the old absolute values and add the new ones. This can also handle updates like changing the strength of a indice. See the Ac code for implementation details- AC code

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

Can someone spot why I am getting WA on test 11 in Problem D. Here is my submission. 93837255

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

I like this step by step style of the editorial. Thanks.

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

Can some one tell me why my program is getting wa for 99 test case .Why the asnwer should be 0 for 99 test case ?

include<bits/stdc++.h>

using namespace std; typedef long long ll;

define mod 998244353

const int N = 1000001; using namespace std;

// array to store inverse of 1 to N ll factorialNumInverse[N + 1];

// array to precompute inverse of 1! to N! ll naturalNumInverse[N + 1];

// array to store factorial of first N numbers ll fact[N + 1];

// Function to precompute inverse of numbers void InverseofNumber(ll p) { naturalNumInverse[0] = naturalNumInverse[1] = 1; for (int i = 2; i <= N; i++) naturalNumInverse[i] = naturalNumInverse[p % i] * (p — p / i) % p; } // Function to precompute inverse of factorials void InverseofFactorial(ll p) { factorialNumInverse[0] = factorialNumInverse[1] = 1;

// precompute inverse of natural numbers
for (int i = 2; i <= N; i++)
    factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;

}

// Function to calculate factorial of 1 to N void factorial(ll p) { fact[0] = 1;

// precompute factorials
for (int i = 1; i <= N; i++) {
    fact[i] = (fact[i - 1] * i) % p;
}

}

// Function to return nCr % p in O(1) time ll Binomial(ll N, ll R, ll p) { // n C r = n!*inverse(r!)*inverse((n-r)!) ll ans = ((fact[N] * factorialNumInverse[R]) % p * factorialNumInverse[N — R]) % p; return ans; }

int main(){ ll p = 998244353 ; InverseofNumber(p); InverseofFactorial(p); factorial(p); ll n,k; cin>>n>>k; ll a[n][2]; ll ans=0; vector<pair<int,int>>v; for(ll i=0;i<n;i++){ cin>>a[i][0]>>a[i][1]; if(a[i][0]!=a[i][1] || k!=1){ v.push_back({a[i][0],0}); v.push_back({a[i][1],1}); } else{ if(k==1) ans++; } } sort(v.begin(), v.end());

ll count=0;
for(ll i=0;i<v.size();i++){
    if(v[i].second==1){

        count--;
    }
    else{
        count++;
        if(count>=k){
            ans+=Binomial(count,k,mod)%mod;
        }
        if(count-1>=k){
            ans=(ans-Binomial(count-1,k,mod)+mod)%mod;
        }
    }
}
cout<<ans<<"\n";

return 0;

}

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

    The answer is exactly 998244353 in this testcase, and 998244353 % 998244353 == 0 :)

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

      Thank you a lot ....I got AC now.I am actually thinking why the answer is 0 and read question for more than 100 times since morning. Thank you :)

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

In the tutorial of problem E, should $$$z_i$$$ be $$$\sum^i_{j=1}{f_j}$$$? And could you please explain why it takes $$$|z_i-(s+h)|$$$ steps from $$$dp_i$$$ to $$$dp_{i+1}$$$?

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

    In the tutorial of problem E, should $$$z_i$$$ be $$$\sum\limits^i_{j=1} f_j$$$?

    Yes, there is a typo in the editorial.

    And could you please explain why it takes $$$|z_i-(s+h)|$$$ steps from $$$dp_i$$$ to $$$dp_{i+1}$$$?

    Remember the reasoning above on how many steps it takes to transform the array $$$a$$$ into $$$b$$$. It's $$$\sum\limits_{i=1}^n \left|z_i - \sum\limits_{j=1}^n b_j\right|$$$, as shown above. In our DP, we know the array $$$a$$$ and build an optimal array $$$b$$$ step by step. After deciding that the value of the $$$i$$$-th element of the array $$$b$$$ will be $$$h$$$, we say that $$$\sum\limits_{j=1}^i b_j = s + h$$$. So, we add $$$\left|z_i - \sum\limits_{j=1}^i b_j\right| = \left|z_i - (s + h)\right|$$$ to the number of steps.

    Is it now clear for you?

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

      Yes, thanks. I didn't realize $$$dp_i$$$ starts from 0 so I mistook $$$h$$$ as $$$b_{i+1}$$$.

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

        I think there is some inconsistency in the editorial text. $$$s + h$$$ should be of the same "size" as $$$z_i$$$, so there I would rather write $$$z_{i+1}$$$.

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

Can someone please tell me why I am not getting TLE on my solution to problem E?

It seems like magic. I really don't understand how a not very well optimized code like this is working.

Here is the solution link: 93898124.

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

    Isn't it just $$$O(n^5)$$$? You have very straightforward loops, so it should be pretty fast. Switching to plain arrays might speed it up, but otherwise this looks like an intended solution.

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

      Yes, but $$$80^5 > 32 \times 10^8$$$ and therefore, should not work, unless it is optimized heavily.

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

        There is a small constant in front, rep(i,1,cnt+1) rep(j,i,n+1) is $$$n^2/2$$$, rep(p,0,j) further gives $$$n^3/3$$$. $$$10^8$$$ is quite okay, it is also very simple operations inside the loops.

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

Can anyone help me with the reason for this solution getting TLE? Problem c2 https://codeforces.me/contest/1420/submission/93901635

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

In editorial of 1420C1 - Pokémon Army (easy version) and 1420C2 - Pokémon Army (hard version).

The outputs of the editorial codes themselves do not match for the same input test cases. For example,
Input
1
4 0
5 2 2 5

Output (C1 Editorial Code)
8

Output (C2 Editorial Code)
10

I know it's a bit late, but the editorial remains as is. So, this should be corrected.

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

Can anybody explain how this formula is deduced in solution of problem E?

$$$p(A) = \sum_{1 \le i < j \le k} f_i\cdot f_j = \frac 12 \left( \sum_{1 \le i, j \le k} f_i\cdot f_j - \sum_{i=1}^k f_i^2 \right) = \frac 12 \left( \left(\sum_{i=1}^k f_i \right)^2 - \sum_{i=1}^k f_i^2 \right)$$$

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

    We can get this equation in an alternative way:

    $$$\displaystyle\left(\sum\limits_{1 \le i \le k} f_i\right)^2 = \sum\limits_{1 \le i \le k,\ 1 \le j \le k} f_i f_j = \sum\limits_{1 \le i \le k,\ 1 \le j \le k,\ i < j} f_i f_j + \sum\limits_{1 \le i \le k,\ 1 \le j \le k,\ i > j} f_i f_j + \sum\limits_{1 \le i \le k,\ 1 \le j \le k,\ i = j} f_i f_j = $$$

    $$$\displaystyle = 2\sum\limits_{1 \le i < j \le k} f_if_j + \sum\limits_{i=1}^k f_i^2 \implies 2\sum\limits_{1 \le i < j \le k} f_if_j = \left(\sum\limits_{1 \le i \le k} f_i\right)^2 - \sum\limits_{i=1}^k f_i^2$$$.

    In simple words, we take $$$\left(\sum\limits_{1 \le i \le k} f_k\right)^2$$$, which is a sum of pairwise products. Split these pairwise products onto three parts: where $$$i < j$$$, where $$$i > j$$$ and where $$$i = j$$$. The first two parts are equal to $$$\sum\limits_{1 \le i < j \le k} f_if_j$$$, and the last part is a sum of squares. From this we get that $$$2\sum\limits_{1 \le i < j \le k} f_if_j = \left(\sum\limits_{1 \le i \le k} f_k\right)^2 - \sum\limits_{i=1}^k f_i^2$$$, therefore the original formula is also true.

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

      I did not get this part: "$$$\left(\sum\limits_{1 \le i \le k} f_i\right)^2$$$ = sum of pairwise products". Can you explain how?

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

        Okay, do you agree that

        $$$(f_1 + f_2 + f_3)\cdot(f_1 + f_2 + f_3) = f_1(f_1 + f_2 + f_3) + f_2(f_1 + f_2 + f_3) + f_3(f_1 + f_2 + f_3) =$$$

        $$$= f_1f_1 + f_1f_2 + f_1f_3 + f_2f_1 + f_2f_2 + f_2f_3 + f_3f_1 + f_3f_2 + f_3f_3$$$?

        (So, we got that $$$(f_1 + f_2 + f_3)^2$$$ is a sum of pairwise products of $$$f_1$$$, $$$f_2$$$ and $$$f_3$$$.

        You can do this for arbitrary number of elements in the same manner.

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

@geopardo in battle lemming soln what does (q-j)*(q-j) mean

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

    As you can read in the editorial, we use the following formula to recalculate the DP:

    $$$ dp_{i+1,\ s + h,\ k + \left|z_i — (s + h)\right|} \text{min=} dp_{i,\ s,\ k} + h^2. $$$

    In my source code q-j is $$$h$$$, so (q-j) * (q-j) is the $$$h^2$$$ addition in the DP. Basically, it's the square length of the next segment.

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

I have an alternative DP solution to problem E. Observe that the answer is at most C(# zero , 2), in stead of counting the good pairs, I count the bad pairs. (The number of bad pairs is the sum of C(len[i] , 2) for each consecutive 0s with length len[i])

Firstly, I considered interval DP, however, we need also keep track with the number of orders, so we have a state at least DP[l <= 80][r <= 80][k <= 80 * 79 / 2], when merging interval, the time complexity is at least O(N^6), so this doesn't seem like a good approach. Then, I consider a left to right solution, let DP[i][j][k][l] = the minimal bad pairs for the first making length of i sequence such that, we have used j orders, and have a length k full of consecutive 0s suffix, and have used l ones. For transition, DP[i][j][k][l] -> DP[i + 1][j][k + 1][l] + k if we put 0 on the (i + 1) th position. DP[i][j][k][l] -> DP[i + 1][abs(pos[l + 1] — (i + 1))][0][l + 1]. where pos[i] is ith one's position in the initial sequence.

Time complexity O(N^5 / 8) Runtime is some thing like O(80 * 80 * 80 * 79 / 2 * 40 * 40) which should be ok for 2 seconds.

My code: https://codeforces.me/contest/1420/submission/95068002

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

I read this blog while upsolving problem E. I want to thank gepardo for such a clear, detailed and well-written editorial. The hints were accurate, the math formulas nice and understandable, the explanations concise, I can even say I enjoyed reading it.

Recently, I've stumbled upon editorials that aren't very good. They're written in a hurry, and sometimes not even clear or complete. This editorial was the exception, and for that, the author deserves recognition. It's a great example of how problem tutorials should be written.

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

My code for problem D is giving me a run time error.

153332275.

Could anyone please tell me what I'm doing wrong here?

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

Can anyone please explain Solution B.Not able to understand it

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

    See my submission: 169305548.

    Let's calculate the first bit that is 1 in every $$$a[i]$$$ from $$$1$$$ to $$$n-1$$$ inclusively going from highest to lowest bit. (function f) Let's call it $$$f(a[i])$$$.

    Observation is: $$$a[i]$$$ & $$$a[j]$$$ $$$>=$$$ $$$a[i]$$$ ^ $$$a[j]$$$ if $$$f(a[i])$$$ = $$$f(a[j])$$$.

    Why? If $$$f(a[i])$$$-th bit in $$$a[j]$$$ is 1 then value of that bit when calulating $$$a[i]$$$ & $$$a[j]$$$ will be 1 and when calculating $$$a[i]$$$ ^ $$$a[j]$$$ will be 0. If $$$f(a[i])$$$-th bit in $$$a[j]$$$ is 0 then value of that bit when calulating $$$a[i]$$$ & $$$a[j]$$$ will be 0 and when calculating $$$a[i]$$$ ^ $$$a[j]$$$ will be 1.

    It's known that when comparing two numbers, first that have 1 bit is bigger. Because $$$2^n$$$ $$$>$$$ sum of all powers of 2 from $$$0$$$ to $$$n-1$$$ inclusively. (I know there is way to write it using LaTex but I don't know how to do it.)

    Hope it helped.

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

Best Editorial!!