TripleM5da's blog

By TripleM5da, history, 3 years ago, In English

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.

Announcement of ACPC Kickoff 2021
  • Vote: I like it
  • +111
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Will there be an editorial after the contest?

»
3 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      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