I hope this will come soon.

AtCoder: Xavier’s School for Gifted Speed‑solvers (and their “special” powers).

Maybe cheaters.

I think it is as easy as CF div2 C...?

upd: Sorry for inproper words; maybe I underestimated the difficulty of the coming-up-with-the-approach part. Here's the link to my solution.

Absolutely agree.

I genuinely don’t understand why comments like these receive upvotes.

Agree, except I dispute calling it patriotism.

That's extreme nationalism, or something even worse.

Patriots love their homeland and their fellow citizens and treat their country's history with seriousness. In these trolls I see none of these.

Agreed. This is an academic website.

When ABC problem EX disappeared, problem G then become the problem EX (?)

My solution uses a pure DP, with a small optimization using NTT.

Let

We compare $$$S$$$ with $$$M$$$ bit by bit. Suppose we have already processed the lowest $$$i$$$ bits of both $$$S$$$ and $$$M$$$. Let $$$\text{sign}\in{0,1}$$$ indicate the current comparison result: $$$\text{sign}=0$$$ means "$$$S\le M$$$ so far", and $$$\text{sign}=1$$$ means "$$$S \gt M$$$ so far". Since the lowest $$$i$$$ bits have already been handled, storing them in the state is unnecessary.

Define the DP state

When transitioning to $$$f_{i+1}$$$, we choose a subset of indices

to turn on the $$$i$$$-th bit of each corresponding $$$x_{i_j}$$$. Let $$$\text{coef}(s)$$$ be the number of ways to choose a subset of $$$I$$$ such that the sum of the chosen values equals $$$s$$$.

Define the bit function

The transition is

Let

If $$$\operatorname{bit}(\text{newSum},i)=\operatorname{bit}(M,i)$$$, then $$$\text{newSign}$$$ depends on the previous comparison (i.e. keep $$$\text{newSign}=\text{sign}$$$). Otherwise,

The final answer is

The $$$sum$$$ state is always in range $$$[0, 2 \times 100^2)$$$. The current time complexity is $$$\mathcal{O}(60\cdot (100^2)^2)$$$. To optimize the transitions, we use NTT to speed up the convolution.

The final time complexity is $$$\mathcal{O}(60 \cdot 100^2 \cdot \log_2 (100^2))$$$

My code

You can just use simulation,use map <pair <int,int> ,int> mp. And if mp[x][y] = 1 it means that (x,y) cell is occupied. Then when u are getting the query just check cells (r,c),(r + 1,c),(r,c + 1),(r + 1,c + 1) If any of them is occupied you can't do it Else do it and make all of them occupied Link to my implementation : https://atcoder.jp/contests/abc436/submissions/71662097 (My time + memory complexity is very big ,maybe there is much easier solution) :)

we can turn $$$(r,c)$$$ into $$$r*(1 \times 10^9 + 2)+c$$$ , use a set to save it and use 'set::lower_bound' to check.

warning : some process value need long long to save,or the program will return wrong answer

update:delete surplus (

Use NTT for fast polynomial convolution, apply an even/odd decomposition, and finish with a Bostan–Mori evaluation.

But this person used AI not to bring glory to the country but to disgrace it

300 contestants? 300 AI users!

(not excluding some contestants who already knows BM, but in abc contestants, the number obviously can't reach 300.)

Use NTT for fast polynomial convolution, apply an even/odd decomposition, and finish with a BM evaluation. by likely

man... to me A<B<C<D=F except E, I absolutely have no idea how yall find it so easy 😭 , I AC it in contest purely by random guessing then the random bs magic just work... 🥀 , difficulty being so real subjective man...

what is even WTT ? I don't even know any of both

Number Theoretic Transform. It's about polynomial.

You can easily search for it in any browser.

true... like what the fuck is even Bostan-Mori evaluation never heard it before in my life(I'm not even mad, I'm just flabergasted cuz I never heard such a thing and say it out of the love for the game 🥀)

I also think it was poorly written. I couldn't make sense of it despite reading many times

just shut the f*ck up and you will be fine

Hint: For $$$i\in[1,n]$$$, considers the number of photos whose maximum value is $$$B_i$$$.

You can group the elements in the array into some cycles by computing for each element where they should be(their value),the number of swap to make the array sorted will be length-1, and the answer will be the sum of C(length of the cycle,2).

To understand it, there is some cases, let’s call the elements swapped in the first swap a and b:

1.both a and b are placed to where they should be. This won’t happen or else they won’t be in the same cycle, unless the length is 0 which has no contribution to the answer.

2.one of a and b are swapped to their correct position, which decreased the length of the cycle by one.

3.both a and b are not swapped to their correct position. This will split the cycle into two subcycles.

ok

Oh, come on~ Contributions to the world, math world especially, seldom came out of patriarchy.

For those strange behavior in this post, I think expressing patriotism in word is their way to survive the culture around them, nothing about True or False.

History is stories about people in the past, I can't care less. Nowadays, wording is nothing, only power talks. let's just ignore them, and do what we think worth to our lives~!

Do notice that for a certain demographic of a certain age, copying and pasting slogans is the cheapest and most effective way to indulge in a fantasy of being a national hero.

What, at least 1/3 of the solutions to G problems are code generated by AI?

AI Beat Contest

Not that few people.

farming social credit like farming contribution