pls help i can't edit problems on polygon, it just gave me this instead

update: ok it worked again now :>

Hi there! So, I was trying to solve 1954D - Colored Balls. When I first looked at it, I thought "omg how do i solve this fast? iz impossibruh!!1!". And then I looked at the additional constraint and then me be like "bruh it's just knapsack". Now, after thinking about the idea to solve this problem and then looked at the editorial (turns out my idea was more complex lmao even though it's the same concept), I was wondering, "ain't no way knapsack can solve the problem but without additional constraint. r-right?". Well, I got good news. Users, I present to you, the solution of 1954D - Colored Balls but the total number of balls can actually exceed $$$5000$$$!

Now, If you want to understand what I'm expanding on, you should check out the editorial for the problem first, as I am too lazy to write everything here and I also have limited time before I have to go back to play Hypixel Skyblock (not sponsored btw) and then sleep. Now that's out of the way, here's how to solve it:

To recap what the editorial has said:

1. Denote the sum of a subset as $$$s$$$. Each subset's value is $$$\big\lceil \frac{s}{2} \big\rceil$$$ (we call this type 1 subset), unless the maximum integer inside that subset is larger than that. In that case, the subset's value is the maximum integer itself (we call this type 2 subset).
2. Assume all subsets are type 1 subset. Then, we can compute the number of subsets with sum $$$j$$$ using knapsack. Then, compute the sum of values over all subsets.
3. Ofc sometimes not every subset is a type 1 subset. And so we have to compensate the missing values for all type 2 subsets, since we assume then as type 1. So, for each $$$i$$$ such that $$$1 \leq i \leq n$$$, we compute the number of subsets $$$S$$$ such that $$$a_i$$$ is inside $$$S$$$ and $$$a_i > \big\lceil \frac{s}{2} \big\rceil$$$. Then, for each of that subset, we compensate it by $$$a_i - \big\lceil \frac{s}{2} \big\rceil$$$. This can easily be done using the knapsack array we already created from the 2nd point.

Now, it seems like the bottleneck for this buffed version is the 2nd point, where we have to do knapsack in $$$O(nS)$$$ where $$$S$$$ is the total number of balls. Since, if we do it exactly like the editorial, it'll TLE (cuz $$$S$$$ could reach like $$$25 \cdot 10^6$$$ lmao). But, notice that $$$a_i \leq 5000$$$. So, why not use knapsack to just compute number of subsets with sum from $$$0$$$ to sum $$$\max(a_i)$$$ in $$$O(n \cdot \max(a_i))$$$, and then use that knapsack to support 3rd point? "uhm, but KitasCraft, how are we suppose to count the sum of values over all subsets from the 2nd point then???" Well, we can use a really interesting trick here. Note that from this point on, all of the text are talking about modifying the 2nd point, so you still have to do the 3rd point normally afterward lol.

Let's modify the 2nd point a little bit. Assume that every "type 1 subset" has the value of $$$s$$$ instead of $$$\big\lceil \frac{s}{2} \big\rceil$$$. Now, the problem for the 2nd point has been reduced to counting sum over all subset sums. If you already know the "Contribution Sums" technique, then congrats. If you haven't, read this (although the blog applied it on a tree problem).

By using the "Contribution Sums" technique, we'll notice that each value of $$$a_i$$$ appears in exactly $$$2^{n-1}$$$ subsets. And so, we can count the sum over all subset sums in $$$O(n)$$$ using this technique. And, if we divide the sum by $$$2$$$, we can count the sum of values over all subsets in $$$O(n)$$$! Well, that is if the value is $$$\frac{s}{2}$$$ instead of $$$\big\lceil \frac{s}{2} \big\rceil$$$. So, how do we get past this?

Notice that $$$\big\lceil \frac{s}{2} \big\rceil = \frac{s}{2}$$$ if $$$s$$$ is even and $$$\big\lceil \frac{s}{2} \big\rceil = \frac{s+1}{2}$$$ if $$$s$$$ is odd. Thus, we only need to count the sum over all subset sums, add it by the number of subsets with odd sum, then divide all of those by $$$2$$$. This way, we can properly count the sum of values over all subsets in $$$O(n)$$$.

Observation. The number of subsets with odd sum is either $$$0$$$ (if there are no odd $$$a_i$$$) or $$$2^{n-1}$$$ (if otherwise)

Proof. Assume that we have a set $$$T$$$ of size $$$k$$$ with only even numbers. Then, it is very obvious that the number of subsets with odd sum and even sum is $$$0$$$ and $$$2^k$$$ respectively. If we add an odd number into $$$T$$$ (now the size of $$$T$$$ is $$$k+1$$$), then it is guaranteed that every subset that has this number will result in odd sum. And so, the number of subsets with odd sum and even sum is $$$2^k$$$ and $$$2^k$$$ respectively. If we add another odd number $$$x$$$ into $$$T$$$ (now the size of $$$T$$$ is $$$k+2$$$), then let $$$T'$$$ be a subset of $$$T$$$ that contains $$$x$$$. Notice that there exists another subset $$$M$$$ such that $$$M = T' \text{ \ } x$$$ and $$$M \subset S$$$. And, the sum of all elements inside of $$$M$$$ always has different parity from the sum of all elements inside of $$$T'$$$. And so, if we apply this into every subset that satisfy the property of $$$T'$$$, then the number of subsets with odd sum is $$$2^k$$$ (the old subset with odd sum A.K.A. the subset with odd sum and without $$$x$$$) added by $$$2^k$$$ (the new subset with odd sum A.K.A. the subset that used to have even sum, but then $$$x$$$ was added, thus making this subset has odd sum), which is $$$2^{k+1}$$$. Same goes for the number of subsets with even sum.

And so, using those observation, we can actually optimize the knapsack from $$$O(nS)$$$ to $$$O(n \cdot \max(a_i))$$$ and we can also optimize the 2nd point from $$$O(nS)$$$ to $$$O(n)$$$. And thus, the problem is solved in $$$O(n \cdot \max(a_i))$$$. Yayyy! oh btw here's the code 256647759

P.S. My nature language is not english. So, there might be mistakes inside this blog. Feel free to point some mistakes in this blog and also to give feedbacks :3 (help i've written this for like an hour and it's like 10 p.m. now lmao)

Edit: Some fixes on the blog for clearer texts.

Hi there. So I was (and still am) trying to code a solution for 1954D - Colored Balls. One of the main implementation here is the knapsack DP, but somehow there was an issue on the variables. So I went to retype just the knapsack code and debug it like the following:

#include <bits/stdc++.h>

using namespace std;

long long dp[5000];
int a[5000];

int main() {
    int n;
    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        for (int j=5000-a[i];j>=0;j--) dp[j+a[i]]=(dp[j+a[i]]+dp[j])%998244353;
    }
    for (int i=0;i<n;i++) cout << a[i] << ' ';
    cout << endl;
}

So, I was testing this input for this code:

3
1 1 2

and in my local VS Code g++17 compiler it results in this:

301989885 0 2

while in Codeforces g++17, it results in this:

1 1 2

Does anyone know why this happened? If so, please let me know :>

Edit: So apparently, the local compiler produce the correct output if I change 5000 to 5001 or 4999. Now I'm more tempted to know on why 5000 specifically fails.

As we all know, National OI is (mostly) one of the stepping stones needed for one to be able to participate in IOI. But, in some countries, this National OI usually consists of recurring characters involved inside the problems we have to solve. One of the famous ones are USACO with their recurring characters being Bessie the cow and Farmer John. While in my country (Indonesia), Pak Dengklek and his ducks (Kwak is usually the most famous one) are the recurring characters in the National OI.

Now, out of curiosity, what are YOUR National OI's mascots or recurring characters? It's fine if your country doesn't have one :>.

(picture unrelated)

Hello, this is just me venting about stuff that's been bothering me while I'm learning competitive programming. Don't worry, the problem is not about cf itself or the community.

So, recently I've been trying to solve more problems in here (as well as some other competitive programming platform) since I need to prepare for my country's National OI. Sometimes, I will stumble upon a problem where I can solve it, sometimes I can't. But for the one that I initially can't solve (or already tried), I've been thinking about many different ways to approach it. Is it DP? Is it binary search? Is it some weird-to-implement data structure? Is it something that I've tried but it needs a different perspective? Well, ofc in the end I can't solve it so I looked at the editorial for that problem. I usually try to read the hint first, but most of the times I already know the hints. It's just that I don't know how to connect the hints to the problem (or approach it in a different way). So after all of the things I can think of, I finally looked at the tutorial.

So, I read through the editorial and I (most of the time) understand what it said. After that, it clicked in my head that "Oh, why didn't I think of this?" or "Oh, that's actually very interesting and clever". And so I implement it and, AC. I feel happy that it finally works. But sometimes, I didn't feel anything or sometimes even the opposite.

For some problems after reading the editorial, I thought to myself "Welp, I looked at the editorial and that's the solution. It's a similar idea but didn't think about that approach apparently" and then feel guilty about it because it's just the same theory that I knew, but never clicked in my head before reading the editorial. And then, after solving it, I didn't feel like I learned anything from that. I only feel like I just write a code with the idea coming from the editorial, and not me. Just another theory that I've learned but never pass through my head when thinking about it. And sometimes it's even worse because the problem looks so specific that I don't know if the approach for this problem is usable in some way to solve other problems

Am I not improving because I sometimes looked at editorials and just, implement the solution with the similar (or even the same) idea as the editorial? Sorry about the long vent, I just want to get this out so that I can feel a bit better.

tl;dr I sometimes looked at editorial but I feel like not learning anything from it. Is it because I'm not improving? (yes i know this question is like very common but i just want to vent about it ok?)

P.S. Sorry for the bad wording or the bad english that I'm using, since I'm not a native speaker. Also if you're confused on what you're reading, just don't try to understand it. I don't want to ruin someone's day :].

So, I was looking through my notes to find what I've written in my spare time. Turns out, I have this problem written in one of the notes.

I have an $$$N \times N$$$ square grid that needs to be fully covered with tiles. I can only use square tiles with the size of $$$i \times i$$$ where $$$1 \leq i \leq M$$$ to fill it. What is the minimum number of tiles needed to be used to fully cover the grid?

For example: If $$$N = 9$$$ and $$$M = 5$$$, then the minimum number of tiles needed is $$$9$$$, since I can use nine $$$3 \times 3$$$ square tiles to fully cover the $$$9 \times 9$$$ grid.

Constraint: $$$1 \leq M \leq N$$$

Further Constraint: idk, since I don't know the fastest complexity for this.

What is the fastest complexity and how to achieve it? Is it just brute force or is there an efficient algorithm to solve this?

Edit: I just realised that this can be solved in around $$$O(N^2M)$$$ using simple DP. But can it be solved faster than that?

Edit 2: Turns out, some value of $$$N$$$ and $$$M$$$ can't be solved with the simple DP. See this.