i_love_penguins's blog

By i_love_penguins, 8 months ago, translation, In English

1935A - Entertainment in MAC

Idea: i_love_penguins
Preparation: i_love_penguins
Editorial: i_love_penguins

Hints
Solution
Implementation on C++
Implementation on Python

1935B - Informatics in MAC

Idea: AndreyPavlov
Preparation: AndreyPavlov, i_love_penguins
Editorial: AndreyPavlov

Hints
Tutorial
Implementation on C++
Implementation on Python

1935C - Messenger in MAC

Idea: i_love_penguins
Preparation: i_love_penguins
Editorial: i_love_penguins

Hints
Solution
Implementation on C++
Implementation on Python

1935D - Exam in MAC

Idea: IzhtskiyTimofey
Preparation: IzhtskiyTimofey
Editorial: IzhtskiyTimofey

Hints
Tutorial
Implementation on C++
Implementation on Python

1935E - Distance Learning Courses in MAC

Idea: IzhtskiyTimofey
Preparation: AndreyPavlov
Editorial: AndreyPavlov

Hints
Tutorial
Implementation on C++

1935F - Andrey's Tree

Idea: AndreyPavlov
Preparation: IzhtskiyTimofey
Editorial: IzhtskiyTimofey

Hints
Tutorial
Implementation on C++

We hope you liked our problems!

  • Vote: I like it
  • +213
  • Vote: I do not like it

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

Very fast editorial

»
8 months ago, # |
  Vote: I like it +91 Vote: I do not like it

I think D is easier than C lol. It takes me nearly 50 mins to come up with C, but only 25 mins on D.

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

    YES

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    D was alot harder for me but that may be just cause I'm bad at math.

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

    Man you are Pro!!

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

    True, my stupid ass got stuck on C but D took me like 10 mins.

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

    Me too, I only used 10 mins actually lol

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

    菜就多练

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

    I have a doubt in the editorial of problem C. When I fix L and R i.e the border values, then why checking only summation of all a_i such that it does not exceed l-(b[r]-b[l]) is sufficient? Shouldn't we also ensure that we have taken a[l] and a[r] in that summation?

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

      Technically speaking, you are right, but it doesn't matter here whether you take it or not,

      Say a[L] and a[R] are not in the cur(from editorial's implementation), say the a[L+d] and a[R-e] (R-e >= L+d) are the leftmost and right most a's included in the cur, then when the loops are at i = L+d and j = R-e this case is going to counted or maybe even bigger subset of a's (since difference of b's is smaller here, than when i = L and j = R, since b's are sorted), hence the multiset s doesn't exactly contain the a's which are considered in the current loop but the answer comes right (a clever implementation !!)

      PS : My submission in contest also works exactly on your line of thinking, you can check that out here 249816460, Although the code is very messy :(

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

        can you please elaborate using an example , I am really struggling to get this point !

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

        thanks, you solved my doubts

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

        Can you plz explain, how your solution is not n^3.logn as you have used while loops (which can go for n iterations every time) inside n^2 loop

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

    what is mistake in this code for problem c It would kind of you if you can figure it out include <bits/stdc++.h> using namespace std;

    define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); define ll long long define pb push_back int main() { fast int t; ll int n, x, a, b, a1, y, j; cin >> t; while (t--) { cin >> n >> x; a = 0; map<ll int, int> m; vector<pair<ll int, ll int>> v(n); for (int i = 0; i < n; ++i) { cin >> v[i].first >> v[i].second; m[v[i].second]++; a += v[i].first; } b = ((*(--m.end())).first — (*m.begin()).first); b += a; while (b > x) { if (v.size() == 1) { v.clear(); break; } j = 0; m[v[0].second]--; if (m[v[0].second] < 1) m.erase(v[0].second); a1 = a — v[0].first + ((*(--m.end())).first — (*m.begin()).first); m[v[0].second]++; for (int i = 1; i < v.size(); ++i) { m[v[i].second]--; if (m[v[i].second] < 1) m.erase(v[i].second); y = a — v[i].first + ((*(--m.end())).first — (*m.begin()).first); if (y < a1) { a1 = y; j = i; } m[v[i].second]++; } a -= v[j].first; m[v[j].second]--; if (m[v[j].second] < 1) m.erase(m[v[j].second]); b = a1; v.erase(v.begin() + j); } cout << v.size() << endl; } }

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

Python implementation, love to see it :)

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

C is much harder than D,I even used a segment tree to solve it.

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

    can you share the solution using segment tree

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

    I solve C,in contest time using a o(n^3) algorithmn.But someone hack me.However,the second day,I solve the problem in a o(n^3) algorithmn again.Using 2.1s to solve the 3s limited problem

»
8 months ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

Problem C can be solved in $$$O(n \log^2{n})$$$ if we use binary search to find the answer.

UPD: Sorry, I was wrong. Yesterday I had an idea of using binary search and I was sure that would work. I even saw some solutions using binary search, so I did not code it. But today I found out they had different time complexities. My bad.

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

    My code with such an asymptotic received a TLE.

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

    Can you explain how?

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

    how

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

      Binary search $$$k$$$ — the size of the subset and check if there is a subarray of length $$$k$$$ with cost no larger than $$$l$$$. The rest is the same with the editorial.

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

        why to check only subarray when we can choose subsequence also ???

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

          I did think in binary search approach but then couldn't prove why subarray selection can be considered optimal instead of subsequence selection. Like, if I am starting at $$$b_{5}$$$ as first element and want to select $$$3$$$ elements, the optimal selection may be by chosing $$$(a_5, a_8, a_9)$$$ instead of $$$(a_5, a_6, a_7)$$$.
          This can happen because $$$a_6, a_7$$$ can be insanely high while $$$b_9$$$ may be only a bit higher than $$$b_7$$$.

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

            i also couldn't figure out why selecting only the subarray works, why not the subsequence??

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

          we are not checking whole subarray here we are checking some elements in the subarray.Here we can use priority_queue or multiset in order to get the maximum number of elements whose sum is less than l-(dif) where dif is the difference between bi value of first and last element of subarray :)

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

        It seems that your own submission is not using binary search. Can you show us your code?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    it also can be solved in O(n^2)

    249837146

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

    Binary Search can be applied: 249807781

    Disclaimer

    Main Idea:

    If we can select a subsequence of size k, so can we select a subsequence of size k' < k. (monotonicity is obvious.)

    Now remains to check if a subsequence of length k exists that doesnt exceed the limit.

    Let's assume we fixed the left and right borders. As pointed out, only the sum of the remaining a-values matters because the b-values are only important if they are on the borders.

    So we need to compute for all subarrays the sum of the smallest k-2 a-values not included in the borders.

    To achieve this, let's iterate over R from 2 to n, set L = R-1 and maintain a multiset that stores the smallest k-2 values currently included in our window. To expand our window, we just need to update the multiset with the a-value of index L.

    Total asymptotics is O(n^2logn). If you have any further questions please don't refrain from asking.

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

IMO C was too hard

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Problem E is a fairly interesting and educational problem, I like it!!!

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Only if I read D before C... xD

»
8 months ago, # |
Rev. 6   Vote: I like it +33 Vote: I do not like it

Really liked the problem B.

  • The key observation that hit me was "the mex of every subarray will actually be the mex of entire array if answer exists."
Why?
  • The 2nd observation was if answer exists, we only need 2 subarrays.
  • In O(N) we can find the mex of entire array.
  • Then pick first subarray starting from index 1 until you have read all numbers from [0, mx).
  • Then find mex for remaining array, and check if it equals to mex of entire array.
Pseudo Code
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice! Same here...for the second one though, I just maintained a prefix array of mexes going from n-1 -> 0. Then, I compute the mex for each $$$i$$$ from $$$0, n$$$ and compare if leftmex == suffixmex[i+1], which is mostly the same as what you're saying, I think! I think the second observation that you only need 2 subarrays was the most useful for me.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    bro really called python pseudocode damn

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Lol. There's subtle differences which make it more valid to call this pseudo-code.

      If it were python,
      1. It would be def solve and not function solve.
      2. set = {} would just create a dictionary object making set.insert(i) invalid.
      3. I am assuming set = {} is a set that only stores distinct integers, which help me in calculating if I have seen all numbers from 0 to mx-1.
      4. getMex is assumed to be well understood and implemented by the user.

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

    Thank You for breaking this down! I was having a hard time understanding the editorial but this makes so much sense.

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

    Bro if 0 is more that two in the array,then 1 is also same but 2 is just 1 then answer should be no?

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

      Yeah, but that approach is not scalable or simplify-able to write code IMO.

      It has lots of corner cases too, I also started with thinking if there's any non-negative number which occurs only once, then answer will be no.

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

        "the mex of every subarray will actually be the mex of entire array if answer exists.",

        If mex is k and k-1 is just one time in the whole array,then answer must be no ?

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

          Yes, that is correct, but it's not useful. Even if $$$k$$$ is the mex and $$$k-1$$$ appears twice, or even if all values in $$$[0, k-1]$$$ appear twice, there might still be no solution, for example $$$a = [0, 0, 1, 1]$$$.

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

            Yeah,after that I will just build my two segment 0 to k-1 first then again 0 to k-1 for the second time.If I can build answer is yes otherwise no.I have already get ac in that way.But thank you for your analysis.

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

    I did it exactly like this and thought authors really messed up with it. Turns out there's a much simpler solution.

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

    why does 0 1 1 return -1?

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

      The mex of the array is 2

      You can't divide it into 2 segments

      [0,1] = 2, [1] = 0

      Not okay. So -1.

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

    Wow u back to cp?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    A typo?

    set.insert(i) should be set.insert(arr[i])

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

    thanks

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Unbelievably fast editorial PLUS 2 language implementations?! Wow -- what an effort by the organizers, thank you!!!

»
8 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

What is wrong with this solution?

void solve(){
    long n;
    string s;
    cin>>n>>s;
    string result;
    if(s[s.size()-1]<s[0]){
        result = s;
        reverse(result.begin(),result.end());
        
        cout<<result<<s<<"\n";
    }else{
        cout<<s<<"\n";
    }
    
    
}
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are only checking for the first character of the string. You should check the whole string. Your code will fail on this string "adba"

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

    You are comparing the first and the last character of the string instead of comparing the complete string with its reverse.

    Consider the string "acba". Take n to be any even number. Now, your code will output "acba", even though "abcaacba" is lexicographically smaller.

    To correct this, check for reverseStr<str instead.

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

      Yeah , the problem was if the last and first are equal I have to keep checking for the condition (s[s.size()-i-1]<s[i])

      Thank you for answering!

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

    thats the same solution as mine

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

    You can try the example acba

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

Problem C was a little too difficult for me to understand. Great round anyways

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C is quite easy for me but unfortunately forgets the case where x+y and y-x equal s in D :(

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

    I am a bit confused, while excluding x + y in S, won't there be some pairs where y — x is also in S, and those are doubly excluded when we calculate the answer for those again?

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

      You can see that when subtracting the set containing (x + y), its common part with the set (y — x) is subtracted once, when subtracting the set containing (y — x), its common part with (x + y) is also subtracted once, meaning we have subtracted the common part twice (with one excess), so we need to add their common part once more

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

B was very nice.

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

C has DP solution in $$$O(n^2)$$$. 249790851

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

    not offending you but what do you expect you are contributing with these comments...most of the people don't understand the code because you know what logic you wrote...it doesn't have comments either. Some understand wrong solutions and concepts get unclear...please if u comment then atleast give a small explanation of ur code

»
8 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

We can solve $$$C$$$ with easy $$$O(n^2)$$$ dp solution. First, sort all pairs by $$$b_i$$$ value.

Now, sum of $$$|b_i - b_{i-1}|$$$ is equal to $$$b_{last} - b_{first}$$$ Let's say $$$dp_{len}$$$ is minimum value of sum $$$a_i$$$. Answer is maximum $$$len$$$, if $$$d_{len - 1} + a_i + b_i \le L$$$.

Base is $$$dp_1 = min(a_1 - b_1)$$$

The transition is $$$dp_{len} = min(self, dp_{len - 1} + a_i)$$$

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    please explain your solution clearly by writing the states then the transitions so that it helps us...these types of comments create in us confusion related to the topics...please answer

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it +13 Vote: I do not like it

      I think I explained it good, maybe some pseudo-code will help you. Ask if it is not

      We must choose maximum lenght subsequence such sum of $$$\sum a_i + max(b) - min(b)$$$ is minimum (we want to choose minimum sum, because we want this sum be not greater than $$$L$$$, if minimum sum is greater than $$$L$$$ it means every sum will be greater than $$$L$$$).

      So, let's iteratate in non-decreasing order of values $$$b_i$$$, for $$$len = 1$$$ we store base $$$d_1 = min(d_1, a_i - b_i)$$$ (because $$$b_i$$$ is minimal value, that is, $$$min(b)$$$. And in formula we get $$$\sum a_i + max(b) - min(b)$$$, so current value $$$b_i$$$ will be $$$min(b)$$$ and we must substract it).

      Now transition is simple: choose previous length and try to add new value in it, increasing lenght by $$$1$$$

      sort pairs by b[i] value 
      d[len] = INF
      
      d[1] = a[1] - b[1]
      for(int i = 2; i <= n; i++) {
         for(int len = 1; len <= n; len++ ){
              check if (len + 1) will be answer after we add a[i] b[i] pair in it
         }
         for(int len = n; len >= 2; len-- ){
              d[len] = min(d[len], d[len - 1] + a[i])
         } 
         d[1] = min(d[1], a[i] - b[i])
         
      }
      
      print ans
      

      Upd: my submission during the contest [here]

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

        Thanks...I got it !! sorry if my comment sounded rude

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          Bro doesn't even try to understand. You just want fast food.

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

Did someone manage to pass a solution with complexity $$$O(n \log A \log n)$$$, where $$$A$$$ is $$$\max(x_i, y_i)$$$, for problem E? My first two solutions with that complexity gave TLE on test 30, but with the TL and the constraints I believe it should be able to pass. Here is my last submission with that complexity, in case anyone is interested: 249817071. I ended up solving it in $$$O(n \log A)$$$ doing the same but with sweepline.

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

    maybe you can try to use scanf to read and printf to print answer. I think your code is correct in time complicity.

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

    Yes, my $$$O(n \log A( \log n+ \log A))$$$ passed with the help of pragmas.

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

    249812906 is $$$n \log n \log A$$$, it passes in 1300ms without any extra optimizations. Feel free to hack if you think you can make it TLE (I might try hacking it myself later)

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

    My O(nlogÂlogn) submission passed in 0.2s with no optimizations.

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

Was n^2log^2 not intended to pass for C? Was going to CM then FST lol.

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

    My n^2log^2 solution passed, but it most likely would not have passed, had I used multiset or some other heavy O(logn) data structure, instead of priority queue.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yeah I used a PST so it's kinda my fault, but I think the TLE case should have been in pretests atleast.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I used a multiset for solving in $$$n^2 (log(n))^2$$$ time and it passed, I think the constant of the time complexity would make a huge difference in this case.

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

Can someone help me in problem C? I am trying to upsolve C and looking at the editorial would be my last option. Till now I have understood the problem and have thought of taking input for the message set as an array of pairs, and will try to sort it firstly on the basis of Api and then on the basis of Bpi and then form sets using dp to find the size of messgaes, Now should I move forward or should I change my approach ? Any hints?

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

    Maybe you should try to sort pairs by $$$b_i$$$ because if you select some pairs and the optimal way to arrange them is sort them with $$$b_i$$$

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

Thanks for the lightning fast editorial

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

C can also be solved using dp, dp[i][j] -> minimin time needed to read exactly j messages where i being the last one. This solution will be O(n^3) TLE but we can optimize it by using prefix dp .AC

»
8 months ago, # |
  Vote: I like it -26 Vote: I do not like it

I really liked problem E, but I misread C so I didn't have the time to implement it :(.

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

My problem E solution(AC after contest) should be $$$O(nlog^3A)$$$ where $$$A$$$ is max grade value (maybe smaller than that, the constant should be really small though). I assumed that for interval that end at $$$r$$$, number of $$$l$$$ that will change the max value is at most $$$log_2(A)$$$, and for each interval $$$[l, r]$$$, the grade that we must consider is also at most $$$log_2(A)$$$ when transition to $$$[l -1, r]$$$.

For those who are interested: 249836964. Feel free to hack!

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

    Meh, I had an $$$O(n \log^3)$$$ solution but decided not to implement because I thought it would TLE.

»
8 months ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it

I have a quite different solution of C. First, sort the array in the non-increasing order of $$$b_i$$$ ($$$b_i >= b_{i+1}$$$).

If we can get a set of size $$$k$$$, we can get a size $$$k-1$$$, so we can binary search on the final answer.

Let the final answer be $$$k$$$ and the set is $$$p1 p_2 ... p_k$$$ => $$$a_{p1} + b_{p1} - b_{p2} + a_{p2} + b_{p2} -b_{p3} .... + a_{pk} + p_{bk}$$$.

The final set is $$$a_{p1} + a_{pk} + b_{p1} - b_{pk} + $$$ the sum of the minimum $$$k-2$$$ values of $$$a$$$ of the selected segement which gives $$$a_{p_2} a_{p_3} ... a_{p_{k-1}}$$$ and we can use a priority_queue or multiset to handle it.

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

    same as mine. We are goofs, the O(n^2) solution was so much easier :skull:

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

      Agreed. We got lucky with the constraints of $$$n$$$. I wasn't able to come up with the O(n^2) solution :'(

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

why does 0 1 1 array in B return -1

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

    Because if you select 0 and 1 1, the mex for first segment is 1, and for the second segment is 0, or if you select 0 1 and 1, the mex on the first segment is 2 and in the second is 0, so again mexs are different.

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for fast editorial

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

In problem C, when I use a vector I get TLE, while when i use an array it gets accepted. Can anyone explain the reason?

https://codeforces.net/contest/1935/submission/249844469

https://codeforces.net/contest/1935/submission/249843979

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

Can anyone explain what's wrong with this idea.

Code

Here dpi1 denotes the maximum number of messages that can be read if ith message is the last one read. dpi0 denotes the minimum time needed to read dpi1 number of messages if ith message is the last one read.

So the answer will be max(dpi1) over all i.

Please someone tell me what's wrong with the above idea/code.

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

C has a simpler solution in O(nsq) where the solution before i can be maintiained in just a vector storing better answer upto i-1

Array a is sorted by b. best stores the min val of (ai+aj+ak...)-(bi) for cnt elements to make ans with a new term az+bz need to be added

        vector<ll>best(n+1,INT_MAX);
        best[1]=(a[0].a-a[0].b);
        for(int i=0;i<n;i++){
            for(int cnt=i+1;cnt>=2;cnt--){
                ll prevmin=best[cnt-1];
                ll cans=prevmin+a[i].a;
                best[cnt]=min(best[cnt],cans);
                cans+=a[i].b;
                if(cans<=l){
                    ans=max(ans,cnt);
                }
            }
            best[1]=min(best[1],(a[i].a-a[i].b));
        }
        cout<<ans<<endl;

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

for C, why the check v[r][0] - v[l][0] + cur > L works.

For the case when we pop a message from the heap that belongs to l or r index, shouldn't we change v[r][0] - v[l][0] to v[r - 1][0] - v[l][0] or v[r][0] - v[l + 1][0]

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

I messed up C, made it $$$O(n^3)$$$. I didn't realise that for a given start value of $$$b$$$. If an element has to be discarded, it just has to be discarded!
I initially thought of a 2 pointer like thing, but discarded it later, and kind of brute forced without considering this fact.


Aside from that: Seems like the demographics have changed!
I remember getting severe negative deltas at such performances (such as mine today, in terms of rank).

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

time travel editorial

»
8 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Can someone help with Problem C ?
The tutorial's O(N^3logN) solution seems correct to me, but I have some hiccups in accepting the O(N^2logN) solution.

My question is in transitioning for (l, r) to (l, r+1)

  1. Answer for (l, r) would be picking as many smaller a's as possible with sum <= L-(a[l]+a[r]+(b[r]-b[l])), lets say you maintain the set S of best a's that fit this equation.
  2. Now, in the transition into (l, r+1) pair, using a[r] is optional. What if a[r] was too high that caused us to remove some good a's in previous iteration from S that could have been used for the solution of (l, r+1).

I know the solution lies where if a[r] was too high, the multiset would have already removed that first, but then, let's be honest, we are not really calculating the exact answer for (l, r) pair in the first place.

Could someone help with a precise explanation here?

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

    In the solution, for the [l,r] interval, we are not maintaining number of smaller a's with sum <= L - (a[l] + a[r] + (b[r] - b[l])).

    Rather, for every interval [l, r], our priority_queue / multiset maintains the list of a's which lie in [l, r], with sum <= L - (b[r] - b[l]). only (which means we do not fix a[l] and a[r] to always be included in the sum).

    Now, 4 cases arise for interval [l, r]:

    1. Both a[l] and a[r] are included in the set of the smallest sum.
    2. a[l] is included but a[r] is not included
    3. a[r] is included but a[l] is not included
    4. both a[l] and a[r] are not included.

    For case 1, we know that this is the best set of a's maintained for [l, r], so we can do mx = max(mx, count) here. For every other case, we have some other interval [l_inner, r_inner] where l_inner and r_inner are indices of the leftmost and the rightmost included a's.

    For every [l, r] interval where case 1 is not applicable, we say that the current count is less than or equal to the count of [l_inner, r_inner] (This is because b[r_inner] - b[l_inner] <= b[r] - b[l] increasing the possible number of items we can pick for the sum within limit).

    So, for any [l, r] where cases 2, 3 and 4 exist, the answer will always be <= answer of [l_inner, r_inner].

    Also, we can see that for the interval [l_inner, r_inner], elements at l_inner and r_inner will be always be chosen in the sum. Since we are looping through all the possible values of l and r, it is ensured that we will calculate [l_inner, r_inner].

    So, this is why we do not need to calculate the exact sum for [l, r], but rather b[r] - b[l] + (sum of a's) <= L.

    Hope this helps and is not too confusing.

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

      In other words $$$\sum a <= L - (b_r - b_l) <= L - (b_j - b_i)$$$ where $$$l <= i <= j <= r$$$. Since we are iterating all possible $$$(l, r)$$$ we are also going over all $$$(i, j)$$$

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

      Great explanation.

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

      Great Explanation!!!

      So our first priority is to maintain all possible gaps/distance [l,r], and for that particular distance we are calculating maximum possible count. (Make Sense).

      I was thinking greddily and why we we not updating [l,r] in the case if we are removing first and last element of subset we are choosing.(We don't required it, we can simply calculate max soln for all possible distance).

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

Why no implementations of E and F in python

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

Can someone tell me what am I missing in C problem ? I sorted in increasing order of b and found the required time for n messages , then I removed the messages one by one , checking which would reduce the time by maximum .. as soon as this sum was getting less than l , I was printing the current number of messages in the set...

249827661

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem F, it can be proved that for any node $$$u$$$, there always exists an optimal set of edges such that there is at most one edge of the form $$$(mx_v, mx_v + 1)$$$, and all other edges are of the form $$$(mn_v - 1, mn_v)$$$ (and possibly one $$$(u - 1, u + 1))$$$.

In fact, we only require an edge of the form $$$(mx_v, mx_v + 1)$$$ when there is some neighbor $$$v$$$ of $$$u$$$ with $$$mn_v = u + 1$$$. In all other cases, it is sufficient to add all the valid $$$(mn_v - 1, mn_v)$$$ edges (and possibly one edge of the form $$$(u - 1, u + 1)$$$) to unite the entire tree.

»
8 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

The phase of the coding journey where you are done with the first div 2 question in maximum 5-10 mins and then spend the next two hours coming up with O(n^5) solutions

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

    Same Solution

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

    Can you explain what you did?

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

      first of all we will store values in a vector<pair<int,int>> v and sort according to bi. (if you don't know why, ask)

      now, my dp[i][j] has following arguments i and j.

      i: chosen subset will end at i. j: chosen subset will have j values

      and dp[i][j] is the minimum cost of choosing optimal subset such that it ends at i and have j values in it.

      answer will be maximum value of all js such that dp[i][j]<=l.

      now transition: well I lied above dp[i][j] is not the minimum cost of choosing the optimal subset but rather it is dp[i][j] = minimum cost — v[x].second. where x is the index of the first value in the subset.

      and it's not only ending at i its minimum cost for all indexes <=i with values count j —

      transition works as follows dp[i][j] = dp[i-1][j-1] + v[i].first + v[i].second.

      a lot of things happened here dp[i-1][j-1] = minimum cost — v[x].second(explained above) is the amongst all the ending indexes < i, such that we get minimum cost — v[x].second so dp[i][j] = minimum cost + v[i].first + (v[i].first-v[x]) now since the b values are sorted only contribution we will get from b is (v[i].second-v[x].second)

      now we will do dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second) (because we want to make it (minimum cost — v[x].second)).

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        what made you choose to sort in accordance with bi

        got it :<)

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

        Wow...your solution was great. I mean thinking of such states and transitions are great. please share some more prblms like this if you have where the state definition is not trivial and transitions require critical thinking...i Specially liked the part where you are using ur dp array to check if it is <= l...and at the next step making it such that it helps in recalculation of next dp states.

        please share more problems like this

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

          this is a common technique where we have to separate f(i) and f(j) if we are dealing with pairs. (here essentially we are dealing with every thing before index j and j) let me give you a trivial example.

          suppose we have been given a array "arr" with some values and we have to calculate no of pairs such that arr[i]*arr[j] = 1 (mod 1e9+7)

          we can just loop in the array store 1/arr[i] (mod 1e9+7) in a hashmap and add and+=mp[arr[i]]; code:

          map<int,int> mp; int ans = 0;

          int inverseMod(int val) for(int i=0;i<n;i++){ ans+=mp[arr[i]]; mp[inverseMod(arr[i])]++; }

          the main idea being used in that dp solution is that only.

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

        upsolving three months later , your explanation is helpful thank you brother

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

      well i did not explain it very clearly if you have any doubt just ask me.

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

        now we will do dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second) (because we want to make it (minimum cost — v[x].second)).

        i don't get it when are you choosing to have v[x].second in dp[i][j] because if choosing ith as optimal then only we should add v[i].second to dp[i][j] so then if it's no optimal it shouldn't be added and shouldn't be subtracted in future

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

          i don't clearly understand your question.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          dp[i][j] before this code "dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second)"

          is taking the following form -> sum of all ai's in the subset + (v[i].second-v[x].second)

          now i am making it dp[i][j] = min(dp[i-1][j], sum of all ai's in the subset-v[x].second)

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Another solution for C using DP and binary search on the solution. https://codeforces.net/contest/1935/submission/249784754

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

Can someone explain why in the editorial of problem C when extracting elements from the multiset the value of v[r].first - v[l].first doesn't get updated? According to the logic, the value of v[r].first - v[l].first will decrease as we remove the greatest element from the multiset.

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

    if you think deeply it still covers all the cases. If we're removing a value of the element and still considering it's b value, this case has already been covered earlier at index with smaller b value which will be optimal than the current one.

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

    I agree. Posted the same query here.

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

I solved B using two pointers: 249886727. It works because mex is monotone by inclusion. Imo your editorial code is quite confusing for beginners. I would scan the array forward and backward instead of inventing how to update mex while removing a number.

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

Problem C

Can anyone tell me what's wrong in my code ? 249887053

logic -> for any range of l and r, we must add a[l] + a[r] + b[r] — b[r] in sum and for remaining we can use priority queue.

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

In problem C, Can someone tell me whether the approach below works somehow?

I thought if I made this array a complete graph, and tried to find the minimum spanning tree starting at each vertex, then the maximum diameter amongst all the MST's should be the answer.

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

For the solution of problem 1935C, when iterating over all $$$(l, r)$$$, the messages $$$l$$$ and $$$r$$$ are certainly read. However, when extracting elements from set s (which contains the $$$a$$$ values of the messages), no care is taken that messages $$$l$$$ and $$$r$$$ are not extracted. Can someone explain this?

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

    If messages $$$l$$$ or $$$r$$$ are removed from the set, we're now calculating the cost incorrectly: the cost we calculate is larger that the true cost, and this might mean that our answer is too small.

    But that is actually never a problem. If $$$l$$$ or $$$r$$$ gets removed when considering the range $$$[l, r]$$$, the range $$$[l, r]$$$ is definitely not optimal ($$$[l, r-1]$$$ or $$$[l+1, r]$$$, depending on which element got removed, would be at least as good as $$$[l, r]$$$). Since we comsider all ranges, including $$$[l, r-1]$$$ and $$$[l+1, r]$$$, we won't miss the optimal solution.

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

      Yes, but it doesn't seem satisfying IMO, I have posted similar doubt comment above.
      Also if element l gets removed, note that though l+1 may have less value in a but it definitely also has bigger b value which helps when its the smallest b. Now the answer to that is, but we will include l+1 in our for loop iteration, so that case gets covered.

      The point here is, this seems to be working only because of many other reasons behind the scenes which are skipped in editorial.

      Would like a cleaner general approach to handle such situations with more clarity without worrying over the behind-the-scenes forces making this work.

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

        Just to avoid all this I didn't include lth element and rth element in the multiset. Instead, I added them explicitly. And guess what I got WA this way. And I ended up not being able to solve the problem in the contest.

        Here is my code : Submission It would be very helpful if you could point out where this code is failing.

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

          I tried the same way and my submission fails at the same test case. This needs rectification.

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

            I was not able to do anything today just to figure out why it is going wrong.

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

            Take a look at Ticket 17407 from CF Stress for a counter example.

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

            I just printed that test case that it was failing for.

            1
            4 4
            1 1
            1 1
            3 1
            1 2
            

            The thing is that when we are fixing lth and rth element we might remove a smaller element that might be useful afterwards just to keep rth element.

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

              Thanks for the clarification

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why not in c we have taken 1st and 2nd minimum value of b . why we have taken max and min value?

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

I tried to use dp for the C, passed the sample cases but got wrong answer. Need some help(´・_・`) My code

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

I am still confused about the formula , $$$\sum_{i = 1} ^ {i = n - 1} |B_i - B_{i+1} |$$$. The formula always gets minimum , as the sequence is ordered. How to proof the formula clearly ???

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

    What proof?

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

      When the sequence of B is odered, why the formula always get minimum ? I want to the reason.Please teach me ,i am willing to know!

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

        I think you misunderstood this. Let's observe formula:

        $$$\sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k-1} (b_{p_i} - b_{p_{i-1}})$$$

        Sum of values $$$a_i$$$ does not require any order, we can just sum them.

        What about sum of differences of $$$b_i$$$, of course, we want to minimize this sum (so that sum is not greater than $$$L$$$)

        Now, we can forget about values $$$a_i$$$ (their sum does not depend on order we choose values). But if we got values $$$b_i$$$, it's always optimal to sort them. For example, $$$b = [1,6,1,5]$$$ gives sum $$$6-1 + 6 - 1 + 5 - 1 = 14$$$, but $$$b=[1,1,5,6]$$$ gives sum $$$1-1 + 5 - 1 + 6 - 5 = 5$$$. Why? You can see abs function $$$|x-y|$$$ as distance beetween two points $$$x,y$$$ on straight line. It's easy to see, that sorting gets the minimum sum.

        Now, we can sort values $$$(a_i, b_i)$$$ by $$$b_i$$$ and choose sum values $$$b$$$ to our answer. Let's closer look at $$$b_j - b_{j-1}$$$, it's equal to $$$b_2 - b_1 + b_3 - b_2 + b_4 - b_3 + ... + b_{k} - b_{k-1}$$$, there are pairs $$$b_2 - b_2 + b_3 - b_3$$$ etc for all $$$i$$$ from $$$2$$$ to $$$k-1$$$, and now this sum equal to $$$max(b) - min(b)$$$

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          i am appreciate your reply! The words resolve my question!

          For example, b=[1,6,1,5] gives sum 6−1+6−1+5−1=14 , but b=[1,1,5,6] gives sum 1−1+5−1+6−5=5 . Why? You can see abs function |x−y| as distance beetween two points x,y on straight line. It's easy to see, that sorting gets the minimum sum.

          Also , you assist me to deepen insigth about the problem. Thank you !

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

            NP! (Not like NP-problems by these authors, but "No problem")

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

              "NP" means "No problem" ? if my guess is right , it is fun and straightforward!

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

          I have one more doubt. While we are selecting the l and r and checking whether the sum of elements in between them is less than l-(b[r]-b[l]), we are taking the sum of some a[i]'s, but the problem is that as soon as we fix l and r, shouldn't we also make sure that a[l] and a[r] are always there in our sum? But proceeding greedily without taking care of them is getting accepted. How is this correct? Please help me with reason why we don't need to make sure that the sum always includes a[l] and a[r].

          Thank You

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

You can solve A without n at all. You just need to find the minimum lexicographic string between the regular string, the inverted string + the usual string, the usual string + the inverted string

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

    You have to use $$$n$$$ in your proof, author's C++ solution don't use $$$n$$$

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

in second how to prove this that if we can not separate array into two segments then it is also not possible for us to do it if the number of segments are increased ?

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

    If there is answer in such $$$k$$$ segments we can always reduce it into $$$2$$$ segments. So, it is not possible to find answer in $$$2$$$ segments, we won't find it in any bigger segments (if there is answer in bigger number of segments, we would reduce it into $$$2$$$ segments and found it there).

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Let us assume for array $$$a$$$, we have a valid partition into $$$k$$$ subsegments $$$S_1, S_2, ... S_k$$$ each having $$$mex(S_j) = m$$$. If we consider merging subsegments $$$S_i$$$ and $$$S_{i+1}$$$ ($$$i < k$$$), the $$$mex$$$ of the new subsegment would also be $$$m$$$ (as it too would contain all elements from $$$0$$$ to $$$m-1$$$ but would not feature $$$m$$$). Continuing this process will lead us to partition array $$$a$$$ into any number of subsegments less than $$$k$$$.

    We can conclude that if there is a valid partition of $$$a$$$ into $$$k$$$ subsegments, a valid partition into $$$x (< k)$$$ subsegments must exist. As a corollary, if $$$a$$$ cannot be partitioned into $$$x$$$ segments, it cannot be partitioned into $$$k (> x)$$$ segments. This would prove your argument for $$$x = 2$$$.

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

I solved C using DP and lazy propagation (I know overkill). Basically $$$dp[i][j]$$$ is the minimum cost to get $$$j$$$ elements in the range $$$[i,n]$$$. Let's sort the elements by $$$b[i]]$$$. In that case $$$dp[i][j] = \min_{k=i+1,k=i+2,...k=n+1} b[k] -b[i] + a[i]$$$. This so far is $$$O(n^3)$$$. We can optimize it by making a segment tree that supports lazy propagation for each $$$j$$$, however that gets MLE. If we iterate over $$$j$$$ we notice that we only care about $$$j-1$$$ so we can use only 2 segment trees. Why do we need lazy? When go from $$$i+1$$$ to $$$i$$$ , the difference between $$$b[i]$$$ and all $$$b[j]$$$ such that $$$j>i$$$ will increase by $$$b[i+1]-b[i]$$$ so we can update them using lazy propagation. The answer is the maximum $$$j$$$ such that there is some $$$dp[i][j] \le l$$$, thus the solution is $$$O(n^2logn)$$$. Code: 249828732

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

Can anyone help me on why I'm getting munmap_chunk() RTE on pretest 1 for Problem C? If I run each test case on the 1st pretest one by one, then there is no RTE! Submission: 249970089

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

Can someone help me with B i have the same idea as editorial but i dont know why iam getting WA here is my code: 249976418

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

    Consider the test case:

    1
    4
    1 1 1 0
    

    This might help.

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

in problem C, when i remove the max element multiset, if i use erase, i WA but i use extract, it AC. Why Ex: mst.erase(mx); (WA) mst.extract(mx); (AC) but when i use extract, my complier ERROR

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

In the author's solution to problem C, can anyone please explain how it is ensured that the end points v[l].second and v[r].second are covered in the multiset and also in the sum $$$cur$$$ (as we are simply removing values greedily)?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think if the multiset is not empty, there must be v[l+a].second($$$a>=0$$$) and v[r-b].second($$$b>=0$$$) in the multiset, so $$$v[r-b].first - v[l+a].first + cur <= v[r].first - v[l].first + cur <= L$$$

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

in problem c, if we add the 'a' value of left element to the multiset , while removing the max element arent we messing up the boundary element? like if left is 0 and its value is (a,b)=(10,1), in future if we remove 10 from multiset we r still holding 0 as left element in the remaining run of the second loop, which seems wrong to me, plz anyone help me to understand this.

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

    this is my code ,the only difference is i am not adding the boundary element to multiset,i dont know why am i getting wa, can someone help me?

    for(i=0;i<n;i++) {

    ll sum=0;
            ans=max(ans,(ll)1);
            multiset<ll>nums;
            for(j=i+1;j<n;j++)
            {
                if(v[i].second+v[j].second+v[j].first-v[i].first>x)
                {
                   continue;
                }
    
                while(nums.size()!=0 && sum+v[i].second+v[j].second+v[j].first-v[i].first>x)
                {
                     sum=sum-*nums.rbegin();
                     auto it=nums.end();
                     it--;
                     nums.erase(it);
                }
                sum=sum+po[j].second;
                nums.insert(po[j].second);
                ans=max(ans,(ll)(pq.size()+1));
            }
        }
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      found what's wrong , i assumed taking the current right element is always best , but its not the case, some times we have to skip the current right element,

      ac code

      for(i=0;i<n;i++)
          {
              ll sum=po[i].second;
              ans=max(ans,(ll)1);
              multiset<ll>nums;
              for(j=i+1;j<n;j++)
              {
                  while(nums.size()!=0 && sum+po[j].first-po[i].first>x)
                  {
                      sum=sum-*nums.rbegin();
                      auto it=nums.end();
                      it--;
                      nums.erase(it);
      
                  }
      
                  sum=sum+po[j].second;
                  nums.insert(po[j].second);
                  if(sum+po[j].first-po[i].first<=x)
                  {
                      ans=max(ans,(ll)(nums.size())+1);
                  }
              }
          }
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same doubt I also have.

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

Why I am getting Runtime Error in the solution of C. I have checked that I am not accessing an unallocated memory. Please help me.

My Submission

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

There is a nice dp way to solve the problem C. After sorting the pairs according to b[i]. lets dp[pos][len][2] be the state. Here pos means any prefix of array dp[pos][len][0] refers minimum possible total cost of any subsequence of length len of the prefix pos and we have stopped taking new value here. and dp[pos][len][1]refers minimum possible total cost of any subsequence of length len of the prefix pos and we will take one or more element to the choosen subsequence. here is my solution link : https://codeforces.net/contest/1935/submission/249842011

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

    My Dp uses only 1 state

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

      yeah its possible to reduce one dimension. Actually i have done this in my solution. I have use this extra dimension for simplification.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You don't have to use DSU or binary search machinery in problem F. You can simply join components as follows:

  1. For each component $$$u$$$ with $$$v<mx_u<n$$$, join $$$mx_u$$$ to $$$mx_u+1$$$. This joins all components extending above $$$v$$$.
  2. For each component $$$u$$$ with $$$1<mn_u<v$$$ that doesn't extend above $$$v$$$, join $$$mn_u$$$ to $$$mn_u-1$$$. Also, if there are any components $$$w$$$ with $$$mn_w<v<mx_w$$$, join $$$mn_w$$$ to $$$mn_w-1$$$ for such a component $$$w$$$ which has the smallest value of $$$mn_w$$$, unless this value is $$$1$$$. You can reason inductively to see that this joins all components which extend below $$$v$$$, either via the edges added in this step or via the edges added in step 1.
  3. This joins everything unless you need to add the edge $$$(v-1,v+1)$$$, in which case, add it.
»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Has anyone done this for C?

For j such that b[j] < b[i]:

$$$ dp(i, cnt) = a[i] + b[i] + min(dp(j, cnt - 1) - b[j] & j < i) $$$

For j such that b[j] > b[i]:

$$$ dp(i, cnt) = a[i] - b[i] + min(dp(j, cnt - 1) + b[j] & j < i) $$$

Answer = max cnt over all dp(i, cnt) such that dp(i, cnt) < l

For finding min(dp(j, cnt — 1) — b[j] & j < i), use range min segment trees over compressed b[i] values. Each cnt will have its own 2 segment trees (one with +b[j], one with -b[j]). Feeling lazy to implement

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

    Update: Misinterpreted that that the chosen indices $$$p_i$$$ need to be in ascending order (Should've seen the first test case explanation smh). This trivially reduces the solution search space as you would obviously sort $$$b_i$$$ values.

    The above solution solves the problem when $$$p_i$$$ must be chosen in increasing order

    Anyway, enjoyed solving this (much) tougher variant although that required me to take 3 hours off a Sat for implementing and debugging

    Code for the variant: https://codeforces.net/contest/1935/submission/250334354

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

For problem E, if n = 2 and y1 = 5 and y2 = 9 and let's consider cases when x1 = 0 and x2 = 0. If we look at the highest bit = 3, then this bit appears twice in numbers <= y2 [number 8 (1000) and 9 (1001)]. I don't think we can set all bits less than 3 in the answer. You can only pick one number out of the two. Here we choose 9. And in order to set all bits to 1 we will have to choose 6 (110) from other number which is not possible. Can somebody rephrase what the editorial is trying to say?

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

    "Suppose we are iterating over bit $$$i$$$, then if such a bit occurs $$$c$$$ times in $$$y$$$ numbers there are several cases:"

    This $$$c$$$ means the number of times that a bit occur in $$$y$$$, not in $$$[0, y]$$$. In your example, when you have $$$y_1 = 5$$$ and $$$y_2 = 9$$$, when we are looking for the highest bit = $$$3$$$, then $$$c = 1$$$, so you put the bit $$$3$$$ in the answer. After that, the next bit is $$$2$$$, that appears once in $$$5$$$, so you put the bit $$$2$$$ in res, then, bit $$$1$$$ doesn't appears in any of them, and bit $$$0$$$ appears both in $$$5$$$ and $$$9$$$, so, the answer is $$$(1101)_2$$$.

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

      Ok, I got confused in the language.

      Another thing is that after removing the values of $$$w_i$$$ we are ignoring the values of $$$x^{'}_i$$$ and only considering $$$y^{'}_i$$$. What allows us to do that? I believe that editorial does not explain that clearly.

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

Edutorial solution of problem B works without
while (mex2 && !cnt2[mex2 — 1]) --mex2; lines.

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

    can you explain the code a little bit

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

      I got it now after reading the code maybe 5 time this part that you talked about is just to make sure that mex2 is correct but it's always going to be correct at this step

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

        I say also that it is always going to be correct

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

Hey, in case any of you are looking for a slightly detailed editorial on Problems B to E, here's my attempt: https://www.youtube.com/watch?v=TrnshSV0qy0&t=5061s&ab_channel=DecipherAlgorithmswithSaptarshi

Btw I got a great comment seeking solution of C in O(n^2) (that I didn't care thinking myself because my O(n^2 * log(n)) worked during contest. But then, putting a thought, I could see that the a very common DP approach — direct Knapsack — would work in O(n^2). I'll consider uploading one video on that, as we all know how much DP knowledge is valuable in these contests.

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

e done using 2d dp :- https://codeforces.net/contest/1935/submission/250851075

clean implementation

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

what is mistake in this code for problem c

include <bits/stdc++.h>

using namespace std;

define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

define ll long long

define pb push_back

int main() { fast int t; ll int n, x, a, b, a1, y, j; cin >> t; while (t--) { cin >> n >> x; a = 0; map<ll int, int> m; vector<pair<ll int, ll int>> v(n); for (int i = 0; i < n; ++i) { cin >> v[i].first >> v[i].second; m[v[i].second]++; a += v[i].first; } b = ((*(--m.end())).first — (*m.begin()).first); b += a; while (b > x) { if (v.size() == 1) { v.clear(); break; } j = 0; m[v[0].second]--; if (m[v[0].second] < 1) m.erase(v[0].second); a1 = a — v[0].first + ((*(--m.end())).first — (*m.begin()).first); m[v[0].second]++; for (int i = 1; i < v.size(); ++i) { m[v[i].second]--; if (m[v[i].second] < 1) m.erase(v[i].second); y = a — v[i].first + ((*(--m.end())).first — (*m.begin()).first); if (y < a1) { a1 = y; j = i; } m[v[i].second]++; } a -= v[j].first; m[v[j].second]--; if (m[v[j].second] < 1) m.erase(m[v[j].second]); b = a1; v.erase(v.begin() + j); } cout << v.size() << endl; } }

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone figure out what is wrong in my solution of problem c

my code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

// ll MOD = 998244353;
// ll MOD1 = 1000000007;

struct box
{
	ll a;
	ll b;
};

box vt[2009];

class comp1
{
public:
	bool operator() (box n1,box n2)
	{
		if(n1.b < n2.b)
		{
			return true;
		}
		return false;
	}
};

ll sol(ll n,ll l)
{
	ll i,j,k,ans,sm,mx,mn,tmx,tmn;
	map<ll,ll> mp;
	map<ll,ll> :: iterator i1,i2;
	multiset<ll> ms;
	multiset<ll> :: iterator i3,i4;

	sort(vt+1,vt+1+n,comp1());
	ans = 0;
	for(i = 1;i <= n;i++)
	{
		mp.clear();
		ms.clear();
		mx = INT_MIN;
		mn = INT_MAX;
		sm = (mx-mn);

		for(j = i;j <= n;j++)
		{
			tmx = max(vt[j].b,mx); // finding new max of b
			tmn = min(vt[j].b,mn); // finding new min of b
			sm -= (mx-mn); // subtracting old difference of max and min of b
			sm += (tmx-tmn)+vt[j].a; // adding new difference of max and min of b along with new a
			mx = tmx; // assigning new max of b to mx
			mn = tmn; // assigning new min of b to mn
			mp[vt[j].a] = vt[j].b; // inserting new a with corresponding b in map
			ms.insert(vt[j].b); // inserting new b in multiset
			while(sm > l) // while sm is greater than l
			{
				i1 = mp.end(); 
				i1--; // finding max a
				i3 = ms.find(i1->second); // finding corresponding b
				ms.erase(i3); // erasing corresponding b
				if(ms.size() > 0)
				{
					tmn = *(ms.begin()); // finding new min of b after erasing
					i4 = ms.end();
					i4--;
					tmx = *i4; // finding new max of b after erasing
				}
				else
				{
					tmx = INT_MIN;
					tmn = INT_MAX;
				}
				sm -= ((mx-mn)+(i1->first)); // subtracting max a and old difference of max and min b
				sm += (tmx-tmn); // adding new differnce of max and min b
				mx = tmx; // assiginig new max of b to mx
				mn = tmn; // assigning new min of b to mn
				mp.erase(i1); // erasing max a from map
			}
			
			k = ms.size(); // finding size of multiset 
			ans = max(ans,k); // findind max size of multiset till now
		}
	}

	// I have tried to implement solution such that max and min b are updated in when we choose best set of a in l to r
	return ans;
}

int main()
{
    ll i,j,testcase,tn,mod;

    // freopen("ip.txt", "r", stdin);
    // freopen("op.txt", "w", stdout);
    testcase = 1;
    scanf("%lld", &testcase);
    for (tn = 1; tn <= testcase; tn++)
    {
        ll n,l;
       	ll ans;
       	scanf("%lld %lld", &n,&l);
       	for(i = 1;i <= n;i++)
       	{
       		scanf("%lld %lld", &vt[i].a,&vt[i].b);
       	}
       	ans = sol(n,l);
       	printf("%lld\n",ans);
    }
    return 0;
}

Update: I found the mistake, I was using a map, instead of map I should use multimap.AC

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

Is it necessary to have this condition while (mex2 && !cnt2[mex2 — 1]) --mex2; in problem B implementation in C++, Can anyone explain this.

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

Sample solution for 1935C - Messenger in MAC should get WA due to integer overflow, but passes tests...

Hack data:

1
2 1000000000
1000000000 1
1000000000 1000000000

Answer is 1 but prints 2.

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

Hm