As a problem setter, I'm proud to have made the first (mostly) Serbian Div. 3 round :)

Best tester ever, orz!

now he is the honored two

The answer is !(do you know how to read)

I will be taking part after reading this statement and having faith in your words :). I don't have any rating hopes as I am more interested in enjoying the round :).

Will give my review after the contest !!

Same goes for you :)

yes , bestest

Don't really see why it should? It's just a number. Maybe if it was 1000th.

I promise it will :)

Hope it is the last one too :)

of course

Me too.. missed by 12 pts last round:(

Hopefully I also get to this point someday ^⁠_⁠^

As you take more and more time to get to the answer, Points get deducted

For example a guy who solved a problem in 10 minutes would get better rank than guy who solved at 20 mins(Assuming both solved it correctly in the first submission itself)

But if the 10 mins guy made an incorrect submission before his accepted answer, 10 minutes worth points will be deducted from that problem's points, So in this particular case both 10 and 20 minutes guy will get same points even tho 10 min giy solved it earlier

In Codeforces, you usually lose 0.4% of the task's points for every minute between contest start and submission time, plus 50 points for every failed attempt, the penalty caps out at 70%. Here, the failed attempt penalty is 4% of the total points rather than flat 50 points.

That's for Div. 4

You didn't understand what that part means. Read this.

It was meant to be

I think u should just stop founding problems in others and focus on getting better. U are responsible for every problem in ur life bro :)

just use treap)

could you please explain your reasoning behind F? The only one that came to mind was counting divisors in N^1/3 but couldn't proceed from there?

Answer is "yes" when n is divisible by d(n).
Reason:
lets say if we prime factorize $$$n$$$ then we get: $$$p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*...*p_k^{a_k}$$$
so $$$d(n) = (a_1+1)*(a_2+1)*(a_3+1)*...*(a_k+1)$$$
let $$$x = \frac{n}{d(n)}$$$. so we need to multiply $$$d(n)$$$ with $$$x$$$.
now we can just multiply $$$n$$$ with $$$a = p^{x-1}$$$ where $$$p$$$ is a prime number not contained in $$$n$$$. Thus $$$d(n*a)$$$ will be $$$d(n)*x$$$

ps: I replied to my own comment by mistake lol

just print any odd sequence of length n

No...

It's just counting the number of reversals that cover each index (because the reversals are symmetric wrt the segments, the order doesn't matter), so it can be done with a "sweep line" sort of thing (idk if it's technically a sweep line).

There is a simpler solution.

Also https://cses.fi/problemset/task/2073

Even easier can be done with Treap. Implementation is very simple, so you might as well learn it if you haven't already. Here is my 30-line template, if somebody wants it:

int pri[maxn];
int levo[maxn], desno[maxn];
int sz[maxn];

void split(int v, int &l, int &r, int i) {
    if(v==0) {
        l = r = 0;
        return;
    }
    if(sz[levo[v]] < i) {
        split(desno[v],desno[v],r,i-sz[levo[v]]-1);
        l = v;
    } else {
        split(levo[v],l,levo[v],i);
        r = v;
    }
    sz[v] = sz[levo[v]] + sz[desno[v]] + 1;
}

void merge(int &v, int l, int r) {
    if(l==0||r==0) {
        v = l+r;
        return;
    }
    if(pri[l] > pri[r]) {
        merge(desno[l],desno[l],r);
        v = l;
    } else {
        merge(levo[r],l,levo[r]);
        v = r;
    }
    sz[v] = sz[levo[v]] + sz[desno[v]] + 1;
}

void init(int n) {
    memset(levo,0,sizeof(levo));
    memset(desno,0,sizeof(desno));
    for(int i = 0; i < n; i++) {
        sz[i] = 1;
        pri[i] = rand();
    }
}

Practice Problems:

• https://cses.fi/problemset/task/1737
• https://cses.fi/problemset/task/2073

can you please explain your approach for problem D

Of course it's not the intended solution.

Because yours solution is $$$O(n^2)$$$ lol:)

Fairly sure that is the intended solution, you can't precompute because the value of k varies. Anything else that involves solving bitwise seems much more overkill to me than sparse table / binary search.

I did it using prefix concept and binary search.

You can have a look at the solution https://mirror.codeforces.com/contest/1878/submission/225351971

Yeah, you will see once the editorial is out

If you fix l and iterate over r, then AND will change atmost 32 times. You can precompute the next index at which it changes

Don't use memset, because you will get unnecessary reset when the number of test case is high. Just use for loop to reset the value of "pre" array instead.

It's because you're using memset in each test case which resets the whole array with size $$$N$$$ not size $$$n$$$.

It is LCA + binary lifting. I don't see how ternary search could be applied, though.

My solution may or may not be wrong (feel free to hack because I feel like it's probably wrong and/or too slow and/or too memory inefficient) but what I did was to sweep line on the first/last occurrences of each bit. Implementation requires binary lifting as you said.

LCA + binary lifting don't really seem like a Div. 3 approach, do they?

are you sure ternary search would work? I think binary searching for 30 places. where bit count of left side is exactly i (i from 1 to 30).

can you please explain how would you do ternary search??

I actually think it's a good div3. Not too easy to be speedforces but not too hard to be div2

Yes. My solution is $$$O(n \log n + q \log n \log (\max a_i))$$$

E also can be done in $$$O(q\cdot\sqrt{n})$$$ 225365334

it can be done in q*log(n) using sparse table and binary search.

Actually, you have been a master LOL

Yeah, my C++ 32 bits kept TLEing, but 30 bits passed; I'm such a clown made 4 TLE submissions because of that.

It is ur problem using 32 instead of 30 bits.

It is symmetric for each interval separately, because they are disjoint

Structures are beautiful :)

Also E required prefix sums and that's the only structure on the whole contest lol

E is pref sums or segtree or sparse tables. If pref sums is structure than using arrays is also structure.

i have never used segment tree in any of my contest ever.

my bro you got bullied by the internet lol

wdym, only E is a data structure, and even that can be solved using prefix sums