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

Автор TripleM5da, история, 3 года назад, По-английски

Hey everyone!

I'd like to invite you to participate in the ACPC 2021 Kickoff contest on the gym on Jun/26/2021 11:00 (Moscow time).

The problems were created by me, KhaledKEE, eagle93, and compiler_101. The contest will include 12 problems and 5 hours to solve them.

I'd like to thank Mostafa_ELbadawy, Amirnasr, and Mohammad_Yasser for testing our (Initially) Bug ridiculed contest.

While the setters didn't have fun creating the contest the participants at the official contest said it was good.

We hope you like the contest or don't doesn't really matter.

Анонс ACPC Kickoff 2021
  • Проголосовать: нравится
  • +111
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Auto comment: topic has been updated by TripleM5da (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

We can't see the contest in the Gym. Can we get an invite link or is there some group that needs to be joined?

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Will there be an editorial after the contest?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

For N=0 Jury's answer in D is 2 but in J it's 0. The empty sum should be counted as 0.
Also what exactly is the solution of D?
Please add ghost participants as well.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve H?

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

    Build a prefix sum array to find the sum of arbitrary subarrays in $$$O(1)$$$ time. Then for each possible $$$X$$$, find the answer. At first glance, this looks $$$O(N^2)$$$, but most values of $$$X$$$ have few intervals. Formally, either $$$X \leq \sqrt{N}$$$, which takes $$$O(N^{\frac{3}{2}})$$$ time, or $$$X > \sqrt{N}$$$, so there are $$$\leq \sqrt{N}$$$ intervals to consider. This branch also takes $$$O(N^{\frac{3}{2}})$$$ time. The overall runtime is $$$O(N^{\frac{3}{2}})$$$.

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

      I think it is O(Nlog(N)) because of the harmonic series.

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

        That is true! Much better complexity analysis is to say each $$$X$$$ takes $$$O(\frac{N}{X})$$$ time, which of course is $$$O(N \log N)$$$ time.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Good problems overall. Absolutely enjoyed solving problem D, thanks for that.

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

    can u tell me the solution, I tried dp , but getting wrong ans, I have tested some numbers but they seems right

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      I can't prove it, but here's what I did.

      Assume we can use only multiplication and division. Then we can use a simple O(N2) DP to pre-process and solve each test case in O(1).

      We can optimize it to roughly O(N log N) if we notice that to do the multiplication, we only need to check the divisors of a number. Also, we don't need to check all possible candidates for addition. It suffices to check for less than 10 candidates, from 1 to N. Just try adding X and N-X for each X in {1, 2, 3, 4, 5, 6, 7, 8, 9}. It's pretty intuitive if you think about it. As because you also have multiplication, you don't need to do many additions.

      How to handle division and subtraction? We can't do DP naively with them, because we'll run into cycles. There are some other tricks you can use here, but the following works pretty nicely.

      Assume we won't ever need to use numbers greater than 4N in our expressions. Do the previous DP with additions and multiplications for all the numbers not exceeding 4N. Then do another DP with subtraction and division (same as in before, just in reverse). After this, do we have the optimal answer? Well only for some values, but not for all because we did the DP in a fixed order and it's not necessary for them to maintain this ordering in the expressions.

      What we can do though, is run this whole cycle over and over again until it converges. Each time, some new values will get updated and we can basically repeat this until all the DP values from 1 to N stops updating. This converges pretty fast, requires less than 10 iterations.

      How did we get these magic numbers like 4N and 10? Just intuition and some trial and error.

      Code