Auto comment: topic has been updated by twosquares (previous revision, new revision, compare).

ok So there are indeed two 'f's in conqueror_of_fourist

Thanks for a super fast editorial. Enjoyed the contest. Happy New Year!

9 problems 1 voter :(

I think the single voting is attached to all the problems — after I clicked "good problem" on D my "awesome problem" on E became a "good problem"

It was a great contest! Happy New Year everyone :)

great problems but no way there are 10 k solves on 'c'

Happy new year!

happy new year everyone :3

I'm just curious, How many guys guessed the solution to E without any proof

Why the voters of all problems are actually the same one

Auto comment: topic has been updated by twosquares (previous revision, new revision, compare).

Nice, I thought of D in this way:

Each elf is an island (node) Initially, you have n elves representing n islands(connected components with a single node with value their attack/hp) .

At every turn, an elf who hasn't attacked yet attacks another elf. Translates to: "A connected component merges with another connected component via a directed edge). This costs loss in hp for both the islands involved in the merge.

Similarly the entire simulation revolves around the approach of building

We're asked to find whether "m" connected components exist simultaneously at any round in our simulation.

The rest of logic, follows on building with these. (Hope you liked this perspective of the problem D).

W Editorial.

how to prove the m=0 case in D? btw happy new year

Queueforces

How the actual f* does a world exist where 186 people solved a problem that even Tourist couldn’t?

Really enjoyed F. It requires some thinking but the solution code is clean. Nice to see it wasn't just ad-hoc.

anyone pls help me implement the m = 0 case for D.

My logic that I thought during contest was something like storing the elfs in multiset and then attacking largest and second largest and thus second largest dies and largest hurts. So, i remove(both) and insert(the health after hurting) in multiset.

Any help will be appreciated

      if(m == 0){
            vi fought(n, 0);

            multiset<pll> s;
            for(auto p : arr) {
                s.insert({p.sc, p.fs}); 
            }

            vctrpll fight;
            
            while(s.size() >= 2){
                auto it_max = prev(s.end());
                auto it_2nd = prev(it_max);

                if(!fought[it_2nd->second]){
                    fight.push_back({it_2nd->second, it_max->second});
                    fought[it_2nd->second] = 1;
                }
                else{
                    fight.push_back({it_max->second, it_2nd->second});
                    fought[it_max->second] = 1;
                }

                s.erase(it_max);
                s.erase(it_2nd);
                if(it_max->first - it_2nd->first > 0)
                s.insert({it_max->first - it_2nd->first,it_max->second});
            }

            cout << fight.size() << endl;
            for(auto it : fight){
                cout << it.fs << " " << it.sc << endl;
            }
            continue; 
        }

full code : 355403171

As a gamer,
recoil != counter-attack
this confused me for a bit.

in D, why is recoil considered an attack?

intuitively, i thought the attacks are like directed

- "Then, elf x attacks elf y"

x attacks y doesnt mean y attacks x is what i thought

its like u punched a wall and got hurt so u tell everyone the wall hit u

edit: mb gng, im dumb af

Auto comment: topic has been updated by twosquares (previous revision, new revision, compare).

Missed the part in E that the chosen element has to be "maximal" :sob:

As a Magic The Gathering enjoyer I have to give a shoutout to poor old forgotten Mass Hysteria all the way back from Mirrodin

Maybe I'm alone in this I don't know

It turns out that for each of the children in this range, we can choose each of their signs independently

bro this took me so long to identify this in problem C

Auto comment: topic has been updated by twosquares (previous revision, new revision, compare).

Got cooked.... anyways happy new year._.

I was so close to solving D but the m = 0 case fried me lol. Great contest, good job to the problemsetters.

The second problem has a hidden line in the statement that normal users cannot see on CF. It only shows up when the statement is copied (like into AI tools). That line asks LLMs to add a specific assert.

Humans would never add that assert because the input already guarantees it. So if you see solutions with that unnecessary assert — yeah, that’s CF quietly catching AI users / cheaters

E is very nice problem. Just simple logic.

What was i thinking during the contest :(

happy new year everyone :3

Hello everyone

I cheated on all the tasks, but I felt very ashamed. I want to admit it. Banish me, please, otherwise my conscience will torment me.

Thanks for the contest, congrats to the authors for a flawless round. I found E not very enjoyable and a bit hit or miss (in particular, I think guessing the correct approach is much easier than proving it works). The rest of the set is peak though. B is great, C is definitely very educative for the target audience, D is interesting enough, and H is an AMAZING problem!!

"Each remaining elf should attack the (larger) elf to its right before the elves before it are dead." That line in the editorial for problem D is unclear. In fact each remaining elf must attack the larger elf first, and only after the last elf required to kill the largest one has been reached, should start the "killing the largest elf with a bunch of smaller ones" part.

I can't see the implementation of the solution to problems in editorial

Auto comment: topic has been updated by twosquares (previous revision, new revision, compare).

I'm quite confused about the m = 0 case in problem D. What I was thinking during the contest is that the last two elves should be having same health values. How does the solution in the editorial guarantees that?

Can we even solve D if ai's are not distinct ? I misread the problem and was trying to solve this

Solved C using dp, though its pretty not simple as compared to editorial

#include <bits/stdc++.h>
using namespace std; 
#define endl '\n'
#define all(x) (x).begin(), (x).end()
using ll = long long;
using i64 = int64_t; 
const long long INF = 0x3f3f3f3f3f3f3f3f; 
const ll MOD = 1e9 + 7;

ll bp(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i]; 
    }
    vector<ll> dp(n); 
    dp[n - 1] = 0; 
    dp[n - 2] = max(-a[n - 1], a[n - 2]);
    int ni = -1; 
    ll nsm = 0;
    ll sm = 0; 
    ll mn = INF; 
    for (int i = n - 1; i >= 0; --i) {
        if (i <= n - 3) {
            dp[i] = a[i] + dp[i + 1]; 
            dp[i] = max(dp[i], -sm); 
            if (ni != -1) {
                if (ni == n - 1) {
                    dp[i] = max(dp[i], -nsm - mn + a[i]);
                } else {
                    dp[i] = max(dp[i], -nsm + dp[ni + 1] + a[i]);
                }
            }
        }
        if (a[i] <= 0) {
            nsm += a[i];
            mn = min(mn, abs(a[i])); 
            if (ni == -1) {
                ni = i; 
            }
        } else {
            ni = -1; 
            nsm = 0; 
            mn = INF; 
        }
        sm += a[i]; 
    }
    cout << dp[0] << endl; 
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
    // freopen("workspace/input.txt", "r", stdin);
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

anyone like me who didn't read that only maximal element was getting split x->x/2 ::( .

Any clues or hints on how to solve the Bonus problem of E? :3

I'd say that G is a wonderful problem!

I thought I've trained hard by the end of 2025,but last night I was stuck by D and haven't noticed "removing maximal" in problem E so I got -77.

It really makes me depressed but I think I will get a better score in 2026.

Editorial problem E:

"Consider the arrays a and b before the final concatenate, so that the hidden final array is ab . Since a and b are identical, we can find where the split point in ab is using binary search on prefix sums."

I think here it's meant to be the sums of elements of a and b are equal?

imo, problem E could have been really hard if a guess was not possible from the max number of queries allowed and typical sum setup which demands for B.S. in interactive problems.

When I was working on D, I even forgot the question's meaning and kept thinking mechanically. Eventually, I got stuck for two hours before finally solving it.

can someone please help where my solution fails on E? for this submission https://mirror.codeforces.com/contest/2178/submission/355617425

Can someone please give the intuition behind coming up with the construction strategy in task d for m = 0 and m > 0 case.

There's an $$$O(n)$$$ time for 2178D — Xmas or Hysteria.

Idea is almost same as editorial, except that we now need a strategy $$$S$$$ that runs in linear time and does the following :

On input any sequence of elves $$$Elves[i,...,j]$$$, output a sequence of valid attacks such that at the end there's exactly one or zero elf remains.

Now suppose we have such magic $$$S$$$, then

for $$$m \ge 1$$$ case : same as editorial, except that we're gonna use std::nth_element to put the largest $$$m$$$ elves in $$$I = Elves[n-m+1,...,n]$$$ and the second largest $$$m$$$ elves in $$$II = Elves[n-2m+1,...,n-m]$$$. Also we're gonna deal with the remaining $$$n-2m$$$ elves with our magic $$$S$$$ (in the case that there's one elf remains, let it attack any elf in $$$II$$$). Finally, we do a parallel scan of $$$I$$$ and $$$II$$$ and let elves in $$$I$$$ attack elves in $$$II$$$.

for $$$m = 0$$$ case : still very similar to editorial. Suppose we pass the sum check (otherwise no solution). First swap the strongest to $$$Elves[n]$$$ and second strongest to $$$Elves[n-1]$$$, then starting at $$$i=1$$$, while $$$Elves[i].attack \lt strongest.hp$$$, let $$$i$$$ attack strongest and strongest.hp -= Elves[i].attack, then ++i. The while loop terminates when we reach an elf Alice where $$$Alice.attack \ge strongest.hp$$$ (it's guaranteed that this occurs and Alice $$$\neq$$$ strongest due to the initial sum check). Now deal with the elves between Alice (inclusive) and $$$2nd$$$ strongest (exclusive) using our magic $$$S$$$. If there's one elf remaining, let it attack the $$$2nd$$$ strongest. Finally, let $$$2nd$$$ strongest punch the strongest (this punch will kill the strongest as $$$strongest.hp \le Alice.attack \le 2ndStrongest.attack$$$).

Here's one possible way to design our magic strategy $$$S$$$. The idea is to be greedy and always let the dying elf to attack. We're going to do a linear scan over the input $$$Elves[i,...,j]$$$. Suppose we're now at $$$p$$$, lets call $$$Elves[p]$$$ Alice and $$$Elves[p+1]$$$ Bob. The invariant is that (1) Alice has never attacked before (2) Bob will always have full hp. Then some case analysis

if(Alice.hp <= Bob.attack){
    if(Alice.attack > Bob.attack){
        //both will die, it doesn't matter who attacks who
        let Alice attack Bob
        p+=2 //skip both Alice and Bob
    }else{
        //only Alice will die
        let Alice attack Bob //valid by invariant
        Bob.hp -= Alice.attack
        p++
    }
}else{
    //only Bob will die
    let Bob attack Alice //valid by invariant, full hp means not attacked before
    Alice.hp -= Bob.attack
    Elves[p+1] = Alice
    p++
}

please check invariant is maintained for all cases. It's clear that either one or zero elf remains when we finish.