Блог пользователя Red0

I need math help
Автор Red0, история, 2 месяца назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
2 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Divisibility

Combinatorics

Bitwise operations

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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!

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

literally no math needed today what are you on

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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

          → Ответить
          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            figure out the math formula or figure out the math casework

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              2 месяца назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

              → Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

602p ta orz

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
2 месяца назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить