This round was pretty interesting for me. Found C much harder than D. Although I did copy E after googling from here, had an insane last minute adrenaline rush trying to guess/brute-force necessary conditions for flower graph in F!

Thanks for the interesting problems — will go and prove F now :blobsweat: Update: hacked lmao

Pretty cool, thanks for sharing! An alternative solution that I implemented uses binary search on prefix sums to find the rightmost drinker that can be satisfied and uses the $$$+1$$$ on left and $$$-1$$$ on right boundary trick. Solution

As a tester, I couldn't help much with review of problems except in the initial div3 phase. The round is well balanced and may positive delta come your way :blobheart:

ord_set.find_by_order(0)

You need to provide the index in find_by_order.

During a contest, I attempted at solving problem E because it felt easier than a usual E. I didn't realize that I was trying E and submitting on D :( I didn't realize it even after the contest ended and was trying really hard to debug and find what's wrong. 1-gon Monogorz helped me find the bug :clownglasses: :ghosthug:

CSES submissions are not globally visible. You need to share it as a paste (you can create one by scrolling to the bottom of your code in your submission, or alternatively use an online paste website. Here's my solution as a paste for example: https://cses.fi/paste/3ff7373cf56f6af416e923/. please share yours the same way). If you're using an O(nk) memory solution, you are not being cache friendly most likely, which is why it might TLE.

Try the test case: 1 1 1 100000000

What do you observe if you use the mean? What do you observe when using the median?

Try solving for some p q r (sorted order). Think of them as points on the coordinate axis. What's the problem asking you to do? It's about finding a point such that sum of absolute differences between each pair of points is minimized. If you choose q to be that point, the answer is (q - p) + (r - q) + (q - q). If you choose some other point, let's say q + x for any value x, then the answer is ((q + x) - p) + (r - (q + x)) + (q + x - q) == (q - p) + (r - q) + x. Hence, the optimal point must be q.

Try solving for some case p q r s and notice that any value x satisfying q <= x <= r works. After solving these two cases, it's easy to show that median works.

(2) Yes, it is possible like dalex mentioned. I was stuck on the same problem for days before coming up with the right idea and have spent a lot of productive hours into it. I couldn't get a working implementation myself. With help from DenjellBoone, I finally managed to get an AC on CF EDU. Same problem on CSES. You can also read our discussion on Discord. I'd like to note that the discussion is incomplete as we continued a lot in personal DM. I would love to explain the idea in more detail if you have any doubts.

Here's a sample implementation for reference:

/**
    Lost Arrow (Aryan V S)
    Tuesday 2020-12-29
**/

// Solved with a lot of help from Denjell (CF: DenjellBoone). Thanks!

#ifdef LOST_IN_SPACE
#  if   __cplusplus > 201703LL
#    include "lost_pch1.h" // C++20
#  elif __cplusplus > 201402LL
#    include "lost_pch2.h" // C++17
#  else
#    include "lost_pch3.h" // C++14
#  endif
#else
#  include <bits/stdc++.h>
#endif

// Y Combinator: Fixed-Point Combinator in Untyped Lambda Calculus
// Y = Lf.(Lx.f(x x))(Lx.f(x x))
// The Y combinator is a formula which lets you implement recursion in a situation
// where functions can't have names but can be passed around as arguments, used as
// return values, and defined within other functions.
//
// Sources:
// https://www.wikiwand.com/en/Fixed-point_combinator#/Fixed_point_combinators_in_lambda_calculus
// https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/
// https://stackoverflow.com/questions/93526/what-is-a-y-combinator (https://stackoverflow.com/q/93526/14339850)

template <typename T>
class y_combinator {
  private:
    T t;
  public:
    template <typename U>
    constexpr y_combinator (const U& u) : t (u) { }

    template <typename... Args>
    decltype(auto) operator () (Args&&... args) {
        return t(std::ref(*this), std::forward <Args> (args)...);
    }
};

template <typename T>
y_combinator (T&&) -> y_combinator <std::decay_t <T>>;

struct node {
    int64_t value = 0;
    int64_t lazy  = 0;
    bool lazy_assign = false;
};

int main () {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.precision(10);
    std::cerr.precision(10);
    std::cout << std::fixed << std::boolalpha;
    std::cerr << std::fixed << std::boolalpha;

    int n, m;
    std::cin >> n >> m;

    std::vector <node> tree (4 * n);

    auto push = [&] (int v, int tl, int tr, int tm) {
        if (tree [v].lazy_assign) {
            tree [2 * v + 1].value = (tm - tl + 1) * tree [v].lazy;
            tree [2 * v + 2].value = (tr - tm) * tree [v].lazy;
            tree [2 * v + 1].lazy = tree [v].lazy;
            tree [2 * v + 2].lazy = tree [v].lazy;
            tree [2 * v + 1].lazy_assign = true;
            tree [2 * v + 2].lazy_assign = true;
        }
        else {
            tree [2 * v + 1].value += (tm - tl + 1) * tree [v].lazy;
            tree [2 * v + 2].value += (tr - tm) * tree [v].lazy;
            tree [2 * v + 1].lazy += tree [v].lazy;
            tree [2 * v + 2].lazy += tree [v].lazy;
        }
        tree [v].lazy = 0;
        tree [v].lazy_assign = false;
    };

    auto update_assign = y_combinator([&] (auto self, int v, int tl, int tr, int l, int r, int64_t val) -> void {
        if (l > r)
            return;
        if (tl == l && tr == r) {
            tree [v].value = (tr - tl + 1) * val;
            tree [v].lazy  = val;
            tree [v].lazy_assign = true;
        }
        else {
            int tm = (tl + tr) / 2;
            push(v, tl, tr, tm);
            self(2 * v + 1, tl, tm, l, std::min(r, tm), val);
            self(2 * v + 2, tm + 1, tr, std::max(l, tm + 1), r, val);
            tree [v].value = tree [2 * v + 1].value + tree [2 * v + 2].value;
        }
    });

    auto update_add = y_combinator([&] (auto self, int v, int tl, int tr, int l, int r, int64_t val) -> void {
        if (l > r)
            return;
        if (tl == l && tr == r) {
            tree [v].value += (tr - tl + 1) * val;
            tree [v].lazy  += val;
        }
        else {
            int tm = (tl + tr) / 2;
            push(v, tl, tr, tm);
            self(2 * v + 1, tl, tm, l, std::min(r, tm), val);
            self(2 * v + 2, tm + 1, tr, std::max(l, tm + 1), r, val);
            tree [v].value = tree [2 * v + 1].value + tree [2 * v + 2].value;
        }
    });

    auto sum = y_combinator([&] (auto self, int v, int tl, int tr, int l, int r) -> int64_t {
        if (l > r)
            return 0;
        if (tl == l && tr == r)
            return tree [v].value;
        int tm = (tl + tr) / 2;
        push(v, tl, tr, tm);
        return self(2 * v + 1, tl, tm, l, std::min(r, tm)) + self(2 * v + 2, tm + 1, tr, std::max(l, tm + 1), r);
    });

    while (m--) {
        int t, l, r, v;
        std::cin >> t >> l >> r;
        --r;
        if (t == 1) {
            std::cin >> v;
            update_assign(0, 0, n - 1, l, r, v);
        }
        else if (t == 2) {
            std::cin >> v;
            update_add(0, 0, n - 1, l, r, v);
        }
        else {
            std::cout << sum(0, 0, n - 1, l, r) << '\n';
        }
    }

    return 0;
}

I've tried maintaining propagation lists for each node but the solution ends up consuming too much memory. This solution that Denjell managed to implement has helped both of us in thinking about the general structure for lazy stuff on Segment Trees.

This round was sexy AF. I really enjoyed the problems (like a lot!). This has been my best performance so far and I'm very happy that I was able to do so in the last contest of the year. It's been a rough year for many, a great time to grind CP for others and a somewhat meh year for me. Whatever it has been, happy new year to everyone! Hope everyone has a great year ahead!

I don't understand how F could possible have 1000+ solves as it seems way too orz than normal. If someone could tell me how to solve, I would be very happy about it. The problems this round were great (to say the least) and the difficulty ordering and level felt perfectly balanced. Thank you authors!

My friends got their future rating predicted and I'd like to know mine too stefosity :thonk:

Almost same problem but with costs for replacing involved — D. Least Cost Bracket Sequence.

I basically copy pasted my solution for that with costs replaced by (0, 0). Problem is that I don't know how to read problem statements :(

I must say, the examples are pretty good yeah.

Does any one of these top results from Google search answer your question? If so, you should consider searching things first before making a blog asking about it.

A B C D

Monogon orz

That's not a sparse table implementation. It's a segment tree. I've a feeling you've probably copied code from somewhere.

Are you angry at Santa or Monogon? Why don't you and other members of your family have the santa hat on?

This is solution to E ig. OP asked about D.

The question states that division by proper divisors is not allowed. So, it makes sense to keep the number even all the time. If you keep it even, you always can divide by its greatest proper divisor i.e. n/2.

When n is odd, decrease it by 1. When it is even, divide it by n/2 (the greatest proper divisor). This is the optimal strategy.

Whoever made problem D, I love you. Fibonacci sequence popped out of nowhere. Could someone please share a solution to F?

Yep, just checked on godbolt. Disassembly is different for compiling with optimisation flags (as expected). The optimiser knows that both calls produces the same result and so instead of doing two calls, only one call is done (which explains the linear time and why the code passes).

My bad, you're right :( It is indeed exponential. I think the compiler optimises the two calls to func(i+1) to just one call. You'll have to probably look at the disassembly to find out if that's right. Locally, you might be using debugging flags and other stuff which prohibit compiler optimisations. I don't really know at this point after I realised I'm mistaken. Sorry for having wasted your time.

I accidentally hit delete on my last comment which had the proof in hurry to edit something :( It is basically iterating through recursion visiting each position twice.

At each step i, you do two calls to f(i+1), both of which are linear. If you were iterating through all possibilities of changing the current position to 1 or 0 with respect to values at all other position j, then you'd have exponential complexity.

No, the complexity is linear.

I stored the min, max, suffix sum at each node. Would that have been enough? I did eventually implement the lazy updates but it was linear and not constant due to bad implementation :(

You only need to solve the 2x2, 2x3 and 3x2 cases. You can then model all n, m into those cases. I bruteforced all costs of strings, made them into linear string instead of grid and tried implementing. I had this one bug in both n and m odd case which I couldn't find which made me mad and I gave up.

Same. I wrote 446 lines of C related code (not counting code template) before giving up and moving to E (which seemed easier to implement).

// handling different costs

std::vector <std::set <std::string>> costs (5);
auto init = [] () -> bool {

    costs [0].insert("0000");
    costs [0].insert("000000");

    costs [1].insert("1110");
    costs [1].insert("1101");
    costs [1].insert("1011");
    costs [1].insert("0111");
    costs [1].insert("111000");
    costs [1].insert("110100");
    costs [1].insert("101100");
    costs [1].insert("011100");
    costs [1].insert("001110");
    costs [1].insert("001101");
    costs [1].insert("001011");
    costs [1].insert("000111");

    costs [2].insert("0101");
    costs [2].insert("1010");
    costs [2].insert("0110");
    costs [2].insert("1001");
    costs [2].insert("010100");
    costs [2].insert("101000");
    costs [2].insert("011000");
    costs [2].insert("100100");
    costs [2].insert("000101");
    costs [2].insert("001010");
    costs [2].insert("000110");
    costs [2].insert("001001");
    costs [2].insert("111111");

    costs [3].insert("0001");
    costs [3].insert("0010");
    costs [3].insert("0100");
    costs [3].insert("1000");
    costs [3].insert("000100");
    costs [3].insert("001000");
    costs [3].insert("010000");
    costs [3].insert("100000");
    costs [3].insert("000001");
    costs [3].insert("000010");
    costs [3].insert("000100");
    costs [3].insert("001000");
    costs [3].insert("111011");
    costs [3].insert("110111");
    costs [3].insert("101111");
    costs [3].insert("011111");
    costs [3].insert("111110");
    costs [3].insert("111101");
    costs [3].insert("111011");
    costs [3].insert("110111");

    costs [4].insert("1111");
    costs [4].insert("111100");
    costs [4].insert("001111");

    return true;
};

Easiest problem of contest: C (idea)

Hardest problem of contest: C (implementation)

Can anyone who used segment tree for E suggest how to handle the lazy updates? What information did you store in nodes? The second type of query was easy to handle and implement. The first, not so much.

I just read the editorial. The $$$O(N)$$$ solution is already mentioned there. Why make a blog regarding the same then? Did you not think of reading the editorial before making a post?

Build prefix sums on the frequency of Q. You can then calculate the number of subsequences by summing up number of prefix Q's multiplied by the number of suffix Q's for each position where A is present.

Wow! I failed the exact same test case for the exact same error. This is the one:

for(int i = 1; i < freq.length; i++) {
    freq[i] += freq[i - 1];
        if(freq[i] > w) {
            can = false;
            break;
        }
}

You never check freq [0] in your if statement. The constraints mention that the values of s and t can include time 0. My fix was to change i to start from 0 and do prefix sum only if i > 0.

He got there for the first time... You're a set player among IGMs. When you make it to LGM some time, I'll be the one who's blog you'll be seeing starting the orz orz chain.

He deserves an orz chain. Let's go!

SecondThread orz

Time is relative. How it moves for one may be very different for how it moves for another :p

If there is a zero in the grid, you can always make all elements positive.

If the number of negative elements is even, you can always make everything positive.

If the number of negative elements is odd, one of the elements will always be negative in the end after all operations. Try making this negative value as the one with smallest absolute value among all numbers.

That feeling of the rise in difficulty from D2C/D1A to D2D/D1B is a killer. The round had sexy af problems. I wasn't able to solve D and above but I really liked thinking about them and how I was thinking about them. Thank you for the amazing round setters and testers <3

Nevermind, I'm stupid. I made it more complicated that it should have been. Sorry for disturbing sare.

I figured you had to do that (and I tried it). But, how do I take care of the sum once I hit a wall?

D is a very standard interval/event management problem.

/**
    Lost Arrow (Aryan V S)
    Sunday 2020-11-15
**/

#ifdef LOST_IN_SPACE
#  if   __cplusplus > 201703LL
#    include "lost_pch1.h" // C++20
#  elif __cplusplus > 201402LL
#    include "lost_pch2.h" // C++17
#  else
#    include "lost_pch3.h" // C++14
#  endif
#else
#  include <bits/stdc++.h>
#endif

namespace competitive_programming::inline utility { }
namespace competitive_programming::debugging      { }
namespace competitive_programming::io             { }

namespace competitive_programming::utility {

    class timer {
      private:
        std::chrono::time_point <std::chrono::steady_clock> begin, end;
      public:
#ifdef LOST_IN_SPACE
         timer () : begin (std::chrono::steady_clock::now()), end () { }
        ~timer () {
            end = std::chrono::steady_clock::now();
            std::cerr << "\n\nDuration: " << std::chrono::duration <double> (end - begin).count() << "s\n";
        }
#else
         timer () : begin (), end () { }
        ~timer () { }
#endif
    };
}

constexpr bool test_cases = false;

auto solve () -> void {
    int64_t n, w;
    std::cin >> n >> w;
    std::vector <int64_t> s (n), t (n), p (n);
    for (int i = 0; i < n; ++i) {
        std::cin >> s [i] >> t [i] >> p [i];
    }

    const int m = 2e5 + 42;
    std::vector <int64_t> time (m, 0);
    for (int i = 0; i < n; ++i) {
        time [s [i]] += p [i];
        time [t [i]] -= p [i];
    }

    bool okay = true;
    for (int i = 0; i < m; ++i) {
        if (i > 0)
            time [i] += time [i - 1];
        if (time [i] > w) {
            okay = false;
            break;
        }
    }

    std::cout << (okay ? "Yes" : "No") << '\n';
}

int main () {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.precision(10);
    std::cerr.precision(10);
    std::cout << std::fixed << std::boolalpha;
    std::cerr << std::fixed << std::boolalpha;

    competitive_programming::timer t;
    int32_t cases = 1;
    if (test_cases)
        std::cin >> cases;
    while (cases--)
        solve();

    return 0;
}

// g++.exe -Wall -Weffc++ -Wextra -pedantic -std=c++20 -g -D_GLIBCXX_DEBUG -DLOST_IN_SPACE -H

How do you convert transitions in E from $$$O(N)$$$ to $$$O(1)$$$ in an easy way? What's the usual style guide to follow? It was an easy and fun problem. I wasn't able to implement the summing up of dp values of rows, cols and diagonals in an easy way that accommodates stopping at a wall (which is done in $$$O(N)$$$ making my solution cubic; would TLE).

It's easier to explain how to use the STL function wrapper :p It is slow for many reasons, the details of which I'm not going to discuss here. Y combinators come to the rescue as they avoid extra overhead. You can use the Y combinator technique without the whole class interface thing though. Feed a lambda to itself.

auto factorial = [&] (auto self, int64_t n) -> int64_t {
    return n == 1 ? 1 : n * self(self, n - 1);
};

std::cout << factorial(factorial, 10) << '\n';

What are you using? Does CF have an app that I don't know about? Or is it some userscript?

Yeah. There are four ways I know that you can use for writing recursive lambdas. One of them being Y combinators.

Hey 300iq. The Sign Up link seems to be broken (both for Russian and other speaking countries). Could you fix it? It redirects to a Codeforces page in russian saying URL not found on server.

Time to write a blog with 4 short ways of writing recursive lambdas and get contribution (at least that's what me and Monogon are here for). I might ask him to write it though. Can't see him lose his source of dopamine :p

What percentage of people using CF do you think know how to write a C++ recursive lambda without using std::function?

There's another blog on the topic here. Most important talk has been done there.

Omg Indian round! So excited

That's a myth. With non-synchronisation with stdio, cout is as fast as printf, if not faster.

What's your idea with binary search?

Thanks rchaves and tribute_to_Ukraine_2022, understood.

Brute force numbers from 2 to 1000 and calculate how many numbers in A are divisible by them. The one with the maximum count of numbers divisible is the answer.

Calculate prefix sums on the input. Also calculate the maximum sum you achieve on the input for every $$$0$$$ to $$$i$$$, where i is from 0 to N — 1 (0-based indexing). Then, you can find the maximum coordinate by iterating from 0 to n and adding the maximum sum in range(0, i) to your current coordinate.

auto solve () -> void {
    int n;
    std::cin >> n;
    std::vector <int64_t> a (n), pref (n + 1), best (n + 1);
    for (int i = 0; i < n; ++i) {
        std::cin >> a [i];
        pref [i + 1] = pref [i] + a [i];
        best [i + 1] = std::max({best [i], pref [i], pref [i] + a [i]});
    }

    int64_t max = 0, x = 0;
    for (int i = 0; i < n; ++i) {
        max = std::max(max, x + best [i + 1]);
        x += pref [i + 1];
    }

    std::cout << max << '\n';
}

What's the idea for E? I spent 50 mins on it thinking it was easier than D but I couldn't get it to work on one of the sample tests; probably some implementation errors. D was easier than I thought though. Great contest, thanks!

Hello from Notepad.

Change accumulate(all(x), 0) to accumulate(all(x), 0LL).

Since a little talk about features has started to take place here in this blog and if it's not too much to ask, I'd like to add a feature request. I find that loading comments on blogs can sometimes be slow (even when the connection seems to be perfectly fine). This is frustrating when one just wants to read some editorial or look at something important. If something could be implemented along the lines of optional loading of comments on blogs (basically loading them only if one wanted to by, let's say, clicking somewhere on the blog like "Load Comments"). Many times the page is unresponsive until all comments are loaded (especially when trying to open spoilers). It gets worse on days when there's a contest and the activity levels are higher than usual. I'd like to peacefully just load the editorial and not want to have to deal with waiting for the comments (which are pretty useless tbh). I guess this may be a pretty common problem but I don't know for sure as I've never seen others speak on the matter. Also, this maybe a pretty easy feature to implement too.

This comment is posted as a reply on Um_nik's comments because more often than not they DO get noticed (and I want this to be noticed by the CF Team). Sorry for another green notification though.

Maintain a count for how many cities are under a bandit gang and indices (using map preferably). Connect all other gang cities to one city.

Example: [1,1,1,2,2,3,3,3,3]

Counts: [1: 3], [2: 2], [3: 4]

Now, connect all cities under gang 2 and 3 to one city in gang 1. For the two remaining cities under gang 1 (notice 1 city of gang 1 is already used up in previous connection), connect them to any other city distinct gang city. Implementation is simple.

The biggest piranha can eat all other piranhas. So 7 at index 1 can eat everything else. However, 4 at index 3 (what you say) can not because it will only get to size 6 after eating piranha with size 1 and 3 and it can't eat 7.

A lot of people solved it by hand. There's nothing to feel stupid about it. I did it too (although I took only 10-ish minutes proving at 3-4 implementing). Although those who did search for it are at a slight advantage in the contest, it's insignificant over many future rounds. At least you were able to prove why the formula is correct and not blindly copy it from elsewhere.

You can't simplify it further. It's a factorial. Maybe you could write the mathematical notation to make it look clean but that doesn't help programmatically.

I looked up your solution after you posted the "Why would you give a problem...." comment. It's very elegant. Understood, thanks!

If Div3 is a contest in which we'd like Div3 participants to solve the entire set, this seemed like the perfect one.

I dislike problem E because it felt easier than B (to me and maybe others too considering the number of solves). F seems pretty easy if the constraint of M/2 is omitted and we're supposed to find maximum sum divisible by K in each row. How do I stay within the constraint? I'm thinking 3 state dp maybe. Any ideas on how to solve G?

Hmm maybe. I haven't yet memorized a bunch of stuff to understand phrases I quote. I'll work on it.

I think its hardest level to become red coder from master, what strategy should I use

Just memorize a bunch of stuff enough to solve harder problems :p (feat. Um_nik)

[Edit:] Oh man! Jokes apart, your graph is insanely beautiful (to me, at least). All the best for whatever it is you aspire to do!

Vladimir Putinov is Drew (OPs username). Drew is the short for Drew House. Drew is a mysterious fashion brand in the industry.

Or I could be wrong and the OP might be the sequel to Vladimir Putin.

Ah, crap, I didn't realise we were allowed to do that. RIP my problem reading skills. I'll leave trying to become better at problem solving and go and start learning primary school english.

Let's first iterate over the string and check if we have any cw or acw paths. Now, everytime we encounter an off path, we can mark it as a good path. If we encounter a cw path, we need to make sure that there are no other acw paths and vice versa. Also, another case is when the previous or the next path (leading to and from a node/snake) is off, we can mark this node as good.

Isn't E just about always taking the maximum number m and separating it into p = m / 2 and q = m - p for all maximums, which can be implemented by priority queue? If not, could someone explain why?

Nah, C was kinda cute. To minimise the end value, we had to keep as many smaller digits as possible was my conjecture (which I indeed took a few minutes to prove after a guess submission). The solution (I think) was to take the biggest two values and perform the ceiling operation and then continue. D was quite great too if we (at least I) didn't misinterpret what the problem statement. I thought E could be something to do with segment trees and inversions but that didn't end so well for me implementation-wise.

I looked at your submission for C and it was kinda hilarious to see your struggle in comments. Well done though!

Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.