BigBadBully's blog

By BigBadBully, history, 3 months ago, In English

There have been numerous occasions on which this community proved to be discriminating against <1400 rated people. Newbies on occasions post the exact same blogs/comments as grandmasters, but get downvoted to oblivion while the grandmasters get upvoted to oblivion. Isn't this unfair? My blogs are also proof of that, I posted blogs which had no errors, no grammatical mistakes and even provided useful information yet they still got downvoted.

I urge every community member to be understanding towards lower ratings, because they're literally the future of codeforces.

Full text and comments »

  • Vote: I like it
  • -55
  • Vote: I do not like it

By BigBadBully, history, 3 months ago, In English

after years of blood and sweat i have reached the. the seemingly unachieveble cyan is coloring my name. BigBadBully is now colored in the beautiful navy cyan color. every 800 probelm i did was worth it, every downvote i got was worth and i request more downvotes to congratulate me please downvote me please i hate this community andi hate most of the people reading this but obviously the mods are an exception plz downvote me plzzplzpzlpzlzplzplzplzplzplzplzplzpzlpzlpl

everybody follow barber.fero on ig

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it

By BigBadBully, history, 3 months ago, In English

After a long and arduous journey, I have finally gotten to a large codeforces milestone. In the 10 months that I have been on codeforces, I have successfully solved 200 problems! While this may still not affect my rating, I believe that it shall very soon change it for the better.

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

By BigBadBully, history, 6 months ago, In English

Whenever I give contests I feel extremely anxious. The last contest I gave I was only able to do A and after an hour I felt so much stress that I left the contest. 1 month later I upsolved the same contest up until E (inclusive). This happened to me many times before. While practicing I can often do <2000 problems without editorial but in contest I struggle with >1400 problems. Why is this so? How can I prevent this from happening? I don't want to be stuck in newbie

Full text and comments »

  • Vote: I like it
  • -11
  • Vote: I do not like it

By BigBadBully, history, 8 months ago, In English

https://codeforces.com/blog/entry/120221

I made a blog about a cool trick I figured out but it got -27. Why? The proof is correct, I wasn't mean, I wasn't trolling... What's wrong with it?

Full text and comments »

  • Vote: I like it
  • -25
  • Vote: I do not like it

By BigBadBully, history, 8 months ago, In English

I'm pretty sure a large amount of people have at the very least heard of Kadane's algorithm. It is a way to find the maximum subarray sum (of an array). But why does it work? Besides the normal proof/explanation, is there another way to explain why it is correct?

Let's fix the right boundary of the subarray. From now on, it is called $$$r$$$. Now we want to find the optimal left boundary, $$$l$$$, for every $$$r$$$. For the answer we can just find the maximum of all fixed $$$r$$$. How could we do this? Well for a given $$$r$$$ let's assume we already found the $$$l$$$. How does the answer change for $$$r+1$$$? For $$$r+1$$$, all we did was just add $$$a_{r+1}$$$ to every subarray we had so far. For every integer value $$$a,b,c$$$ it holds true that

$$$a \ge b \implies a + c \ge b + c$$$

This means that the greatest subarray sum will still be greater than every subarray whose left boundary was contained in the $a_{l..r}$ subarray, so we only need to check if the subarray sum $$$a_{{r+1}..{r+1}}$$$ (the element $$$a_{r+1}$$$) is greater than the sum of $$$a_{l..r+1}$$$. Because this is true for the $$$a_{1..2}$$$ subarray it holds true for every subarray, completing our proof by induction. Why does this prove Kadane's algorithm? Because when we consider the $$$a_{{r+1}..{r+1}}$$$ subarray, in the perspective of the $$$r$$$ before, we are considering the neutral element of addition, 0. Following the property stated beforehand, this means the answer doesn't change based on whether we evaluate $$$0 > a_{l..r}$$$ or $$$a_{r+1} > a_{l..r+1}$$$

Does this only work for subarray sums? It turns out that every function for which

$$$f(a,c) \ge f(b,c) \implies f(a,c+1) \ge f(b,c+1)$$$

holds true this works (the function takes subarray bounds as parameters). We in turn get a very simple general Kadane's algorithm. A considerable number of practical functions have this property, but I don't know of much problems that can be solved by reduction to such functions. If you want to prove that the function has the property you can also use something like I used in the proof of Kadane's subarray sum algorithm.

Besides the proof by induction I presented here is a proof by AC (if you don't believe me):

CSES Kadane's: https://cses.fi/problemset/result/7030713/ or https://cses.fi/paste/5900cd60d6a09ffc6b47b9/

Full text and comments »

  • Vote: I like it
  • -36
  • Vote: I do not like it

By BigBadBully, history, 9 months ago, In English

During my quest to become pupil (which requires learning FFT) I discovered how to do the classic subset sum problem using FFT. As you all know, FFT is an algorithm commonly used for polynomial multiplication. What does it have to do with calculating subset sums though? (all you need to know about FFT for this blog is that it is used for multiplying polynomials)

Let's look at the dp solution first. While considering a number, you can either use it or not use it. If a number can be used an arbitrary amount of times (which is the constraint the blog will be focusing on from now on), it can either be used $$$0$$$ times, once, twice, ... This can be represented as a polynomial.

The polynomial for a number $$$n$$$ will look like: $$$1 + z^n + z^{2n} + z^{3n} + ...$$$

What does this have to do with subset sums though? You can first get rid of some terms in the polynomial, i.e. the terms with exponents greater than $$$x$$$, the target sum. When multiplying $$$2$$$ such polynomials, a lot of stuff happens, to say the least. But, because $$$2$$$ polynomials are being multiplied, both with the same bases, some exponents are going to be added to some other exponents.

This might sound confusing but to clear it up let's look at $$$2$$$ polynomials of numbers $$$a$$$ and $$$b$$$.

$$$a(z) = 1 + z^a + z^{2a} + ...$$$
$$$b(z) = 1 + z^b + z^{2b} + ...$$$
$$$a(z) \cdot b(z) = a(z) \cdot 1 + a(z) \cdot z^{b} + ...$$$

In simple terms, this means to make an arbitrary sum using the $$$2$$$ numbers, we can use $$$b$$$ $$$0$$$ times, once, twice, ... and combine it with the number $$$a$$$, which we can also use $$$0$$$ times, once, twice, ... Does this sound familiar? This is the subset sum problem! This interesting property is not restricted to polynomials with only $$$1$$$ and $$$0$$$ in their coefficients. So this means that we can compute ways to construct sums of $$$n$$$ numbers using polynomial multiplication, which can be done with FFT. Because we got rid of the terms with exponents greater than $$$x$$$, we will need to do polynomial multiplication with $$$n$$$ polynomials of length $$$x$$$. In the final polynomial, you can find the number of ways to construct a sum $$$x$$$ by just looking at the coefficient of the $$$z^x$$$ term. All of this can be done in $$$O(n x \log x)$$$.

Sadly, the "naive" FFT solution is slower than the dp solution in $$$O(nx)$$$. This trick though isn't that unknown, -is-this-fft- used it as an example of what FFT can be used for in his FFT tutorial. I would also implement this as a proof it works, but I couldn't find any problems which have low enough constraints for this method to pass.

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

By BigBadBully, history, 9 months ago, In English

I have tried absolutely everything. I learnt dp, djikstra, bfs, binary search, dsu, dfs, nCr, segment tree, fenwick tree, spare tables, stacks, floyd warshall, hashing, modular inverses, but to no avial. I can even solve super hard problems but im still stuck in newbie... how???? why???? i wake up everyday crying because i'm newbie and everytime i go to sleep dreaming of the same beautiful moss green colored name: BigBadBully. please help me i don't know what to do anymore

Full text and comments »

  • Vote: I like it
  • -26
  • Vote: I do not like it

By BigBadBully, history, 12 months ago, In English

The user Planned_Attack obfuscated code in nearly all of the contests he took, except one contest in which he received the "Skipped" verdict. This goes against the contest rules which forbid code obfuscation. Here is one submission of his:

Example of his obfuscation method, task in question is 1838A

I apologize if I made a mistake while reporting this user, this is my first blog and I'm relatively new to the platform.

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it