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 | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | maroonrk | 3575 |

5 | fantasy | 3526 |

6 | ko_osaga | 3500 |

7 | ksun48 | 3491 |

8 | Um_nik | 3486 |

9 | jiangly | 3474 |

10 | orzdevinwang | 3461 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 177 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 161 |

8 | kostka | 160 |

9 | YouKn0wWho | 158 |

10 | errorgorn | 153 |

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*

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/05/2023 23:36:24 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

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 tonot wrong answer) orAC:)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

oddnumber 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 ofuniquedivisors (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 thinkto solve this kind of problems.