Last line is gold

I don't think this would change anything for cheaters because they anyway stop competing after getting their desired colour.

1B/2D and 1C/2E were great problems

Problem F was awesome!

F was great

D cooked me. Enjoyed the contest tho.

Nvm, i misread the comment.

Loved the problems, especially D. Thanks to authors!

Relatively simple E, just ran out of time smh

Unpopular opinion but ppl complaining about debugging, corner-cases and hard implementation should probably work on those things rather than blaming the author

Loved the contest! TL too tight on D tho

Anyone else tried solving 2E/1C using binary search?

Great round, thanks to authors!

Can someone explain why 372483665 this submission for B gets WA when it should be getting RE? As far as i can tell, the only problem is that the code is trying to access elements beyond the size of the vector. This verdict costed me precious time during contest :/

Love E

Thanks :)

The code provided for the local testing tool in the Link is a single line of text which Python isn't able to interpret. I got it reformatted from ChatGPT but that doesn't feel like the intended way.

Excited!

Yess, we should double them :P

Preventing $$$O(n log$$$^$$$2$$$$$$n)$$$ solutions in F feels unnecessary.

That makes sense. Thanks!!

I almost didnt submit this code thinking there is no way it’ll pass. Thank god I did xD

My seemingly $$$O(n$$$^$$$3$$$$$$)$$$ Solution works for D2. Idk why. Can it be hacked?

G is awesome

Is it just me or have the runtime limits on CF problems gotten stricter lately?

Dijkstra works on the assumption that the minimum distance in the priority queue will always increase (or stay the same) with time. But having negative edges breaks this assumption.

I couldn't figure out E was

Great problem-setting on this one :)

Loved problem F :)

Also, can u add the feature to add a list of points (and lines also maybe)

Very helpful. Awesome job!

Awesome problems, thanks to authors!!

Thanks to the authors. Loved 2E/1C!

F is a communication problem disguised as an interactive problem haha

Great inspiration, thanks :)

Great contest :)

Great problems!

Pls put it under spoiler because it spoils the problem for ppl just wanting to read general comments here

B was actually awesome!

It's surprising how so many people (including me) found it hard to come up with such a simple idea during contest

This communication format is really awesome. Great to see CF trying out new stuff!

Some explicit clarification from the MHC team would be nice

No, actually the problem turned out to be that I was using -D_GLIBCXX_DEBUG compilation flag and apparently it has massive overhead

C2 and D were great! Thanks for the contest

Are nlogn solutions not supposed to pass for C or is my laptop too slow?

#pragma GCC optimize("Ofast,unroll-loops")
#ifdef LOCAL
#include "snippets/debug.h"
#else
#include <bits/stdc++.h>
using namespace std;
#define debug(...) 42
#endif

#define i64 long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    for (int tc = 1; tc <= tt; tc++) {
        debug(tc, tt);
        int n;
        cin >> n;
        debug(n);
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        vector<int> pre = a, suf = a;
        for (int i = 1; i < n; i++) {
            pre[i] ^= pre[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            suf[i] ^= suf[i + 1];
        }
        map<int, vector<int>> mpp, mps;
        map<int, int> mpr;
        for (int i = 0; i < n; i++) {
            mpr[pre[i]] = 0;
            mpp[pre[i]].push_back(i);
            mps[suf[i]].push_back(i);
        }
        suf.push_back(0);
        i64 ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += i * 1LL * (n - i + 1);
        }
        debug(ans);
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (i % 1024 == 0) debug(i, n);
            auto &v1 = mpp[last];
            int &iidx = mpr[last];
            while (iidx < v1.size() && v1[iidx] < i) iidx++;
            if (iidx < v1.size()) {
                auto idx = v1[iidx];
                auto &v2 = mps[suf[idx + 1]];
                auto itp = lower_bound(v1.begin() + iidx, v1.end(), idx);
                auto its = upper_bound(v2.begin(), v2.end(), i);
                int l = its - v2.begin();
                int r = v1.end() - itp;
                ans -= r * 1LL * l;
            }
            last = pre[i];
        }
        cout << "Case #" << tc << ": ";
        cout << ans << '\n';
    }
    debug(verify);
}

Me too

Ohh right. If some query returns more than n indices then that would be the answer, and if not, then your construction would be present.

Awesome proof, thanks :)

What do u mean by “there will be 1 element left”?

My Solution for E using DAG 341753535

Would be great if someone could prove why it works

Basically, I tried to build a DAG using the queries where each index is a node and edges point from index with smaller value to index with greater value. Then find a path of length n + 1 such that indices on that path are monotonically increasing or decreasing. I'm not sure why a path of length n + 1 always exists in this DAG.

Woahh, thats way simpler than the bs construction I used, thanks xD

Is there a method to come up with a solution for constructives like B? I could only do trial and error.

Great problems tho :)

For finding LCA, this algorithm might take O(log²n) time in some spcific cases (as discussed in comments above) which might not be fast enough to pass tight time limits intented to weed out O(log²n) solutions. But it would work in a lot of cases where the time limit is manageable.

For finding the k-th ancestor, this is at par with regular binary lifting, if not faster.

Also, if the problem has tight memory limit that only allows linear memory (happens rarely), this algorithm beats binary lifting which precomputes with space O(nlog n) compared to O(n) here.

C was great

Also, i didnt get the point of having 10 test cases per test without any limit on the sum of n. That can allow 2e6 input elements with 2 sec limit

I felt like time limit was too tight for D :/

My nlogn solution in cpp TLEed

Good point! It reduces the constant factor almost by half.

Thanks a lot :)

Thanks for noticing! I had thought of mentioning that the actual speed might be faster in most cases, however since the case of the “square” tree with repeated similar queries takes it to O(log² n), I decided to not include that point.

I appreciate u testing the code locally for the “square” case, I hadn’t actually done that xD

Good to hear it’s only a little slower than O(log n)

shuffle points then try points with indices (0, 1), (2, 3), (3, 4)..

Submission

Solved D using ternary search

Submission

Agree. It was a nice problem.

or 6

Great contest, thanks!

Problem D was awesome

Edit: Also, does anyone have a greedy solution for D?

I used binary search 334924908

Idea : Sort both arrays in descending order and try to find i and j such that a[i] and b[j] are as close as possible

Great contest, thanks to the authors!

ATB!

Great contest. Love interactive problems!

AtCoder Educational DP Contest solve this

Exactly

D was great, dk how to solve it tho ToT

F was very cool

Using something like

constexpr long long mod = 1e9 + 7;
inline long long Mod(long long num) {
    num %= mod;
    return num < 0 ? num + mod : num;
}

inline long long Inv(long long num) {
    assert(num > 0);
    num %= mod;
    long long p = mod - 2;
    long long res = 1;
    while (p) {
        if (p & 1) {
            res *= num;
            res %= mod;
        }
        num *= num;
        num %= mod;
        p >>= 1;
    }
    return res;
}

inline long long Add(long long a, long long b) {
    return Mod(Mod(a) + Mod(b));
}

inline long long Sub(long long a, long long b) {
    return Mod(Mod(a) - Mod(b));
}

inline long long Mul(long long a, long long b) {
    return Mod(Mod(a) * Mod(b));
}

inline long long Div(long long a, long long b) {
    return (Mod(a) * Inv(b)) % mod;
}

might help, instead of using +, -, * and / to perform the operations safely. (/ is mostly just useless in case of modular operations)

(I know the above code applies Mod too many times and might increase overhead but I just like to keep the functions safe for big or negative inputs unless the time limit is too strict)

Additionally, avoid using int for variables that store modular values, as multiplication (or addition or subtraction) with big numbers can cause overflow.

As for when and where to apply %, you want to apply it after any operation whose result can be >= mod. If you use the * operator, make sure you don't do more than one multiplication (or addition or subtraction) without modding the previous result. For example,

long long mod = 1e9 + 7;
long long a = 1e9;
long long wrong = (a * a * a) % mod; // gives wrong result since a * a * a is 1e27, which exceeds even the limit of long long
long long right = (((a * a) % mod) * a) % mod; // gives right answer since  a * a = 1e18 is modded immidiately, before exceeding the limit of long long

Also, in case of negative numbers (like result of a subtraction), make sure you you add mod if res % mod returns a negative number.

However if you just use the functions given above, you don't have to pay too much attention to these details.

There might be other ways like using a modular integer class, but this is just what I'm comfortable with. Hope it helps!

Here as well

Kindly consider these during plag check

I enjoyed the problems, different style

Dk what u mean exactly but it sounds super cool!

because u can do the next explosion on some cell adjacent to the last explosions's center and it will collect the gold just outside the last explosions's border, and no extra gold is wasted since u already collected gold from last explosion's border. keep repeating till all cells are covered.

If C can be solved in O(n^2) using 2D prefix sum, why was limit on n kept <= 500?

Very interesting. Thanks!

My solution for 2C passes with int (1.5s) but TLEs with long long :*)

Great problems. Thanks

Great problems, thanks

Great contest. Thanks!

Was the contest way easier than usual?

Just checked out linked lists for sqrt functionality. Very cool. Thanks!

Idt this will last long xD

2077B - Finding OR Sum

I see, but i did it using ordered set in cpp (302954264). So ig linked lists aren't necessary there. Are there any problems where linked lists are inevitable?

Yeah that sounds like a simpler way to implement it than struct

The text "problem-solving heatmap for {User Name}" i feel is unnecessary and takes away from the clean look of the feature. Love the extension tho!

April fools contests feel like magic

Great Job!

Cangrats!! ToT ToT

2C wasn't explained well, lost a lot of time because of it

This is not an exact proof for D, but an intuition for why it's always possible to get the biggest min when we get the smallest max. If we look at the array as a stack of bricks at each position, then we know that bricks can flow from left to right. Now let's look at these operations as transactions. When we are trying to get the smallest max (let's call it mx), we want all the elements that have value greater than mx to sell their bricks to someone. And since mx is the smallest max value, this will generate the highest supply of bricks than any other (bigger) max value. Similarly, for getting the biggest min value (calling it mn), we want to get bricks to all the positions that have bricks less than mn. And since mn is the biggest min value, this will create the maximum demand for bricks. Hence it only makes sense that the highest demand and the highest supply can't only coexist simultaneously but actually beneficial for each other since when people want to sell the most bricks, there are the most buyers.

Hope this makes some sense XD

CF contests are getting less and less frequent :(

Looking forward to getting this feature for everyone :)

Great contest! Thanks to the writer(s)

Gta 6 will come before rating changes

No way XD

Yeah, D did feel like it would give chat gpt a hard time visualising it

Anyone else solved D using trie?

Does anyone else think there was a lot of cheating today?

I actually did it using just combinatorics, no dp. 299567046