How do I proof the existence of a solution of Greedy, Number theory and mathematical problems???
// If you have time, please visit my profile and give me some advice // I think I solved too many easy 800 rating problems
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
How do I proof the existence of a solution of Greedy, Number theory and mathematical problems???
// If you have time, please visit my profile and give me some advice // I think I solved too many easy 800 rating problems
Name |
---|
In CP you can just try and guess that some idea (maybe greedy) is correct. Code brute force approach about that idea and submit it. It's indeed correct if you got TLE (which is equal to not wrong answer) or AC :)
In order to really prove that some idea is true you have to study math OR solve bunch of problems and learn from them.
And I did look at your profile, I see you solved many A and B problems. Learn to solve them quick (virtual contests). Once you got that (you'd probably already reach high pupil) start to solve C and D.
https://leetcode.com/problems/bulb-switcher/
Check out this Infamous and most disliked Problem Bulb switcher. The answer is mathematical and too stressful to handle.
I appreciate your suggestion. Thanks man.
well basically the problem is to count the numbers from $$$1$$$ to $$$n$$$ that have odd number of divisors.
if you think about divisors of a number, you can see that for every divisor $$$d$$$ of a number $$$x$$$, there's its let's say mirror divisor $$$x/d$$$. So you may guess that every number actually should have even number of divisors (if for every $$$d$$$ you have $$$x/d$$$ you should end up with even number of divisors right?). But it's not the case. In which cases a number has odd number of divisors then? When $$$d = x/d$$$, since you only count number of unique divisors (you don't count the same number twice).
Now the problem is to find number of such $$$i$$$ that there's some divisor $$$d = i/d$$$. Simple math and you see that $$$d^2 = i$$$, so $$$i$$$ should be perfect square. You can count them manually, since the square root of the biggest perfect square $$$i$$$ cannot be bigger than $$$d^2 = i \leq n, d \leq \sqrt{n}$$$ (complexity $$$O(\sqrt{n})$$$)
And finally you can notice that integer $$$\sqrt{n}$$$ is literally the biggest such number $$$d$$$, and every $$$d$$$ less than $$$\sqrt{n}$$$ works as well (if $$$d^2 \leq n$$$, then obviously $$$(d-1)^2 \leq n$$$ if $$$d > 0$$$). So the answer is $$$\sqrt{n}$$$
I don't see the reason why it is so disliked
I solved this problem like the second I read the statement, it's all about practice I guess then afterall. Solve more problems like this and you'll get the idea how to think to solve this kind of problems.