Thanks for the fast editorial

I loved the contest, especially problems F and G.

whats wrong with this https://codeforces.net/contest/1692/submission/160657931 P.S. found.

How to solve H without using trees?

**problem H **, also can be solved useing kadane's algorithm.

H can be solved in O(n) just iterating for indexes of each a that is in array. My solution is here

Problem H can use Kadane in a nice way.

Notice that the sum over frequencies of distinct elements is the size of our input array.

We know any subarray endings should be at two elements that have the same value, otherwise, we are pointlessly reducing our answer and we can fix our boundaries to be on the same boundaries.

say if we have XXXLXXXRXXX where [L, R] is the subarray we are considering then there is no point in having the left or right boundaries on Xs since we could improve the sum by restoring boundaries to L and R.

We can make an array of positions for each distinct element and use the observation that the Xs can be compressed together, therefore for each distinct element, such a compression yields a size of array twice the array of all positions for that element.

So our solution boils down to making a compressed array for each distinct element and then applying kadane to it, finally taking the one which gives the maximum answer.

Time complexity is still the order of n as we are effectively applying kadane on twice the input size.

Problem F : O(10^3) preprocessing + O(n) approach Submission

https://codeforces.net/contest/1692/submission/160650500

Here , is my submission for problem G, i didn't get how I am getting wrong answer on testcase 15, can someone please explain fault in my submission?. Thank you.

Solution of H without trees

Instead of doubling and halving, consider the score of a subarray to be the difference between the frequency of $$$a$$$ and the number of elements in the subarray not equal to $$$a$$$. This is done because we will double our score for $$$freq[a]$$$ times and halve it for the rest elements and hence we want this difference to be maximum. Notice that for the best subarray, $$$a = x_l = x_r$$$. The problem can now be solved with dp. Let $$$dp[i]$$$ be the best score for a subarray with $$$l = i$$$ and $$$a = x_i$$$. Then we can see that $$$dp[i] = 1 + max(0,dp[next[a[i]]] - (next[a[i]]-i-1))$$$, where $$$next[x]$$$ is used to store the next occurence of $$$x$$$ on iterating over the dp. The right end can be maintained similarly(if the dp is maximised then $$$right[i] = right[next[a[i]]]$$$.

Submission at the time of the contest — https://codeforces.net/contest/1692/submission/160583853

Can we use sliding window for E by searching total sum minus reqd target in the sliding window?

Solution of H without using segment trees: https://codeforces.net/contest/1692/submission/160692781

Could anyone help me with problem E: Binary Deque? My solution is kind of greedy. I create an array with distances (in numbers of zero entries) between two conseсutive ones. For example, for the sequence: 0 0 1 0 0 0 1 1 0 1, my array is [2 3 0 1 0] (last zero means that we have tail of zeros with length 0). Next, I use two iterators for decreasing the sum of the array choosing at every step iether the head or the tail with zeros and errasing it from my array. I cannot find the mistake and 1st test is OK, but I get WA for the second. If this idea is correct then the solution is O(n). Here the link: 160692840

Can anyone explain the Kadane algorithm approach for the H problem? I am unable to understand what one is exactly trying to do.

Thank you for fast editorial and interesting tasks.

Pretty sure we can do a O(n) solution for E right? I did this. Doesn't use map stl. https://codeforces.net/contest/1692/submission/160607428

anyone please tell me where am i wrong 160716728 problem D

I'm not too fond of the author's solution to problem H, though the problem was great. But no divisional 4 rounds should contain any Data Structure. Here's my solution —

The basic observation is that the problem simply asks us to find, for each element(x) of the given array, the maximum subarray sum on another array(b) where b[i] = 1 if a[i] == x, -1 otherwise.

We can apply Kadane's algorithm for each element lazily. In Kadane's algorithm, the important variables are current sum, current best, and where the best subarray is. So, as we iterate over the array, we evaluate elements one by one and remember these important variables for each element and their last positions, std::map works fine.

And finally, we can just iterate over the map to find the best answer and the desired segment with the same asymptotic, O(n.log(n)). See my implementation if need be.

What is the wrong on my solution Problem E ? im using two pointers to get the best distance from left and right.. 160727889

160731775 : An Elegant solution for Problem H:no segment tree required

Where can I find a tutorial for the standard problem of finding the maximum sum of a subarray?

In D, why is the second for loop running for 2022 iterations?

An alternative solution to problem H without segment tree. Notice that if we choose $$$(a,l,r)$$$, the money we will get is $$$2^{x-(r-l+1-x)}\ =2^{2x-(r-l)+1}\ $$$ ($$$x$$$ is the number of times that $$$ a $$$ appears in round $$$l$$$ to round $$$r$$$). Thus our goal is maximizing $$$2x-(r-l)+1$$$. For a certain number $$$a'$$$, we can create an array $$$b$$$, where $$$b[i]=-i+$$$ $$$2\times$$$(the number of times that $$$ a' $$$ appears in round $$$1$$$ to round $$$i$$$). And the money we will get by choosing $$$(a',l,r)$$$ is equal to $$$2^{2x-(r-l)+1}=2^{b[r]-b[l]+1}\ $$$! On the other hand, it's obviously that if the answer is $$$(a,l,r)$$$, then the dice must show $$$a$$$ in both round $$$l$$$ and round $$$r$$$. Therefore, we only need to consider the rounds where dice show $$$a'$$$ for a certain number $$$a'$$$. Based on the above, the problem can now be solved with time complexity $$$ \mathcal{O}(nlogn)$$$ by using maps and arrays. Checks this code for better comprehension:https://codeforces.net/contest/1692/submission/160769341

when div5 begins to be held? I want a more easier division!

mesanu For Problem H, can you explain how you are updating and calculating the maximum sum subarray having elements -1, 1, and like how you are updating it in log(N). Like in your code what does pref, suf, Val, and sum store, and how your modify function is working as I'm having trouble with these parts. Thank you.

Here's another approach to problem H which is very surprising for me. We can just make store all positions of each distinct value. Then apply the Kadane's algorithm to find the leftmost and the rightmost of each local maximum power of 2. Lastly, just find the maximum of them. Here's the code to what I'm saying: https://codeforces.net/contest/1692/submission/161122830

[Deleted]

Greedy Approach for last question : Gambling ->

Suppose we have this example :

10 
8 8 8 9 9 6 6 9 6 6

First make map< long long , vector> and insert key : [with vector of indexes]

8 : [0,1,2]
9 : [3,4,7]
6 : [5,6,8,9]

then iterate over vector of indexes of each element Initialize res = 1 ( represent power of 2. Initially 1 because for one occurrence we have 1*2)

for 8 : res = 1 ( index 0 )
start iterating from : index 1 
   if gap>0
   subtract gap ( res -= gap (here gap is 0) )
   and add +1 ( for current occurrence )

   index 2 : gap is zero
   so just add +1

   we get res = 3
   this means final money is pow(2,3) = 8

   if at any moment res become <= 0 then set res =1 again (as this is minimum value possible)
Do this for all and record max res

CODE

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define ll              long long
#define pb              push_back
#define For(i,n)        for(int i=0; i<n; i++)
#define Fora(i,a,b)     for(int i=a; i<b; i++)

void solve(){

   ll n;cin>>n;
   vector<ll>v(n);
   For(i,n)cin>>v[i];
   map<ll,vli>m;
   For(i,n){
        m[ v[i] ].pb(i);
   }
   ll a = v[0] , l = 1, r = 1;
   double sum = 1;

   for(auto itr : m){
        vli temp = itr.second;    
        ll siz = temp.size();        
        double res = 1;
        ll start = temp[0];
        Fora(i,1,siz){
            ll gap = (temp[i]-(temp[i-1]))-1 ;
            res -= gap;
            res ++ ;
            if(res>sum){            
                sum = res;
                a = itr.first;
                l = start+1;
                r = temp[i]+1;
            }            
            if(res<1){
                start = temp[i];
                res = 1;
            }            
        }        
   }
   cout<<a<<" "<<l<<" "<<r;

}
int main() {
    int t; 
    cin>>t;
    while(t--){
       solve();
      cout<<endl;
    }
    return 0;}

hi

Another div4 is coming soon

Will participate in next div4

In problem E editorial there is a mistake

here we have to choose largest value of r , not smallest.

What was the logic of 1st Question?

Why this approach failed for problem E:

#include <bits/stdc++.h>
using ll = long long;
using dl = double long;
using namespace std;
const ll MOD = 1e9 + 7;

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

    while (t--) {
        int n, s;
        cin >> n >> s;
        vector<int> nums(n);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];

            sum += nums[i];
        }
        
        if(sum == s){
            cout << 0 << endl;
            continue;
        }
        if(sum == n){
            cout << n - s << endl;
            continue;
        }
        if(sum < s){
            cout << -1 << endl;
            continue;
        }

        int count = 0;
        int zero = 0;
        int i = 0, j = n - 1;
        while(i <= j){
            if(nums[i] == 1){
                count++;
                i++;
            }
            else if(nums[j] == 1){
                count++;
                j--;
            }
            else{
                i++;
                j--;
                zero++;
            }

            if(sum - count == s) break;
        }

        cout << count + zero << endl;
    }

    return 0;
}

In the solution of D, why the 2nd for loop is running 2022 iterations?