In problem A, it is also necessary to add 4, since clicks are counted as a separate move

1883E can anyone tell me why in my code i am getting negative output for the first test-case ? SUBMISSION :- 229287818

It's impossible to solve Div3D in Python without implementing custom Multiset :(

Actually, in G2, you don't need binary search. You can just sort the two arrays and pair them up greedily.

Div 1. B can be solved in linear time. https://codeforces.com/contest/1888/submission/229257846

Div2 D2/G2 can be solved in O(nlogn). If we increase a number then we need to check if it satisfies at only 1 index. If currently the number is at a[i], then we can increase a[i] till min(a[i+1], b[removals+i]) without changing the answer. Do some casework. My AC code link

Div. 1 A can be solved with multiset in $$$\Theta(n\log n)$$$: submission

I am beginner,, i stuck in A and cannot proceed further,,Can anyone tell me how to improve myself>

1888E. I'm curious about the cases where my code fails. Code

Div3 D is really misleading. The question doesn't clearly describe the ability to pair l and r randomly.

Two codes below use very similar algorithms but only different data structures, only the first code is accepted:

implement using two multiset left,right:

implement using a multiset<pair<int,int>>

Me — "I can solve it piece of cake" Div 3E ; 'Haha I am E Don't even think' Nice problems and I personally like the experiment :)

Div1 D can also be solved using divide and conquer: https://codeforces.com/contest/1887/submission/229298128

Feeling that 1B=1C=1D=1E. Small difficulty gap. Nice round.

I can't see the English solution to Div1C

1887C — Minimum Array

Unable to parse markup [type=CF_MATHJAX]

Oh my goodness, When I solve Dances (Easy Version), I accidentally mistook 'reorder' in the question for 'record', thinking that the task taught me to store it in a local array—I even thought the question was elaborately detailed!!! Now, I would like to know if there are any algorithms capable of solving this problem without the 'reorder' condition. I tried dp but it seems too difficult, I would be grateful if someone could share some thoughts with me.

Problem 1887C is awesome. I really like the idea of 1887C.

Prob E. AC 229306255 and WA 229307572.

My idea is to use log2. In AC, I use double and ceil, while in WA, I use long long and handle ceil in an alternative manner. Help me

In Div3 C, I calculated the product of all elements in array and if it is divisible by k, then print "0. why is this condition giving WA, because when i removed this(condition) it got accepted?

Can someone explain solution to 1883F? Why it works?

Why not rated -_-

In problem E why do we get TLE if we go naive way multiplying them by 2?

Does anyone have any good SortedList implementation?

I'm wondering is there any C++ implementation without using multiset? I tried using vector and sort after every update but it leads to TLE.

https://codeforces.com/contest/1883/submission/229322842

can anyone tell me where I am going wrong. Any help would be appreciated . Thanks in advance

in 1883B even when we donot not remove all k characters but get the frequencies even we print "Yes"... why?

In F:

Note that a subarray suits us if al is the leftmost occurrence of the number al in the array and ar is the rightmost occurrence of the number ar in the array.

How can we proof this?

In problem Div3, F, I got TLE (submission 229270873) using unordered_map. I replaced it with map (submission 229332985) and it got accepted. Isn't unordered_map supposed to be faster?

There is a fun solution of 1887C using something that is sometimes called Radewoosh trick (https://codeforces.com/blog/entry/62602).

First, let's use the idea of transition to differences array.

Suppose that we are given some array state after several operations. Let's call this STATE. Than, for every state that has ever occured we can find out, whether this state is lexicographically smaller than STATE, or not — we can process change operations in the original order and maintain fenwick tree f, where f[i] = 0 if value in index i in current state is the same to the STATE and 1 otherwise. In order to check, whether current state is lexicographically greater than STATE or not we just need to get first 1 in fenwick and perform one comparison.

After that we can just change STATE to the random state that is lexicographically smaller than STATE. Expected number of such runs is $$$O(\log n)$$$, which gives $$$O(n \log ^ 2 n)$$$ solution, which is fast enough to pass the tests.

My code: https://codeforces.com/contest/1888/submission/229293148.

Can someone tell me, whats wrong with my code for 1883E. am i missing something. i think my logic is correct. thanks 229351983

div2.D2 can be solved in linear time with following algorithm. First, you greedily find minimum number of needed operations with your array 'a' having only n — 1 elements(greedily as until b[j] <= a[i] we decrease 'i' and only then decrease 'j' in previously sorted arrays). So we now found solution in O(n). My idea was that when you try to insert your m at position i(so it stays sorted) following can happen: 1)Because you shifted all elements left of m 1 more place left now their conditions are maybe ruined with their new pairing with a. 2)Your m can be >= b[i + numOfOperations](we paired every a[i] with b[i+numOfOperations] with our greedy method, check for yourself) In both of those cases, we need to increase numofOperations for this m by 1, but let's look at it reversely. Let's say our answer is (numOfOperation + 1) * m so we 'predict' that 1 of these 2 conditions will always hold, so we need to find when it won't. We can deduce that if we start increasing m from 1 and come to a point where first condition disturbs the pairing, it means that it will also disturb it for all m >= current one. But if the second condition happens, it just means we need to shift our search between next two elements in array a.SO, the solution will look like this: 1)Find greedy for starting a and b 2)In every interval between a[i] and a[i + 1], we can fast check for which m-s was our prediction bad(none of 2 conditions happened), which will be for all m-s between a[i] and b[i + numOfOperations] 3)If, at any moment while iterating i, we come to a point where first condition happens, we end the iteration because to fix the pairing from now on, we need to add 1 to every solution, which we already did. Time Complexity:O(n)

thank you for the solution!

229293708 should give tle

how to solve for k=4 in Div 3 problem C raspberries?

In Question 1883 F why I am getting TLE?? 229371473 it's O(n)

The rounds were beautiful, they helped me get to Specialist for the first time! Really glad :D

In Div3 E , You can simply calculate how many 2's in every a[i] and then just calculate the difference of

    a[i-1] - a[i]
if a[i-1]+pre[i] > a[i]

. here pre[i] is number of 2's used earlier !

problem D is a great one, it really confuses me.At a moment I thought a treap or splay was required.

can anybody explain why 1883E giving tle on using brute force multiplying 2 consecutively as the maximum time 2 can be multiplied is 32 times so why tle?

About Div1F,there are some details about the boundries---there should be no $$$nxt_i$$$ equal to $$$r_1$$$,but the editorial didn't metion this,please update your editorial.

I am a python user and wondering how can i solve 1883D In Love question as python don't have the inbuilt feature of multiset.

maybe i play genshin impact to much...

Note that $$$a$$$ subarray suits us if $$$a_l$$$ is the leftmost occurrence of the number $$$a_l$$$ in the array and $$$a_r$$$ is the rightmost occurrence of the number ar in the array.

Could any body explain why this is correct?

In G2. Dances (Hard Version), how to proof the line "changing one element of array a cannot worsen the answer by more than 1"? :")

1883F Anyone know why my solution TLE when i use unordered_map but AC when i use map?

Submission: 229484801

In problem 1883E, can anyone tell me why my code is getting runtime error? My submission

HELP PLS:
https://codeforces.com/contest/1887/submission/229544478
DIV 1 D PROBLEM
I DONT KNOW WHY THIS FAILS AT TESTCASE 29

can someone please explain the test case on which my code will fail on E

submission

Div3 E can be solved easily using logarithm and its properties, Its more optimal and even simpler to understand,.. the code for the same is as follows:

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

//ψ(｀∇´)ψ    TeqArine    ψ(｀∇´)ψ

#define ll long long int
#define yessir cout<<"YES"<<endl
#define nope cout<<"NO"<<endl

int main(){
    //Fast I/O:
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //My Code Here...
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> v(n);
        for(int i=0;i<n;i++)cin>>v[i];

        vector<ll> c(n,0);
        for(int i=1;i<n;i++){
            ll y=(ceil(log2(v[i-1]*1.00/v[i]*1.00)) + c[i-1]);
            c[i]=(y>0?y:0);
        }

        ll out=0;
        for(auto num:c)out+=num;
        cout<<out<<endl;
    }
}

Thanks for such a nice contest. :D

Could someone explain me why the solve of the test case: 3 2 2 3 for the problem 1883F — You Are So Beautiful is 3 and not 4.

there are 4 differeces subsequences ( [2,2] [2,3] [2,2,3] , [3])

could anyone please tell me what is wrong with my submission? submission- 229277838

229682104...In problem e : why this code is giving wrong answer in test case 13 anyone?

Why I m getting TLE ...can anyone please tell me the reason behind the TLE... while(t--){

int n;
        cin>>n;

        vector<int> v(n);
        unordered_map<int,int> l;

        for(int i=0; i<n; i++){
            cin>>v[i];
            l[v[i]] = i;
        }

        unordered_set<int> f;
        ll cnt = 0, ans = 0;

        for(int i=0; i<n; i++){
            if(f.find(v[i])==f.end()) {f.insert(v[i]); cnt++;}
            if(l[v[i]]==i) ans += cnt;    
        }

        cout<<ans<<endl;

    }

// code of the problem F(You are so beautiful)

Can anyone please look into my code and tell me why I am getting WA on Div3.E? I used log_2 to calculate how many twos are required. Code

In part F, using unordered_map resulted in TLE. I had to use a map for it to work

Incase anyone like me find the implementation of others hard for C

void solve(){
    int n, k;
    cin>>n>>k;
    vi a(n);
    
    int mn = inf;
    for(auto &it : a)
    {
        cin>>it;
        int j = it;
        while(j % k != 0)j++;
        mn = min(mn, j - it);        
    }
    if(k == 4)
    {
        mnh minCostToMakeNumberDivisibleTo2;
        for(auto &it : a)
        {
            int j = it;
            while(j % 2)j++;
            minCostToMakeNumberDivisibleTo2.push(j - it);
        }
        if(minCostToMakeNumberDivisibleTo2.size() >= 2)
        {
            int curr = minCostToMakeNumberDivisibleTo2.top(); minCostToMakeNumberDivisibleTo2.pop();
            curr += minCostToMakeNumberDivisibleTo2.top();
            if(curr < mn)mn = curr;
        }
    }
    cout<<mn<<endl;


    
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("error.txt", "w", stderr);    
#endif
fastio();

ll t;
cin>>t;
// t = 1;
while(t--)solve();
return 0;
}

can someone tell me why cant we just delete bad subarrays from total in question You Are So Beautiful.

ll tot=n*(n+1)/2;

    for(auto x : mp) {
        if(x.second.size()==1) {
            continue;
        }

        for(int i=0; i<x.second.size(); i++) {
            if(i==0) {
                tot-=(x.second[i]+1);
            }
            else if(i==x.second.size()-1) {
                tot-=(n-x.second[i]);
            }
            else {
                tot-=n;
            }
        }

    }

    cout<<tot<<"\n";
}   
return 0;

Wonderful problems. Thank you!

Tutorial of 1883E needs correction

If a(i-1) >= a(i), then we say x(i) = x(i) — 1 and add 1 until a(i) * 2 < a(i-1)

Instead of a(i) . 2 < a(i — 1) It should be a(i) . 2 < a(i) Submission link : https://codeforces.com/contest/1883/submission/231445041

Alternate brainless $$$O((n + q)\sqrt{n})$$$ solution for div1-D:

Divide the array into square root blocks. Now for queries spanning only one or two square root blocks we can simply bruteforce in $$$O(\sqrt{n})$$$ time.

For queries spanning > 2 blocks, lets think of how we can efficiently check whether a split point exists within a square root block $$$B$$$ which lies completely within the query.

Let $$$B_l$$$ and $$$B_r$$$ be the left and right bounds of the block $$$B$$$. Let $$$mx(l, r) = max(a_l, a_{l + 1} \dots , a_r)$$$ and $$$mn(l, r)$$$ is similarly defined for the minimum.

Now, for a query $$$(l, r)$$$, a split point $$$S$$$ exists within block $$$B$$$ if $$$max(mx(l, B_l - 1), mx(B_l, S))$$$ < $$$min(mn(S + 1, B_r), mn(B_r + 1, r))$$$.

Claim: For any query $$$(l, r)$$$, a split point is present in block $$$B$$$ if and only if there exists some $$$S$$$ such that the ranges $$$[mx(l, B_l - 1), mn(B_r + 1, r)]$$$ and $$$[mx(B_l, S), mn(S + 1, B_r)]$$$ have a non zero intersection.

Therefore, for every block, we need to create a structure which holds information about a set of ranges of size $$$p = O(\sqrt{n})$$$ and can efficiently answer queries of the form:
Given a range $$$[l, r]$$$ answer whether any range in the set intersects with $$$[l, r]$$$.

We can easily solve this subproblem online in $$$O(p + range)$$$ time with some precomputation.

So, we prebuild this structure for each block in $$$O(n\sqrt{n})$$$ time and $$$O(n\sqrt{n})$$$ memory.

Now each query is answered by firstly brute forcing over the blocks at the edge, and for each block $$$B$$$ which lies completely in the query, we query the structure corresponding to $$$B$$$ to check if the range $$$[mx(l, B_l - 1), mn(B_r + 1, r)]$$$ intersects with anything.

Finally, we achieve a total time complexity of $$$O((n + q)\sqrt{n})$$$ and consume $$$(O(n\sqrt{n}))$$$ memory.

Code: link

Problem F : 232780368

https://codeforces.com/contest/1883/submission/233002798

O(NlogN) solution for G2.

Great round

I solved 1883D - In Love by convert a[i] to log(a[i]) and binary search to find the minimum k that a[i] + k >= a[i-1]. That's so much simple but I love your technique!

include <bits/stdc++.h>

using namespace std; typedef long long ll;

int main() {

int t;
cin >> t;
while (t--)
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        //a[i] &= ((1LL << 64) - 1);
    }
    int k = 0;
    int ans = 0;
    int count=0;
    int store=0;
    if (n == 1)
    {
        cout << "0" << endl;
    }
    else
    {
        for (int i = 1; i < n; i++)
        {

            if (a[i] >= a[i - 1])
            {
                continue;
            }
            else
            {
                int numerator=ceil(log2((double)a[i-1]/a[i]));

                int result=numerator;
                count+=result;
                a[i]*=pow(2,result);
            }
        }
        cout << count << endl;
    }
}
return 0;

}

Can someone please explain that why this solution is giving wrong answer? Also if we use log(2)(a[i-1])-log(2)a[i] instead of log2((double)a[i-1]/a[i]) it gives different answer on some testcase, so what form should we prefer in general?

In problem 1883E (Look Back) the naive way is faster then the optimized way if the input is like that: 1e9 1 1e9 1 1e9 1 1e9 1 1e9 1 So why it get TLE in naive approach?

Could someone please provide the Python code for 1883E? I'm having trouble implementing the idea into Python code. I was able to find a C++ version through Google, but I couldn't find any Python code.

Can somone explain more problem E of div 3 or give us other solution , I didn't understand the editorial .

// Can someone please tell me what's wrong in this code for Problem D

include<bits/stdc++.h>

using namespace std;

define ll long long

define mod 1000000007

// For ordered_set data structure

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

// *s.find_by_order , s.order_of_key typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

ll power(ll a,ll n) // Binary Exponentiation { ll res = 1; while(n) { if(n&1) // n is odd { n--; res = (((res) % mod) * (a % mod)) % mod; } else { n /= 2; a = (((a) % mod) * (a % mod)) % mod; } } return res; }

// Sieve of Erastoshenes const ll N = 100000;
vector sieve(N,0);

// Sieve of Erastoshenes is for Finding divisors of Number void sieveoe() { for(ll i=2;i*i <= N;i++) { for(ll j = i*i;j<=N;j+=i) { sieve[j] = 1; } } }

template inline std::string to_string (const T& t) { std::stringstream ss; ss << t; return ss.str(); }

int main() { ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll q;
cin>>q;
multiset <pair<ll,ll>> ms;
while(q--) {

// for(ll i=0;i<;i++)
   // {
        char ch;
        cin>>ch;
        ll a,b;
        cin>>a>>b;
        if(ch == '+')
        {
            ms.insert({a,b});
        }
        else if(ch == '-')
        {
            auto it = ms.find({a,b});
            ms.erase(it);
        }
        if(ms.size() == 0)
        {
            cout<<"NO"<<endl;
            continue;
        }
        pair <ll,ll> start = *(ms.begin());
        pair <ll,ll> end = *(ms.rbegin());
        if((int)ms.size() and start.second < end.first)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    //} 
}

}

problem G2, $$$O(n\,\,log\,\,n)$$$ with two pointers method. https://codeforces.com/contest/1883/submission/255096685

Idea: Sort both arrays. Only iterating forward, greedily match $$$i$$$ with lowest $$$j$$$ s.t. $$$a[i] < b[j]$$$. Since we can match at most $$$n-1$$$ elements, we will always be left with at least one unmatched in $$$b$$$. Out of all these unmatched, we will save the largest, $$$LU$$$. Denote $$$x = \#(removed\,\,both\,\,in\,\,a,b)$$$. Then for each $$$m >= LU$$$, we use $$$x + 1$$$ operations. And for $$$m < LU$$$, we use $$$x$$$ operations.

Can anyone tell me if the solution of problem B will work for the string "daabdad" when k = 3? Shouldn't the answer be "YES"? But the solution code is printing "NO".