Red0's blog

I need math help
By Red0, history, 2 months ago, In English

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!

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

»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Divisibility

Combinatorics

Bitwise operations

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! I'll check them out!

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah I was shocked too I think cpalgorithms number theory section is great

→ Reply
»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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!

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cheers brother :) I still can't understand why only perfect squares stay on though :/

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Aren't there numbers out there that have a non-even number of divisors and aren't a perfect square?

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          for every divisor i of n, there is a divisor n/i

          → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh wait, that makes a lotta sense when you draw out all the factors. Thanks everybody!

            → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so let me explain,

          when you find divisor of n what we do ?

          vector<int> store;
for(int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        store.push_back(i);
        if (i != n / i) store.push_back(n / i);
    }
}

          {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.

          → Reply
»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

literally no math needed today what are you on

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        D is the least mathy problem of the first 4 ig (A,B,C is pretty math heavy imo)

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            figure out the math formula or figure out the math casework

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tend to ignore the tags when i practice tho (yes i know there's hide tags but still)

      → Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

602p ta orz

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    nah, im not orz lol :). half the class has higher rating than i do after this contest

    → Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah this cool! Thanks!

    → Reply