Done Sir.

i did it and finally get a positive delta lol

Ate this too much!!, Hope to reach specialist in this round.. After performing like specialist in some rounds, there comes one round such that sometimes I am not able to perform as expected. It's all about consistency.. Will try my best in tomorrow's div 4 round. Wish me luck :)

Just don't participated live and give it virtually after contest. Ez Win.

Also my first unrated!

As a tester, I want more upvotes than Gheal.

Insha Allah.

Good luck.

THANK YOU SlavicG GUGUSTIUC

yes it will be rated for you. however, you will not be included in official standings because you have participated in < 5 rated rounds. this round is rated for all people with rating < 1400

Yes

The world doesn't work that way brother.

omg prvocislo tester

dude you forgot your signature

or in any of the last 3 contests

35

You waste your mother's time for nine months.

Marinush

Seems like lazy propogation on segment tree. Calculating the value is O(1) as sum of digits would convert to a single digit in 2-3 operations.

You can either solve it using Fenwick tree like I did, or there's an alternative approach as well which doesn't use trees at all.

The sum of digits operation will only be applied at most 3 times on $$$a[i]$$$. So, make an 3 arrays, the $$$1st$$$ one will be storing the numbers obtained by using the sum operation on all $$$a[i]$$$ once, the $$$2nd$$$ one is when the sum operation is used twice, and similarly for $$$3rd$$$.

Now, all you need to do is to check for all $$$i$$$ in $$$[l,r]$$$ how many times it occurs.

I solved it with dsu

I observed that a number will not be updated many times so that I let a number to be updated no more than ten times.

When the number of updates for a particular index reached >10 I will make the parent[i]= findparents(i+1)

Using the above approach whenever an index would be encountered for greater 10 times it will be skipped to the next index and then with the help of dsu I will reach the required index

My submission — https://mirror.codeforces.com/contest/1791/submission/191990981

time complexity will O(n*10+q)

E was one liner after some simple observation.

Elegant solution for problem E:
- If number of negative numbers is even then maximum possible sum will be sum of absolute value of all array elements. - If number of negative numbers is odd then maximum possible sum will be sum of absolute value of all array elements except absolute minimum one minus absolute minium one.

Done

F was some standard stuff after you know it will take atmost 3 op to reduce the no to the final form.

me too lol.

The return value of your sol functuon is int instead of long long.

Sir it was int overflow

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

long long sol(int n, vector<long long>& v){
    long long qneg = 0, min_mod = 2e18;
    long long abs_sum = 0;
    for(int i = 0; i < n; ++i){
        if(v[i] < 0) {
            qneg++;
            v[i] = v[i] >= 0 ? v[i] : -v[i];
        }
        abs_sum += v[i];
        min_mod = min(min_mod, v[i]);
    }
    if((qneg % 2 == 0)) return abs_sum;
    return abs_sum - 2 * min_mod;
}

int main() {
    int t; cin >> t;
    for(int i = 0; i < t; ++i){
        long long n; cin >> n;
        vector<long long> v(n);
        for(long long& x : v) cin >> x;
        cout << (long long)sol(n, v) << '\n';
    }
    return 0;
}

I could not find the template for range update and point query. I could only manage to find for point update and range query smh.

ok, I hack it myself. this is my first hack >W<

You are only calculating up to two operations for every number, while there are numbers like $$$999\ 999\ 988$$$ which become 1-digit numbers only on the third operation.

Look at the editorial. The intended solution doesn't use segment trees.

Segment Tree is one of the ways of doing it.

no

Thank you

• First, take -3 and -1 as a boundary, then the array will become -1 -2 3 4 1 -2 -3
• Next, take -2 and -2 as a boundary, then the array will become -1 2 3 4 1 2 -3
• Last, take -1 and -3 as a boundary, then the array will become 1 2 3 4 1 2 3

You can make all the element in $$$[l,r]$$$ positive if $$$a_l<0$$$ and $$$a_r<0$$$ and $$$a_{l+1} \cdots a_{r-1}$$$ are positive, so it is not correct to take neighboring elements.

first loop should be upto n-1

You can check my answer

    int n;
    set<int>h1; set<int>h2;
    cin >> n;
    char c[n]; int ar[n];
    for(int i=0; i<n; i++){
        cin >> c[i];
        h1.insert(c[i]);
        ar[i]=h1.size();
    }
    for(int i=n-1; i>0; --i){
        h2.insert(c[i]);
        ar[i-1]+=h2.size();
    }
    sort(ar,ar+n);
    cout << ar[n-1];

Your code hacked by me :)

I'll assume you read the editorial for F but could not understand that solution, so I'll go ahead and try to explain another approach.

For each position i, we need to know how many times that position was modified by the operation. For queries of type 1, we get an interval [l, r] and we need to apply the operation on every position i from l to r. But how do we do that?

We could have an array initially filled with zeros to maintain a counter of how many operations were done for each position. Say, for n=5, this array would start as [0, 0, 0, 0, 0], and if we got a query of type 1 in the interval [3, 5], our array would update to [0, 0, 1, 1, 1], as we did one operation on positions 3, 4, and 5.

Now, a simple way to maintain this operation counter array would be to iterate over each position from l to r, whenever we receive a query of type 1, and add 1 to each position. But straightforwardly doing that would TLE, as it would take O(n) (linear time) to process each query of type 1.

But what if we could do this update operation on our array of counters in O(logn)? That is where the data structure BIT (Binary Indexed Tree, or Fenwick Tree) comes in handy. We can do range updates (say, add 1 to each position from l to r) in O(logn). If this is your first time hearing about this data structure, I suggest you read a bit more about it. It can be a bit daunting to understand at first, but the code is really easy.

Well, now that we can process queries of type 1 in O(logn) time, now we're left with queries of type 2. To process those, we only need to read the value present in our array of counter, for the requested position. After reading this value, we can apply the operation in a straightforward manner, as it is really fast.

Here is my submission to make more sense of what I tried to explain. Please let me know if you have any more questions and I'll try my best to answer them.

The naive approach would be to iterate from $$$l$$$ to $$$r$$$ and apply the changes as mentioned in the statement. However, the time complexity is $$$O(nq)$$$ for this approach which will TLE.

Consider what happens when we apply the operation $$$a[i] := d(a[i])$$$ to an index $$$i$$$ (here $$$d(x)$$$ denotes the sum of digits of $$$x$$$). Clearly, $$$d(a[i])$$$ is $$$O(\log a[i])$$$, since there are $$$O(\log a[i])$$$ digits in $$$a[i]$$$, and each of them is upper bounded by $$$9$$$. So roughly the operation corresponds to doing $$$x \mapsto c \log x$$$.

Intuitively, the idea is that this reduction is huge, and the number of times you will need to apply this operation till you get a single digit number is quite small. At least you can show that every time we apply this operation on a number having at least 2 digits, the number of digits never increases after applying this operation, and in fact it decreases by at least 1 after at most 2 operations. So you need at most $$$18$$$ operations (which is a very loose bound, and the editorial shows that you can replace it by $$$3$$$) under these constraints to get to a single digit number, which satisfies $$$x = d(x)$$$. So after a small number of operations on $$$a[i]$$$, you end up with a single digit number, after which applying the operation on it doesn't change the number.

So let's do this mentally: maintain a (sorted) list of indices which have $$$a[i] > 9$$$. These are the indices on which doing the operation can potentially change the number. When you're applying the update on a range, you find the indices in this list that will need a change (the remaining ones are fine as they are). Let's not think about how we will find the indices at this point. For each index, we will process it at most $$$18$$$ times before it gets out of the list. So overall, the total number of indices considered is $$$18n$$$.

Now using a std::set and lower_bound, you can find and update the (sorted) list in $$$O(\log n)$$$ time per operation.

Rishabh_coder you used the condition : if(c < arr[i]){ break; } , it should be : if(c <= arr[i]){ break; }

not yet

Your code might have significantly matched with someone else's code then. You can check your talks or post about it on a specific blog about same.