Please read the new rule regarding the restriction on the use of AI tools. ×

TheScrasse's blog

By TheScrasse, history, 6 days ago, In English

All the Polygon materials (including the official implementations of all the problems) are here.

2019A - Max Plus Size

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2019B - All Pairs Segments

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

2018A - Cards Partition

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

2018B - Speedbreaker

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2018C - Tree Pruning

Author: wksni
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2018D - Max Plus Min Plus Size

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

2018E1 - Complex Segments (Easy Version), 2018E2 - Complex Segments (Hard Version)

Authors: lorenzoferrari, TheScrasse
Full solution: Flamire
Preparation: franv, lorenzoferrari

Hint 1
Hint 2
Hint 3
Hint 4
Solution

2018F1 - Speedbreaker Counting (Easy Version), 2018F2 - Speedbreaker Counting (Medium Version), 2018F3 - Speedbreaker Counting (Hard Version)

Author: TheScrasse
Full solution: Flamire
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
  • Vote: I like it
  • +117
  • Vote: I do not like it

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

1 minute late editorial?

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

    I created video editorial for Div2D/Div1B: Speedbreaker.

»
6 days ago, # |
  Vote: I like it -14 Vote: I do not like it

:)))) Too fast

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

E was such a good problem, great problemset. im so mad i didnt get C earlier though

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

very interesting problems!!

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

The goddamn C...

»
6 days ago, # |
  Vote: I like it -6 Vote: I do not like it

so fast :O

anyway, good songs :D

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

Thank you so much for the great contest! I loved the problems!

»
6 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Is it just me or was this Div 2, little too difficult?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    i think this is one of the easier ones recently. a and b are pretty simple and c seems hard (atleast it seemed to me) but is actually fairly simple. the rest are pretty standard div2 problems imo

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's just me then I guess. Tbh, I couldn't even solve one lol. I did get the basic idea but could not solve them completely, in first and second question. Anyways thanks for the reply, mate!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think its a bit easier than other div2 , C usually is harder i find it a bit easy i came up with the idea for it very fast but took me some time to fully solve it and b was easy but i spent a lot of time understanding what they want like it took me 40 min just to understand the problem and solve it in like 15min

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was unable to understand the problem B in whole contest and still having WTF it wants, that test case 1 [101,200] making things even harder.

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

To solve the third problem [2018A cards partition], can we use the binary search?

if yes then how to implement the checker function that this size of deck is possible or not

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried but mine didn't work

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

    i thinking no, because the checker is no montonic fuction

    thinking in the primes number and k=0, the 6 can be divide, 7 no, and 8 yes. So the binary search can fail.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think we can't do binary search on no.of decks

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

    consider how you would make the decks, you would put all the cards with the highest frequency first, and then just greedily put all the cards on top of the lowest deck that you own currently, without making any new decks. then in the end if the last "row" you filled wasn't completely filled, you can try filling it with the k coins you have. you can do that if (sum)%x<=k , where x is the size youre checking. i didnt do it with bs, since i couldnt prove that if x doesnt work then x+1 surely wont work. also you have to check that the partition that you made actually uses all cards, you can check this by seeing if the amount of decks you would have would be atleast the frequency of the most frequent card. i hope i explained it well, if its not clear, just ask. also you can check my solution for details, but its very simple

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

    I tried but got WA on pretest 4, I think search space is not monotonic

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

    A binary search on all numbers from $$$1$$$ to $$$n$$$ doesn't work, because the function isn't monotonic, so if some deck size fails, it's still possible for a bigger one to succeed. Consider a case where you have $$$n=5$$$, $$$k=0$$$, and $$$1$$$ card of each type. Clearly, the only possible deck sizes are $$$1$$$ and $$$5$$$, while $$$2$$$, $$$3$$$ and $$$4$$$ fail, but $$$5>4$$$.

    It might be possible to do a binary search on all numbers that divide at least one possible number of cards you can get. I'm not sure about that. In any case, as of now, I'm not aware of any reasonably fast checker function that isn't $$$O(1)$$$ (or easily possible to turn into $$$O(1)$$$ by some precomputation), so this probably isn't a great way to think about the problem.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i tried but wrong 283276768

  • »
    »
    6 days ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    with binary search here

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what does ans+=max(0LL,c*v[i]-sum-ans); in check mean?

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

        if the c*v[i] more than sum then increase all prefixs,ans here is the need from k

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

    i made a checker of O(1) and tried binary search but as function is not monotonic so it fail so i just removed the binary search and then just run a for loop keeping checker then it got accepted so as i used that checker function to check that size is possible or not.. you can check my code for checker function

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How much practice do i need i was stuck at B completely.

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

E1,O(n * sqrt(n) * log^2(n)) got a TLE......sad

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

How to implement E.

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

    here. if you have any questions, just ask

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the only thing i don't understand is how maxwin affects the answer. I was able to implement everything else.

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        maxwin[i] is the maximum depth you can reach if you start going down from the i-th vertex. then when checking for a certain depth x, if maxwin[i] is smaller than x, then i must be destroyed, because the i-th vertex can never become a leaf with depth x, and neither can any node in it's subtree, so the entire subtree must be destroyed, since i counted all the vertices by themselves i just remove a vertex one by one

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

          yes yes brilliant thank you. I was trying to do something like this with prefix sums as well but failed miserably.

»
6 days ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

today's contest just ruined my day (though contest was good)... My submission on C 283251847 is the biggest blunder i had done till now... if i did not tried the binary search && just run a loop my code would be accepted && I might be Cyan today...

when i firstly start to solve this C.. i go for nlogn approach... then make the function 'f' .. but i did not notice function is literally O(1) .. so I could run a O(n) loop...

when i find this 1 minute after contest, I realize this CP is not for me...

(apologies for my poor english)..

»
6 days ago, # |
  Vote: I like it +16 Vote: I do not like it

The intervals in the editorial of F should be $$$[i - a_i + 1, i + a_i - 1]$$$?

»
6 days ago, # |
Rev. 9   Vote: I like it +31 Vote: I do not like it

An alternative solution for Speedbreaker (Div2D):

There are 4 cases:

  1. $$$a_0 < n$$$ and $$$a_{n-1} < n$$$: no solution is possible.
  2. $$$a_0 \geq n$$$ and $$$a_{n-1} < n$$$: This means that $$$a_0$$$ must be the last element that is conquered. We now check how many solutions exist in the interval $$$[1, n-1]$$$.
  3. $$$a_0 < n$$$ and $$$a_{n-1} \geq n$$$: Similar to second case.
  4. $$$a_0 \geq n$$$ and $$$a_{n-1} \geq n$$$: We now want to check if $$$a_0$$$ and $$$a_{n-1}$$$ are valid solutions. $$$a_0$$$ is a valid solution only if we can conquer every city going from left to right. To check if $$$a_0$$$ is a valid solution, create a segment tree $$$b$$$ with $$$b_i = a_i - i$$$. Now do a query on the range $$$[0, n-1]$$$. $$$a_0$$$ is a valid starting city if and only if the result of the query $$$\geq 1$$$. For checking if $$$a_{n-1}$$$ is a valid starting city, do something similar. After that, count the number solutions in the range $$$[1, n-2]$$$.

Submission: 283247155

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did binary search.

    283252824

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cool

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice one!

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

      Can we claim that "if all the cities in the intersection are valid, then any strategy should first visit all the cities in the intersection before visiting other cities"?

      UPD: No

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

    The above observation actually makes the solution much easier,

    Observation 1 : All solutions would lie in a contiguous segment

    Observation 2 : If a segment [l, r] has a solution then a[l] >= r-l+1 and a[r] >= r-l+1

    My proposed solution :

    set l = 0, r = n-1. if exactly one of a[l] or a[r] is >= r-l+1 then reduce the segment by removing that element i.e. segment either becomes [l+1, r] or [l, r-1]. If both a[l], a[r] are >= r-l+1 decrement r. If both a[l] and a[r] < r-l+1 then no solution.

    Claim : The above iteration ends in the leftmost solution.

    We reach a solution because we could just perform the above steps in the reverse order and cover the entire array, By Observation 1, as we always decrement r means that we must have reached the smallest such l.

    Similarly perform the above with incrementing l at each iteration, this gives the largest r such that we can start and conquer all indexes.

    Code for this solution : https://mirror.codeforces.com/contest/2019/submission/283302596

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nice

    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      But why do all solutions lay in a contiguous segment?

      Apart from that, very nice solution!

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

      Adding to it why removing a[l] >=r — l + 1 and a[r] >=r-l + 1 works as the segments get shorter these cities can be still be visited with lesser segment length and pausing at a[l]<r-l+1 or at a[r]<r- l + 1 means we have to stay here and decrease the segment from the opposite end until we get a[l]>=r — l + 1 or a[r]>=r — l + 1 if both are less than a[l]<r-l + 1 and a[r]<r — l + 1 no matter what you we cannot reach this from either end therefore no solution exist at first place.

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

    Hi, I don't get how a city is a valid starting city can be checked? I see some implementations where they are doing l = max(l, i-a[i]+1) r = min(r, i+a[i]-1) but this gives a range of starting cities, that also I don't get, I don't get how can you verify if a city i is a valid starting city, what is the strategy to pick cities if you make i the starting city, I can't understand the editorial, if you don't mind, can you please independently explain a solution to a beginner? In your words as an editorial, take some time for us bro, I solved A, B, C, E and could not understand D till now. Please help dear friend! TELL WHY to whatever you approach, like step by step how you build the solution and how you proved yourself that's working, please help

»
6 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Wasn't div2 E a lot easier for its position?

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

C was tooo gorgeous... Gave it the attempt of my life on Codeforces... Learnt a lot, it was like an adventure... Thank you contest×codeforces

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    literally had the same experience with C, spent like an hour on it and finally got the perfect solution.

    also is your profile picture a reference to the AMV tan(x) by lolligerjor?

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ummm, No, didn't know that such thing existed, but my good name is Tanishq, it kinda sounds like TanX, maybe...Yes!

»
6 days ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

For div2 E i used ternary search on depth...and got wrong answer on test 3.i can not find any wrong case.can anyone hep me 283252293? update: may be this problem can't be solve using ternary search. i got a case

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

woah too fast (:

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

Felt like DIV2B was harder than DIV2C :)

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

Oh wow, my solution to F is completely different. The canonical strategy that I use for an array with a marked interval of possible starting cities is to always go to the city with the shortest deadline and break ties by going left. It seems that the resulting dp is very different (and in particular I don't need to use any division)

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

Obligatory "thanks mr Radewoosh" comment.

div1E is https://mirror.codeforces.com/blog/entry/61331

»
6 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Why this code is a incorrect !! My intuition was first find maximum element across the array and then if n is even — n/2 and if n is odd — ((n+1)/2)?!

int main() {
    int t;
    cin >> t; 
    while (t--){
        int n;
        cin>>n;
        vector<int>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int max_value= *max_element(arr.begin(),arr.end());
        if(n==3){
            cout<<arr[0]+((n+1)/2)<<endl;
        }
        if(n%2==0){
            cout<<(n/2)+max_value<<endl;
        }
        else if (n!=3){
            cout<<((n+1)/2)+max_value<<endl;
        }
    }
 
    return 0;
}
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First of all, your n == 3 case should be reconsidered as on test cases:

    1
    3
    1 2 3
    

    Your code says 3 but the answer is max_ele(3) + 2 = 5 As the 1 2 3 you can colour 3 and 1 red having 2 red elements + max_ele(3) will give optimal answer as 5. Moreover, you have to consider the max element being in an odd place having all odd indexes counted elements, or being in an even place having all even indexes counted elements.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about this solution-

      #include<bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      
      int main() {
          int t;
          cin >> t; 
          while (t--) {
              int n;
              cin >> n;
              vector<int> arr(n);
              for (int i = 0; i < n; i++) {
                  cin >> arr[i];
              }
              int max_value = *max_element(arr.begin(), arr.end());
              
              if (n % 2 == 0) {
                  cout << (n / 2) + max_value << endl;
              } else {
                  cout << ((n + 1) / 2) + max_value << endl;
              }
          }
      
          return 0;
      }
      
      
      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1
        5
        1 5 2 3 4
        

        what do you think the answer should be?

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

        you have to check the parity of position of max value

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

It's shocking that so many people in Div1 solved problem C.

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

    i found D1C to be the easiest div1 problem today, looking at my friendlist, most people had the same feeling. It was obvious to me what to do upon reading the problem. Same for D too, I took less time to mindsolve CD combined than either of AB

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      D might be *2200,but C is sure under 1900.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am interested to know your opinion on this. After reading your comment, I spent some more time on problem C, unfortunately I still can't come up with the solution. I haven't looked at the editorial but so far my idea is to consider iterating on the levels of the tree and taking the minimum and for a particular level the answer is N-number of distinct vertices on the path from the root to all the vertices on the current level(I actually figured all this in about ten minutes but I can't think of a way to calculate this in O(n), maybe LCA/inclusion exclusion to avoid double counting I don't know). What do you think one should ideally do in such case? Try for more time or just look at the editorial and be done with it?

      Also, I solved DIV1 A in about 30 minutes and got the idea even fairly quick and spent time only to fix a stupid typo. However, if I didn't already know the fact that we only need to know the max element and total sum to figure out if we can arrange the cards, then I don't think I would have been able to solve the problem. So, for DIV1A I would recommend someone to look at the editorial quite early if they weren't able to solve it. So, my general question is how long do you think should one spend time trying to solve a problem before looking at editorial and what was your strategy when you were at specialist/expert level ?

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

        you are close on C, you just overcomplicated the latter part. Try to think of when a vertex will be deleted instead of its opposite.

        As for when I used to read editorials, it somewhat depends on my progress. If i felt I was close to the answer, I would hold off / read a bit after long time. Otherwise, if i did not make substantial progress, I would read after say 30mins — 1 hour (now its more ofcourse)

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          Thanks for the response! With your hint for C, I managed to solve it myself. I would have solved it in 30-40 min I guess if I thought of this:( Is there a way to count the answer if you look at it my initial way(counting the distinct vertices among all the paths from root to all the vertices at the current level)? Assume if that was what you thought first, Is there any way to recognize that the other way of looking at it is easier/will lead to solution or once you are stuck you just simply switch to looking at when the vertex will be deleted instead of opposite? Asking because I kind of get stuck on one approach like this and fail to solve many solvable problems and would love to get better.

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

            Is there a way to count the answer if you look at it my initial way(counting the distinct vertices among all the paths from root to all the vertices at the current level

            yes, but it will end up being the same thing. We want to charactertize such vertices to easily count them. Its not hard to see that you want to count vertices that satisfy dep_u <= k and max_dep_in_subtree_u >= k

            So, for all k in range [dep_u, max_dep_in_subtree_u], increase the count of saved vertices by 1.

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

              Bro can you explain your intuition for Speadbreaker which is Div1B? I'm unable to build the solution even after reading editorial, like why is it happening? How can you claim that a city i is valid starting city, what is the strategy to pick cities after you fix a starting city and how can you say that this range from l to r is going to be the valid cities, I'm unable to understand @Dominater069

»
6 days ago, # |
  Vote: I like it -8 Vote: I do not like it

can someone please tell me what's wrong with this soln for Div2-B? it gave WA on pretest 9

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

int main(){
    int t;
    cin>>t;

    while(t--){
        int n,q;
        cin>>n>>q;
        vector<int> v(n);
        vector<long long> queries(q);

        for(auto &x:v) cin>>x;
        for(auto &x:queries) cin>>x;

        map<long long,int> mp;

        for(int i=0; i<n; i++){
            long long cnt = 0;  // number of segments this point is part of

            if(i==0 || i==n-1) cnt += n-1;
            else{
                cnt += (n-1+(i*(n-1-i)));
            }

            if(mp.find(cnt)!=mp.end()) mp[cnt]++;
            else mp[cnt]=1;
        }

        for(int i=0; i<n-1; i++){    // considering the points that lie on the axis apart from the ones in the array
            long long cnt = (i+1)*(n-1-i);

            if((v[i+1]-v[i]-1)>0){
                if(mp.find(cnt)!=mp.end()) mp[cnt]+=(v[i+1]-v[i]-1);
                else mp[cnt]=(v[i+1]-v[i]-1);
            }

        }

        for(int i=0; i<q; i++){
            if(mp.find(queries[i])!=mp.end()) cout<<mp[queries[i]]<<" ";
            else cout<<0<<" ";
        }
        cout<<endl;


    }

    return 0;
}
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe integer overflow in the line cnt += (n-1+(i*(n-1-i))); You have taken n and i as int.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i just typecasted at 2 places and it accepted. I thought since cnt is long long, it'll get handled. Can you please suggest some reference where i can clear this concept?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    may be overflow ...using long long in your ans

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

My O(n^5) solution (with small constant) passed F1. However it's hard to optimize to O(n^4) or better (Because I solved d1B by a suboptimal solution, which mislead my thinking of F1)

»
6 days ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

EDIT: you can actually do this in $$$O(n)$$$: 283287968. Same idea, but using path counting instead of the first PIE step.

For F you don't really have to think about paths at all, inclusion-exclusion on the arrays is enough (submission 283272424, ignore the unused variable).

Idea one: it's always sufficient to take the "working" interval first.

Idea two: to count the number of arrays of length $$$k$$$ with elements in $$$[1,n]$$$ and every index works, one only needs to make sure the endpoints work. You can just lower bound the elements for a count of

$$$ \frac{\left(n-\left\lfloor\frac{k}{2}\right\rfloor\right)!\left(n-\left\lceil\frac{k}{2}\right\rceil\right)!}{(n-k)!^2} $$$

Now iterate over $$$k$$$. Count the above and consider how to count extensions to arrays of length $$$n$$$ that do not break any of the elements that were supposed to work. You can do this with PIE; to get extensions of length $$$i$$$ get extensions of length $$$i-1$$$ and extend them on either side, then subtract out extensions of length $$$i-2$$$ where you can take the next two elements in either order. (see my solution for the push dp)

Now you have

$$$ ans[k] = \sum_{\text{arrays $$$a$$$}}\#\{\text{intervals $$$I$$$ of working indices in $$$a$$$ with $$$|I|=k$$$}\} $$$

Idea three. the PIE to finish is by subtracting out

$$$\#\{\text{intervals $$$I$$$ of working indices in $$$a$$$ with $$$|I|=k$$$}\}$$$

for each $$$a$$$ with a working interval larger than $$$k$$$. If you know the size of the working interval, you can count this.

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

too fast!!

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

D is a tremendous problem

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest, I explained the entire process of how to do D (div 2) and GPT-o1-mini still couldn't solve it.

Prompt explanation + problem (separately):

In case anyone is wondering, I have written a code with the exact same logic and it is AC. You can check it out on my submissions.

Good news is, despite several attempt and demand of direct conversion of logic to code without adding its own logic, it could not produce a code which solved even TC 1.

This implies GPT-o1 really isn't something we should worry about for now for div 2 and above. Not only can it not think critically, it cannot even follow basic logical instructions.

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

Can someone tell me why I got WA on Test Case 9?

283223987

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

Can anyone tell me which test case will be wrong in this solution of Problem C 283238912 ? Can anyone give me the tc where binary function won't be monotonic??

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

    consider
    5 0 1 1 1 1 1
    your code says 1, but the answer is actually 5. just because 3 doesn't work, doesn't mean that 5 won't.

»
6 days ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

I have a quite different solution for Div2 E. I think it’s quite enriching and gives some insights about an alternate way of thinking hence i will try to present it here. Let’s try to calculate the cost for some fixed final depth(say d) of all the leaves. What do we need to do to make the depth of all the leaves equal to d? Try to think of it before looking up the spoiler below.

Spoiler

Do the two cases hint you something, how are they related. Do they seem quite similar?

Spoiler

We define two arrays:

1) less[d] : it represents the cost of case 2 for depth d. More formally for some depth d, it represents the cost of removing all leaves with depth less than d to a point where the left tree has no leaf with depth less than d

2) more[d] : cost of case 1 for choosen depth = d(define formally in a similar way)

How do we calculate these for all possible d(0 <= d <= n)

Spoiler

Now the cost for a final depth of d = less[d] + more[d]. Hence take minimum across all the values

You can view my solution for implementation details here : 283261930

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Div2E, can solve using bfs.
iterate level-by-level, each level we can compute the number of nodes not removed.
when a node is a leaf node, need to remove from leaf to it’s parent recursively.

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

what is the "x" in the tutorila of problem C

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Here's a "troll" way to solve F in linear time.

As with some other approaches to this problem, we want to answer the following question: given $$$n$$$ and a width $$$w$$$, compute the sum over all $$$n-w+1$$$ intervals of width $$$w$$$ of the number of ways to pick numbers outside that interval so that all cities in that interval are good, given that the numbers inside that interval are already chosen to make it possible. Now observe, either through a bijective argument or by printing the results from a slower solution, that this quantity only depends on $$$n-w$$$, i.e. it is the sequence $$$1$$$, $$$2$$$, $$$7$$$, $$$34$$$, $$$209$$$, $$$\dots$$$ found in column 1 of the samples. Finally, observe that this is OEIS A002720 which provides a recurrence that computes these numbers in linear time. The rest is straightforward.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The combinatorial interpretation of the sequence is really nice, though. You don't really need to biject with anything new. Basically you have

    $$$ f(n) = \sum_{i=1}^n (i+1)*(n-1)_{(i-1)}f(n-i). $$$

    (the subscript is falling factorial).

    Here $$$f(n)$$$ is the number of ways of expanding by $$$n$$$. Consider this to be the picking the values enumerated by the path as in the editorial. Pick the first fixed point in the sequence to be index $$$i$$$, and choose how much of the suffix is on the right/tight side (options are $$$0$$$ through $$$i$$$). Pick the non-fixed points and recurse.

»
6 days ago, # |
  Vote: I like it +11 Vote: I do not like it
»
6 days ago, # |
  Vote: I like it +21 Vote: I do not like it

Thank you for sharing polygon materials! For future setters, can we normalize this?

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

Very nice problems!

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

Could someone explain the problem div2D for me, as I couldn't understand the editorial.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Query 1: is it pssible to even complete.

    Maintain a lo and hi pointer, initially set to 0 and n-1. Check if either a[lo] or a[hi] >= size of array. Then, increment lo up or hi down, depending on if it was a[lo] or a[hi]. Repeat until lo>hi.

    If this process results in no answer, for any quey, then 0 starting locations will suffice.

    Otherwise, maintain a minStart and maxStart position. Set to 0 and n — 1.

    For each item: minStart = max(a[i]-i,minStart) maxStart = min(a[i]+i,maxStart)

    ans = maxStart — minStart + 1.

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

For problem D(div2) can someone explain this line from the editorial — "At some time t, consider the minimal interval [l,r] that contains all the cities with ai≤t(let's call it "the minimal interval at time t"). If this interval has length >t, the answer is 0."

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you got something??

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

      I still didn't get the editorial's solution. I solved it in a alternative way.

      An alternative solution for Speedbreaker (Div2D): Solution Courtesy: asdasdqwer

      There are 4 cases:

      1.a0<n and an−1<n: no solution is possible.

      2.a0≥n and an−1<n: This means that a0 must be the last element that is conquered. We now check how many solutions exist in the interval [1,n−1].

      3.a0<n and an−1≥n: Similar to second case.

      4.a0≥n and an−1≥n : We now want to check if a0 and an−1 are valid solutions. a0 is a valid solution only if we can conquer every city going from left to right. To check if a0 is a valid solution, create a segment tree b with bi=ai−i. Now do a query on the range [0,n−1]. a0 is a valid starting city if and only if the result of the query ≥1. For checking if an−1 is a valid starting city, do something similar. After that, count the number solutions in the range [1,n−2].

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

Can anyone explain C?

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

It's my birthday and I get -180 as a gift :p sadge

»
6 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Can the editorial writers consider providing some useful thinking process to reach the solution instead of a formal proof of correctness which I don't think is very useful for most readers of the editorials ?

At least, for Div2 A B C D , make it simple and intelligible and actually useful for PROBLEM-SOLVING.

For example, I find editorial for problem C very challenging to follow and honestly not very useful. I Solved this problem before reading the editorial with a very different thinking.

I suggest that the editorial writer for such problems not to be red coder but maybe expert level, or a red coder who has some teaching background.

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

Great contest,was able to solve A-B-C,got the idea of E in the contest but didn't know how to find lca of two node in logn time(though i know that binary lifting is used),after the contest i learned Lca using binary lifting.Basically i calculated distance of root from every node.Let say we fix the level of all the leaf nodes in the tree,total number of edge that u have to remove is nothing but ((n-1)-total number of unique edge that all the node on the particular level pass through)).To calculate the total number of unique edge on a particular level,i iterated through all the node in that level using queue,and added (distance of that node from root-distance of lowest common ancestor of previous node and current node from root).Answer is lowest operation on all the level.

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

how 2F?

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

can anyone help me understand D?

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

:O I see a lot of geometry dash songs in the problem statements

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

in problem E can we solve it ternary search? if no why?

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

can you please include the actual solutions themselves

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

can anyone provide me the dp solution for 1st problem ...did it using greedy but not getting right solution using dp...2019A Max Plus Size

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

For 2018B-Speedbreaker, I have another solution which seems simpler. Consider [1,n] first, we observe that if max(a[1],a[n])<n, then there isn't a valid starting point because 1st or nth must be the last city visited. If a[1]==n, we know that if we start in [2,n], then 1st is the last city and we can only consider cities [2,n]. This implies we can first check whether 1st is a valid starting point or not, and then decrease the question size by one. When considering [l,r] and a[l]>=r-l+1 (we want set l to l+1), l is valid starting point if and only if a[l]>=1, a[l+1]>=2, a[l+3]>=3,...,a[r]>=r-l+1, which is equivalent to a[x]-x>=1-l for any x in [l,r], which can be maintained using Sparse Table. Similar condition for r when we want set r to r-1. This leads to a O(n log n) solution.

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

Could anyone please explain me how to prove this part of C solution: "the maximum number of cards of some type (x ) is ≤m/s"

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

    m = the number of total cards we have after we buy some

    s = the number of elements in each deck

    m/s= the number of decks we have

    so no element can be more than m/s because you have m/s decks only

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

I saw a lot of solutions for problem Div1D. Max Plus Min Plus Size that use DP + Segment tree. Can someone explain those please?

»
5 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Div2 E / Div1 C Tree Pruning
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I might be retarded but once you get the arrays a and b for Div2E/Div1C as mentioned in the editorial, how do you calculate the count of intervals overlapping each 1<=i<=n, at least without using max segment tree with range update or something stupid. I saw a lot of answers using prefix sum and Shayan's video editorial also mentioned prefix sum, but I'm absolutely not able to understand what we are accomplishing with prefix sum.

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

    Problem : find the intersection of the segments.

    Problem Reduction
    Hint 1
    Hint 2
    Solution
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain div2D "speedbreaker" problem ? I am not able to understand it solution ?

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

hello, I am getting wrong answer on test 45, i tried my best but i was unable to find why it is happenning in this Solution, Problem D Name- mouse hunt , in educational round 49,could anyone please help me

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

What is x in the solution of problem C?

»
3 days ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Hi, this is my second account and in this round I was testing my solution to problem A before writing it in my official account and i had no idea that my solution will be skipped if I did this, so can you please accept my solution because as a beginner I was trying hard to solve it and thank you

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

I have a strict $$$\mathcal{O}(n)$$$ approach to the div1C problem, which uses long-chain partitioning to optimize dynamic programming on trees.

283907902

»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone elaborate on Div1.D? I cannot understand the editorial. Thanks in advance!