Today's mathforces contest screwed me over. Does anybody have good material suggestions so that I can quickly improve my skills in number theory and combinatorics?
Thanks!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
6 | adamant | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Today's mathforces contest screwed me over. Does anybody have good material suggestions so that I can quickly improve my skills in number theory and combinatorics?
Thanks!
Название |
---|
Divisibility
Combinatorics
Bitwise operations
Thanks! I'll check them out!
https://youkn0wwho.academy/topic-list
Use this.This has all the math topic that you'll ever require in cp. Just start with some common topics.There are quite high lvl topics also just skip them for now
Thank you!
Yeah I was shocked too I think cpalgorithms number theory section is great
I'm certainly not an expert but I am definitely better at math than coding for now. I don't think you needed a deep mathematical understanding to solve todays problems. For problem b for example, you just go, when does a light get changed? It has a divisor. For every divisor it as another number than goes with it right? (like 2 and 3 make 6). Does this mean every light stays on? Nah, when is the number of (unique) divisors not even. A perfect square. If you don't believe that a number has an odd num of divisors iff it is a perfect square. Try proving that an even number of divisors implies a number is not a perfect square, this is an equivalent statement in fact. After that the problem breaks down.
I'm by no means a great coder, in fact, I had a horrible contest because I didn't know the sqrt function was imprecise, which wasted me like 40 mins, but I hope what I said makes sense. Cheers!
Cheers brother :) I still can't understand why only perfect squares stay on though :/
Perfect squares are off at the end. Perfect squares have odd number of divisors which makes them off at the end, while other numbers have even number of divisors and are on at the end.
Aren't there numbers out there that have a non-even number of divisors and aren't a perfect square?
for every divisor i of n, there is a divisor n/i
Suppose $$$i$$$ is a divisor of $$$x$$$. Then, $$$\cfrac{x}{i}$$$ is also a divisor of $$$x$$$, so all $$$i$$$ and $$$\cfrac{x}{i}$$$ are paired. There is one exception: when $$$i = \cfrac{x}{i}$$$, which means $$$i = \sqrt{x}$$$. This can be the only number that has no pair, and for this number to exist $$$x$$$ must be a perfect square.
Oh wait, that makes a lotta sense when you draw out all the factors. Thanks everybody!
and an lgm was born
so let me explain,
when you find divisor of n what we do ?
{1, n}, {2, n / 2}, {3, n / 3} ..... so all divisor are in pair except sqrt(n) if it exits ? right ?
so we know if n is perfect sq then it has odd no. of divisor.
literally no math needed today what are you on
in the first 4 problems, i mean. (i assume that is what he's going after given his attempts in contest)
you can say it has math tags but none of today's problems actually have much of a requisite math knowledge, except maybe B, but even that is pretty basic imo
D is the least mathy problem of the first 4 ig (A,B,C is pretty math heavy imo)
the problems are math heavy, but A is greedy and C is casework (or just figure out the formula). You can make an argument for B being math i guess
figure out the math formula or figure out the math casework
it's literally simple bitwise operations? there are 4 cases, 1/1, 1/0, 0/1, 0/0 and for each case you try setting that bit to either 1 or 0. that's technically "math" but anyone who has a basic knowledge of binary should be able to do it.
sadly even that is tough for me :(
someone told me that, if you force ourself to see problem as specific problem of math, dp, binary search etc. you will endup with not solving a problem.
i tend to ignore the tags when i practice tho (yes i know there's hide tags but still)
602p ta orz
nah, im not orz lol :). half the class has higher rating than i do after this contest
Basically, you have to memorize the "Bulb Switcher" problem, because the trick shows up sometimes.
If you need a good reference solution, check out this one. Amazingly, his code runs in $$$0$$$ ms while using only $$$39.6$$$ megabytes, beating $$$100$$$ percent of the other solutions.
Unable to parse markup [type=CF_MATHJAX]
MikeMirzayanov I'm not sure if you care, but it doesn't look like CF can render percent signs in LaTeX.
Ah this cool! Thanks!