noomaK's blog

By noomaK, history, 17 months ago, In English

Hello Codeforces!!

We're honored to invite you to TheForces Round #17 (AOE-Forces) which will take place on Jun/17/2023 18:05 (Moscow time).

What is a TheForces Round?
What is AOE?

The registration is open now! please don't forget the time.

You will have 2 hours and 15 minutes to solve 6 problems.

  • Also we want to thank You for participating in our rounds.

Discord Server (1000+ people, join for a cookie)

Contests' archive

Editorial

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

| Write comment?
»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Nice round! Neat problems! Hope you'll enjoy!

»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

As a tester, I can confirm to you that the round is great and all the problems are interesting. Good luck in the round!

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    As a Friend of the tester. Please give him contribution because he deserves it.

    click here
»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I remind you to join the Discord server!

»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Excited for this

»
17 months ago, # |
  Vote: I like it +13 Vote: I do not like it

AOE2 is my favorite game in my childhood! I still play it now. However every time when I play this game before a CF contest my performance would be a disaster...

»
17 months ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester, I can assure that everyone will have a non-negative delta in this round.

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

As a tester, problems are interesting, hope you can enjoy them!

»
17 months ago, # |
  Vote: I like it +27 Vote: I do not like it

As an author, give me contribution ;)

»
17 months ago, # |
  Vote: I like it -6 Vote: I do not like it

TheForces Orz!

»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

My favorite RTS game! Wow!

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

OMG AOE-Forces Round :)

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

excited

»
17 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I like playing as holy roman empire in aoe4.

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

as a tester, u will enjoy solving the problems:)

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I'm excited for this Thanks for your efforts guys

»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Warrior Scouts are the best!! ILALUUUUUUU

»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I'm coming with the mangudai

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a participant,I shall play as english

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish I won't go with the late game choice Xd

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

As a tester, You will enjoy balanced problemset ;)

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's time for real eltihab my friend

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I have a complexity of O(n * 2^k * k). The author's solution seems to have the same complexity. But my solution keeps getting TLE. Can anyone tell me where I am going wrong? Link to Submission: Link. Thanks in advance.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Note that you are using __gcd() too. So your complexity is not $$$O(n \cdot 2^k \cdot k)$$$.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      But in the editorial there is also a line checking if __gcd(a[i], a[j]) is 1. I think the solution in the editorial also uses O(n * 2^k * k) other than the __gcd() check.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Order of loops matter too. Look at the editorial code carefully. They are checking gcd for each possible pairs only once.

»
17 months ago, # |
Rev. 7   Vote: I like it +19 Vote: I do not like it

I nuked $$$D$$$ with the Micali-Vazirani (MV) algorithm. See:

An $$$O(|E|\sqrt{|V|})$$$ algorithm for finding maximum matching in general graphs, Silvio Micali and Vijay V. Vazirani, 21st Annual Symposium on Foundations of Computer Science, 1980.

It is a very advanced algorithm. Note that the complexity of the Edmonds blossom algorithm is $$$O(|E||V|^2)$$$, which is not sufficiently fast! For the MV algorithm, I adapted a code from a github repository. Its code quality is reliable.

My final code:

Spoiler

Overall complexity:

Part1: Calculating the gcd and constructing the graph: $$$O(nklogmaxa_i)$$$.

Part2: There are $$$|V|=n$$$ vertices and at most $$$|E|=nk$$$ edges in this graph. Thefore, the complexity of the matching process is: $$$O(n^{\frac{3}{2}}k)$$$. In practice, there is an additional log, i.e., $$$O(n^{\frac{3}{2}}k logn)$$$.

Therefore the overall complexity is:

$$$O(nk(logmaxa_i + \sqrt{n}logn))$$$, which can pass this problem easily. Also, MV algorithm is not a randomized algorithm, so the complexity is guaranteed no matter what the test data are.