KitasCraft's blog

By KitasCraft, history, 4 months ago, In English

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 :].

Full text and comments »

Tags idk
  • Vote: I like it
  • +47
  • Vote: I do not like it

By KitasCraft, history, 5 months ago, In English

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.

Full text and comments »

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